Bit level tricks: setting and unsetting right most 1 bit

This post is in continuation with the earlier post, where I have discussed some of the bit manipulation techniques. In previous post, I discussed about how to set, unset and toggle a bit at fixed position like 3rd from right/LSB, 1st from left/MSB etc. Setting and unsetting a bit at fixed position is relatively easier to achieve by using left and right shift operators.
 
This post will discuss about manipulating a bit at relative positions, like right most 1 bit, left most 0th bit etc. Here also, I will explain all tricks using 8 bit number.

 

Bit Hacks

#1: Unset the rightmost 1 bit

So objective is to turn off the right most 1 bit in a number.  If input number is 10100100 then it needs to get converted into a number with b2 (b0 is LSB; highlighted bit is b2) getting turn off.

                           X    = 00100100 

                          X-1  = 00100011   

   Expected response = 00100000   ??

As shown above, subtracting 1 from number unsets the right most 1 but it also sets the zeros right to 1. Please note that other bits left of targeted 1 remain unchanged. Can X and X-1 be combined to get the expected response. If you notice closely the last 2 bits, ANDing looks to do the job. 

     00100100   (36 in binary)
&  00100011    (36 -1 )
     ------------
     00100000 

     10000000 (-128 in binary)

&  01111111  (-128 -1 in binary = 127 )

     ------------

     00000000

 

     00000000 (0 in binary; there is no right most bit)

&  11111111  (0 -1 in binary = -1)

     ------------

     00000000  (no change)

General formula for unsetting the right most 1 bit of a number, X

X = X  & (X-1)

Also, be careful of the impact of changing AND to OR in above formula.

#2: Unset all except rightmost 1 bit

So we need to unsets (clears off or changes to 0) all bits except the right most 1 bit. Trivial approach to solve this would be to RIGHT SHIFT the number until you encounter the set bit (i.e. 1) and counting the number of shifts done. 

    while(X & 1 != 0){

        count++;

        X = X>> 1;

    }

 Above approach more easier to think logically but execution complexity and verbosity is high. Let's think of abstracting it into minimal number of steps. 

     00100100   (X = 36;  in binary)
     11011011    (~X )

                +1
     ------------
     11011100  (-X; in two's complement system -X = ~X+1)

Let's use above -X 

     00100100   (X = 36;  in binary)
&  11011100  (-X)
     ------------
     00000100  (bingo!!!)

     10000000   (X = -128;  in binary)
&  10000000  (-X = -128)
     ------------
     10000000  

And it can be generalized as:

X = X  & (~X)

#3: Set the right most 0-bit

So this hack expects to turn on the right most 0 bit (irrespective of position). This also can be achieved by multiple steps but we want to achieve it compactly. 

     00100100   (X = 36;  in binary)

                +1
     ------------
     00100101  (X+1; )

So adding 1 sets up the right most 0. This can be used to set the right most 0 to 1. 

      00100100   (X = 36;  in binary)

  |   00100101   (X+1 )
     ------------
      00100101  

      01110111   (X )

  |   01111000   (X+1 )
     ------------
      01111111

So OR-ing X with X+1 does the job. 

X = X  | (X+1) 

Related Post : Bit manipulation in Java

 Bit level tricks : setting, unsetting and toggling a bit

----

keep coding !