Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the right most set bit of a number

Objec­tive: Given a num­ber, write and algo­rithm  to find the right most set bit in it (In binary representation).

Exam­ple:

Number : 1
Binary representation: 1
Position of right most set bit: 1

Number : 6
Binary representation: 1 1 0
Position of right most set bit: 2

Number : 11
Binary representation: 1 0 1 1
Position of right most set bit: 1

Number : 24
Binary representation:  1 1 0 0 0
Position of right most set bit: 3

Approach:

If N is a num­ber then the expres­sion below will give the right most set bit.

N & ~ (N -1)
  • Let’s dig lit­tle deep to see how this expres­sion will work.
  • We know that N & ~N = 0
  • If we sub­tract 1 from the num­ber, it will be sub­tracted from the right most set bit and that bit will be become 0.
  • So if we negate the remain­ing num­ber from step above then that bit will become 1.
  • Now N & ~(N-1) will make all the bits 0 but the right most set bit of a number.

Exam­ple:

Say N =10, so N = 1 0 1 0, then ~N = 0 1 1 0 => N & ~ N =0

N – 1 = 1 0 1 0 – 0 0 0 1 = 1 0 0 1

~(N-1) = 0 1 1 0

N & ~(N-1) = 0 0 1 0 => 2nd bit

Code:

Out­put:

Right most set bit for 1 is : 1
Position: 1.0

You may also like...

  • lipsa patel

    The posi­tion for num­ber 24 should be “4” not “3”.