23/10/2017

[Java] Find lowest set bit in number

This is a very interesting bit magic trick: given a number, return the first (from least significant) bit set to 1.

The magic formula is:

n & ~(n - 1)

To break it down:

- (n - 1) creates a mask where the last bit set to 1 is now 0
- negating that mask gives us a new mask that is the exact opposite of n except for the bit we flipped before
- the AND operation of the original number with this mask, will then return only the bit we flipped

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.

Da grandi poteri derivano grandi responsabilità.