Bit Manipulation

1Bitwise Operation

You have to be comfortable with Bitwise operations (<<, >>, &, | , ~, ^). Please have a look at the basics here.

These are the operations to summarize

& - bitwise and
| - bitwise or
~ - bitwise nor
^ - bitwise xor
<< - bitwise left shift
>> - bitwise right shift

In this section I will get to more detailed explanation of the operations that we have seen in the previous post and also techniques for some new operations.

Masking

Masking is very basic in bit manipulation and make sure you get that right before starting any bit level operations.

  • use left shift (<<) to increase the shift from LSB to MSB
  • use right shift (>>) to increase the shift from LSB to MSB

How to mask?

  • Take a number lets say x = 8; The binary representation for this for 8 bit register will be 0000 1000
  • Lets consider that we are masking this number with a mask which is at the 0th position, that will be 0000 0001 = 1
x(8)       0000 1000
mask(1)    0000 0001
------------------------------------
x & mask will give us 0000 0000 - 0
x | mask will give us 000 1001 - 9
x ^ mask will give us 000 1001 - 9

What if we want to mask the bit at the position 4

  • Left shift the mask 1 with 4. this will move the bit to the 4th position. from
  • mask = 1 << 4 = (0000 0001   <<  4)=  0000 1000

Now

x(8)            0000 1000
mask(1 << 4)    0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 000 1000 - 8
x ^ mask will give us 000 0000 - 0

This is enough to start with our first bit trick.

#1 . How to check if the Integer is even or odd

We know that

  • for even number we will have LSB set to 0 always
  • for odd number we will have LSB set to 1 always
x(3)    0000 0011
1       0000 0001
------------------------------------
x & 1 will give us 0000 0011 - 3

So with this trick we can come up with the code like

if((x & 1) == 0)
   //even
else
   //odd

#2 . Check if the n’th bit is set or not

  • we take the number, lets say x = 8   =>  0000 1000
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x & mask)
  • bit wise & will be 1 if both the bits are set to 1. If the output is 1 for that bit then the bit is set

case 1 – position  – 4

x(8)          0000 1000
mask(1 << 4)  0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 0000 1000 - 8

case 2 – position  – 3

x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x & mask will give us 0000 1000 - 0
x | mask will give us 0000 1100 - 12 (we cannot use |)

We can write code for this like

if(x & (1 << position))
   // bit is set
else
  // bit is not set

#3 . Set the n’th bit

  • we take the number, lets say x = 8   =>  0000 1000
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x | mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1
x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x | mask will give us 0000 1100 - 12
y = x | (1 << position)

#4 . Unset the n’th bit

  • we take the number, lets say x = 12   =>  0000 1100
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x & ~mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1.
x(12)                     0000 1100
mask(1 << 3)   0000 0100 
~mask(1 << 3)             1111 1011
---------------------------------------------------
x & ~mask will give us 0000 1000 - 8
y = x & ~(1 << position)

#5 . Toggle the n’th bit

  • we take the number, lets say x = 12   =>  0000 1100
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x ^ mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1.
x(8)           0000 1000
mask(1 << 3)   0000 0100 
---------------------------------------------------
x ^ mask will give us 0000 1100 - 12
y = x  ^ (1 << position)

#6 Turn off the right most 1 bit

  • we take the number, lets say x =8   =>  0000 1000
  • subtract 1 from x (x – 1)
  • Bitwise & x and (x – 1)
x(8)         0000 1000 
x-1 (7)      0000 0111 
---------------------------------------------------
x & (x- 1) will give us 0000 0000 - 0 (4th position 1 is changed)
x(7)         0000 0111 
x-1 (6)      0000 0110
---------------------------------------------------
x & (x- 1) will give us 0000 0110 - 6 (0th position 1 is changed)
y = x & (x - 1)

#7 Turn on the rightmost 0 bit

  • we take the number, lets say x =8   =>  0000 1000
  • Add 1  to x (x + 1)
  • Bitwise | x and (x – 1)
x(8)         0000 1000 
x+1 (9)      0000 1001 
---------------------------------------------------
x | (x + 1) will give us 0000 1001 - 9
x(7)         0000 0111 
x+1 (8)      0000 1000
---------------------------------------------------
x | (x- 1) will give us 0000 1000
y = x | (x + 1)

#8 Isolate the rightmost 1 bit

  • we take the number, lets say x =8   =>  0000 1000
  • take -x (-x)
  • Bitwise & x and (-x)
x(11)         0000 1011 
-x (-11)      1111 0101         (~x + 1)
---------------------------------------------------
x & (-x) will give us 0000 0001 - 1
y = x & (-x)

#9 Isolate the rightmost 0 bit

  • we take the number, lets say x =8   =>  0000 1000
  • do the ~ of x
  • Bitwise & ~x and (x + 1)
~x(11)         1111 0101 
(x + 1)        0000 0110
---------------------------------------------------
~x & (x + 1) will give us 0000 0100
y = ~x & (x + 1)

Reference:
https://graphics.stanford.edu/~seander/bithacks.html
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: