A bit handling technique

Recently i discovered a new bit twiddling hack, which proves to be quite useful.

If a number is AND-ed bit-wise with its two's complement, then the resulting number will hold the first bit that is set in the original number(from LSB)


For ex: Consider a number 62hex(11000010).
Its two's complement is 3Ehex(00111110).

AND-ing the two numbers gives us 2hex(00000010) ,
i.e the first digit of 62hex(from LSB) is got.

If you want the next bit that is set, clear the bit of the previous operation and repeat the above steps.

i.e. Clear the processed bit(2hex) from 62hex => 60 hex.

AND the num with its 2's complement => 60hex && 40hex = 40hex(0100 0000)

Thereby the next set bit in the byte is obtained.

This is a very helpful tool when one has to perform certain operation based on the bit set in the byte of an array. One can loop or shift through only the bits that are set in the byte, thereby reducing the execution time by a great extent.