Category Archives: tricks

Clearing the right most set bit in a binary number

Given an integer, write a program to clear the right most set bit in it’s binary representation.
For example, consider a number 54. It is represented in binary as  
1 1 0 1 1 0
The right most set bit is marked in bold. We need to convert this to 
1 1 0 1 0 0
Let us look at the approach step by step.

If you negate the number to -54, it is represented in computer’s memory in 2’s compliment.

0 0 1 0 1 0

Let us perform a bit-wise AND operation between these two.

1 1 0 1 1 0
0 0 1 0 1 0
————&
0 0 0 0 1 0

Subtract this from the original number to get the result. So x – ( x & -x) gives the required answer.

Here is the simple program to test the above.