HAKMEM Item 175

HAKMEM is a collection of computer trivia produced by the MIT Artificial Intelligence Laboratory in 1972. Item 175, by Bill Gosper, gives an algorithm for finding the next higher number with the same number of 1 bits — for example, 110011 (51) is the next number after 101110 (46) with four 1 bits.

The algorithm

The original algorithm was written in PDP-10 assembly code:

1
2
3
4
5
6
7
8
9

MOVE B,A
MOVN C,B
AND C,B
ADD A,C
MOVE D,A
XOR D,B
LSH D,-2
IDIVM D,C
IOR A,C

A direct conversion to JavaScript gives:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function next(a) {
  let b = a
  let c = -b
  c = c & b
  a = a + c
  let d = a
  d = d ^ b
  d = d >>> 2
  c = d / c
  a = a | c
  return a
}

Refactoring the code and renaming the variables gives:

1
2
3
4
5
6
7

function next(n) {
  let lowestBit   = n & -n
  let leftBits    = n + lowestBit
  let changedBits = n ^ leftBits
  let rightBits   = (changedBits / lowestBit) >>> 2
  return (leftBits | rightBits)
}

A manual algorithm

To understand how the algorithm works, let’s consider how we would solve the problem manually. Suppose we start with this bit string (where the numbers above the bit string are the position indices, and the numbers below are the values represented):

If we think of the 1 bits in terms of their indices (here 5, 3, 2, and 1), we can see that to create a higher number at least one of the bits must move to the left.

Moving a bit that’s further to the right results in a smaller increase — for example, moving the bit at index 5 to index 6 results in an increase of 32, while moving the bit at index 3 to index 4 results in an increase of only 8.

Moving the bits at index 2 or 1 to the left would require the bit at index 3 to move in order to make space, but this results in a larger increase than moving only the bit at index 3.

So the first step is to find the rightmost 1 bit that has a 0 bit to its left (in this example, the bit at index 3) and move it to the left (to index 4):

This represents a higher number (54), but it’s not the next higher number. We can create a lower number (51) that’s still higher than the original number (46) by taking the 1 bits to the right of the bit we moved and moving them as far to the right as possible:

Implementing the manual algorithm

The steps in the manual algorithm don’t correspond directly to processor instructions, but each step can be implemented by a combination of arithmetic operations (treating the value as a number) and bitwise operations (treating the value as a bit string).

To show how the code works we’ll use this example bit string, representing the number 46:

All modern computers represent negative numbers using the two’s complement system. The two’s complement representation of −46 is:

A well-known feature of the two’s complement system is that the rightmost 1 bit of a number and of its negation are in the same position, so a bitwise AND of the two numbers results in a bit string containing only the lowest one bit:

Adding the lowest 1 bit to the original number causes a 1 to be carried until it reaches the first 0 bit, giving us the left bits of the next higher number:

We now need to determine the rightmost bits. A bitwise XOR with the original number tells us which bits have changed:

The changed bits include the two bits we want to move to right, but also two extra bits, representing the old and new positions of the bit we moved to the left. We can move these bits to the right by dividing by the lowest 1 bit:

We then perform a bitwise shift two places to the right to remove the two extra bits, giving us the right bits of the next higher number:

Finally, we perform a bitwise OR of the left and right bits to produce the next higher number (51):

Improving the PDP-10 code

The original PDP-10 code isn’t actually the optimal implementation of the algorithm. Reusing a register results in a saving of one register and one instruction:

1
2
3
4
5
6
7
8

MOVE B,A
MOVN C,B
AND C,B
ADD A,C
XOR B,A
LSH B,-2
IDIVM B,C
IOR A,C