Sunday, January 11, 2015

Bit level tricks : setting, unsetting and toggling a bit

I will be talking here, about some of the coolest language agnostic bit hacks. Below diagram, gives brief idea about the relative positions of bits in a 1 byte number. Right most bit, 0th is LSB and left most bit, 7th bit is MSB.

Bit operators 

Just as a re-cap, let's start with the list of bit operators. I have discussed about them, here.  I have not included unsigned right shift operator, >>> in below list, as it's specific only to Java.
&  -  Bitwise AND
 |   -  Bitwise OR
^   -  Bitwise XOR
~   -  Bitwise NOT
>> - Bitwise SHIFT LEFT
<< - Bitwise SHIFT RIGHT
Above operators are mostly used for bit level manipulation.

Below table, will be handy to understand the behavior of SHIFT operators. It is used to manipulate a bit a particular position like 3rd, 7th etc. LSB is 0th bit and MSB is 7-th bit (as shown in above diagram as well).
1<<0 or 1  - 00000001
1<<1         - 00000010
1<<2         - 00000100
1<<3         - 00001000
1<<4         - 00010000
1<<5         - 00100000
1<<6         - 01000000

1<<7         - 10000000
Note - index starts from 0.

 

Bit Hacks

Here, we will always consider 8 bit (1 byte) signed numbers to explain all hacks. The same approach can be used for signed number of any size (like 16, 32 bits etc ).

 

#1: Set bit at a position

Setting a bit means, updating its value to 1 (irrespective of the current value). OR-ing a bit with 1 sets the bit ( & OR-ing a bit with 0 leaves it unchanged).

     00000000   (0 in binary)                     
|    00000001    ( 1 or 1 << 0)
     ------------
     00000001


     01001001   (73 in binary)
|    00001000    ( 1<<3)
     ------------
     01001001

General formula for setting n-th bit of a number X
X = X  | 1 <<  n 

#2: Unset bit at a position

To unset a bit, we need to AND it with 0. But the tricky part is that, other bits should be 1 so that the only the target bit gets unset. 

00000001  = 1
11111110   = ~1

     00000001   (1 in binary)                     
&  11111110    ( ~(1<<0)  )
     ------------
     00000000


     01001001   (73 in binary)
11110111    ( ~(1<<4)  )
     ------------
     01000001

General formula for unsetting n-th bit of a number X
X = X  & ~(1<< n) 

#3: Toggle a bit

 Toggling a bit means flipping it; i.e. make it 1 if it is 0 and 0 if it is 1. So we need to use something which turns 0 to 1 and 1 to 0. 

Test if the bit is set. 
    - If set, AND it with 0 (to make it 0)
    - if not set, OR it with 1 (to make it 1)

Let's take a case where we want to toggle the MSB of a 8 bit variable, X whose value is -1.
//n = 7
if(X & (1<<n) == 0){
   //nth-bit is set
   X = X & ( 1<< n)
}else{
  //nth-bit is not set
  X= X | (1<<n)
}
Above approach works, but it require multiple operations to toggle a bit. Can it be done using a single step? YES!
Recall that, XOR-ing a bit with 1 will turn it to 0 if it's already 1 and vice-versa.

    01001001   (73 in binary)
^  00001000    ( 1<<3)
     ------------
    01000001 

 It can be generalized as:
 X = X  ^ (1<< n)

---
do post your inputs/feedback.
keep coding !!!

No comments:

Post a Comment