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