HAKMEM Item 175 describes a concise algorithm that, given an integer, calculates the next higher integer with the same number of one bits.
By adding this on to the original input, we obtain the leftmost bits of the output:
Next it performs a logical ‘xor or’ of the input and this value to determine which bits have changed:
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):
Finally, it performs a logical ‘or’ on the leftmost and rightmost output bits to combine them into the answer:
Read full article from HAKMEM Item 175
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);
}By adding this on to the original input, we obtain the leftmost bits of the output:
Next it performs a logical ‘xor or’ of the input and this value to determine which bits have changed:
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):
Finally, it performs a logical ‘or’ on the leftmost and rightmost output bits to combine them into the answer:
Read full article from HAKMEM Item 175
