Finding position of first least significant non-zero bit in Binary number
let’s say we have x = 11110010
here the position of first non-zero least significant is 2 as shown in Bold.
how to find that position
let’s understand subtraction by one in binary
we can not do 0–1 in first bit so we need to borrow from second bit
second bit represents 2 in decimal
so 2 = 1+1
so we can have 2 number of 1’s if we borrow from 2nd place
so that second bit will become zero in result.
now we know that whenever we subtract 1 from the number,the first least significant bit will become zero in the result.
we can use this to our advantage.
lets say we do ~(x-1)
in this operation of ~(x-1) our first non zero bit which was turned off due to (x-1) operation will be turned on. but other bit will become toggled from initial position.
we have x-1 = 11110001
now we have ~(x-1) = 00001110
initial x = 11110010
now compare x with ~(x-1)
if we (~)toggle x the we will have 00001101
~ x = 00001101
now we can see that only difference between ~x and ~(x-1) is least significant non zero position bit. which is indicated in bold
so if we do x & ~(x-1)
then we will have only least significant non-zero bit signed on.
x & ~(x-1) = 11110010 & 00001110
we we have our answer as 2 now