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

~(x-1)= 00001110

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

___________________________________________________________

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store