C

Bit Hacks You Must Know

Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming hacks do the same but in a tricky way.

This post assumes that you know about the following bitwise operations and some C/C++ language.

  1. & : Bitwise AND
  2. ||   : Bitwise OR
  3. ^  : Bitwise XOR
  4. ~  : Bitwise NOT
  5. <<: Bitwise Shift Left
  6. >> : Bitwise Shift Right

I’m taking the size of each variable as 8 bit, where the first bit is b0 and last bit (MSB) is b7.

 

Let’s go ahead with some bit hacks.

 

Check if the integer is even or odd


if ((a & 1) == 0) {
a is even
}
else {
a is odd
}

The righmost or zeroth bit of odd number is always set. Checking the rightmost bit only will do if we want to find out that a is even or odd.

 

Turn off the rightmost 1-bit


b = a & (a - 1)

If x is even, then x – 1 will be odd and vice versa too. This is gonna unset the zeroth bit. Why? The rightmost bit of odd number is always set.

 

Test if the n-th bit is set


if (a & (1 << n)) {
n-th bit is set
}
else {
n-th bit is not set
}

1 is left shifted n times and then anded with a, do a example paper run, and you will get it better.

 

Set the n-th bit


b = a | (1 << n)

Shift left 1 n times or it with a and then put it into a new variable b.

 

Unset the nth bit


b = a | ~(1 << n)

Shift 1 n times left, complement it or it with a and then put it into a new variable b.

 

Toggle the n-th bit


b = a ^ (1 << n)

Shift left 1 n times, xor it with a and assign it to a new variable.

 

Uppercase to lower case letter


"CAPITAL LETTER" XOR " " = small letter

Xoring with space i.e., ” “, will give you lowercase letter.

 

If a integer is power of 2


b = a && !(a & (a - 1));

Check a and a – 1 is 0, and AND the result with a, to check that a is not zero and some power of 2.

 

Let me know if you want me to explain it more. 🙂

Advertisements

One thought on “Bit Hacks You 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s