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 unset bit OR zero bit of a number

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

This prob­lem is sim­i­lar to: Find the right most set bit of a number

Exam­ple:

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

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

Number : 13
Binary representation: 1 1 0 1
Position of right most unset bit: 1

Approach:

If N is a num­ber then the expres­sion below will give the right most unset 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 add 1 from the num­ber, it will make most unset bit to 1, if there are any set bits in the right side of unset bit, those bit will become zero.
  • (exam­ple : 1 0 1 1 + 0 0 0 1 = 1 1 0 0)
  • So if we negate the orig­i­nal num­ber it will make the right most unset bit to 1.
  • Now ~N & (N+1) will make all the bits 0 but the right most unset bit of a number.

Exam­ple:

Say N =11, so N = 1 0 1 1
N + 1 = 1 1 0 0
~N = 0 1 0 1
~N & (N+1) = 0 1 0 0 => 2nd bit (assuming right most index is 0)

Code:

Out­put:

Right most Unset bit :2.0

You may also like...