To find the rightmost set bit in
N and perform bitwise AND operation with with itself. Then the position of the rightmost set bit in
N will be the position of the only set bit in the result.
N & -N // Same as N & (~N + 1)
Above takes advantage of the two’s complement system used to represent binary numbers, i.e. negative of a number is produced by inverting the number, then adding 1 (Two’s complement definition).
When you add 1, every bit starting at the bottom that is set will overflow into the next higher bit; this stops once you reach a zero bit. Those overflowed bits will all be zero, and the bits left to the last one affected will be the inverse of each other, so the only bit left is the one that stopped the cascade – the one that started as 1 and was inverted to 0.
Consider below example
#1 Consider integer N N = 0010010000110000 #2 Two's complement of N -N = 1101101111001111 + 1 or -N = 1101101111010000 #3 Bitwise binary AND N & -N = 0000000000010000