Bit Manipulation

1. Bit Operators

1. & ( bitwise and )
2. |   ( bitwise or )
3. ^ (xor)
4. <<, >> (shift)
5. !   ( bitwise not, complement)

2. Usages

• &     used to set a bit into 0
• |       used to set a bit into 1
• ^      used to check whether two bits are the same. ( thus can store information )
• <<    used to perform the times 2 operation

3. How to set a sequence of bits into 0s or 1s

Let say we can an integer X and would like to set from i-th bit to j-th bit into 0s (or 1s).

We first get a mask that all bits are 1 except the bits from i to j ( looks like 11111000..0011111)

Finally  X = X & Mask 

4. How to get that mask

How can we get the mask that all the bits are 1s except some are 0s ( all are 0s except some are 1s)

In order to get some masks looks like this

• 00000111 :     (1<<3)-1
• 11100000 :     ( !0 ) - ( (1<<5) -1 )
• 11100111 :     ((1<<3)-1)  |  (( !0 ) - ( (1<<5) -1 ))         

5. How to swap two variable without using extra variable

x = x ^ y

y = x ^ y

x = x ^ y

This shows that XOR operator could store extra information within one variable which could be used in some brain teaser.

6.How to check if a integer is power of 2

( ( x & ( x -1 ) ) == 0 )

All the integer which is power of 2 and 0 will return true.

x = 0 ;      // 2 ' 00000000
x-1        ;  // 2 ' 11111111
x & ( x-1 )// 2 ' 00000000

6.Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”