HAKMEM Item 175

HAKMEM Item 175 describes a concise algorithm that, given an integer, calculates the next higher integer with the same number of one bits. Such an algorithm could be used to enumerate all permutations of a bit string, as shown in the example below — click on a bit to flip it, or click ‘Next’ to calculate the next integer. This page reproduces the original PDP-10 code, provides an equivalent JavaScript version for readability, and explains how the algorithm works.

0
0
0
0
1
1
1
1

The original code

HAKMEM Item 175 originally appeared in the following form:

ITEM 175 (Gosper):
To get the next higher number (in A) with the same number of 1 bits: (A, B, C, D do not have to be consecutive)

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

The original code contains an error; the final line should read ‘IOR A,D’.

A JavaScript equivalent

The following JavaScript function implements the algorithm described in HAKMEM Item 175:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Returns the next higher integer with the same number of one bits. The
 * parameter is:
 *
 * value - the value on which to perform the calculation
 */
function hakmemItem175(value){

  // find the lowest one bit in the input
  var lowestBit = value & -value;

  // determine the leftmost bits of the output
  var leftBits = value + lowestBit;

  // determine the difference between the input and leftmost output bits
  var changedBits = value ^ leftBits;

  // determine the rightmost bits of the output
  var rightBits = (changedBits / lowestBit) >>> 2;

  // return the complete output
  return (leftBits | rightBits);

}

How it works

To understand how the algorithm works, we first consider how we might solve the problem manually, and then go on to show that the code above is equivalent to this manual process. Consider the following example bit string:

0
0
1
0
1
1
1
0

Counting from the left, this string has one bits in the third, fifth, sixth, and seventh positions. To create a higher integer, at least one of the bits must move to the left. The first zero bit to the left of a one bit is in the fourth position, so we move one of the one bits to the right of the zero bit into that position:

0
0
1
1
?
?
?
?

The integer is now greater than the previous integer. To ensure it is as small as possible, we place the remaining one bits as far right as possible:

0
0
1
1
0
0
1
1

The algorithm in HAKMEM Item 175 is equivalent: it determines the leftmost and rightmost bits of the output separately and then combines them. It starts by performing a logical ‘and’ of the input and its negative. This well-known trick returns the lowest one bit in the input:

0
0
0
0
0
0
1
0

By adding this on to the original input, we obtain the leftmost bits of the output:

0
0
1
1
0
0
0
0

Next it performs a logical ‘exclusive or’ of the input and this value to determine which bits have changed:

0
0
0
1
1
1
1
0

To produce the rightmost bits of the output, it then divides this value by the lowest one bit (in order to remove any trailing zero bits) and then logically shifts the new value two bits to the right (to remove the extra one bits that resulted from the bit that moved):

0
0
0
0
0
0
1
1

Finally, it performs a logical ‘or’ on the leftmost and rightmost output bits to combine them into the answer:

0
0
1
1
0
0
1
1

Improving the PDP-10 code

As a final note, the original PDP-10 is not optimal. Reusing a register yields a saving of one register and one instruction:

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

Where now?

Found this useful? Share it:

Also in Articles: