23/10/2017

[Java] Right propagate the lowest set bit in number

Building on top of the magic to find the first set LSB in a number, we have another magic trick to right propagate it.

Eg:

10100

would become:

10111

The code for this is:

 public static long rightPropagateLowestSetBit(long n){  
  if(n > 1) return n | getLowestSetBitPosition(n);  
  return n;  
 }  


And the breakdown:

- 0 and 1 have nothing to propagate, so return them directly
- find the lowest set bit
- bitwise OR the number with the position of its lowest set bit, that means we start counting from 0 as LSB; the position is then exactly the mask for the missing 1s we need to set.

To get the position we simply return the first set LSB - 1 and pay attention to the fact that now 0 has -1 as result :)

You can check more bit magic on my Gist along with some test cases.

No comments:

Post a Comment

With great power comes great responsibility