Bit Manipulation Tips and Tricks (Part 1)

In this series, we'll try to compile a list of tips and tricks that are useful for performing bitwise operation.

1. Multiply a number by a power of two using bit left shift

Remember the bit shift operation? << and >>? Well if we left shift a number, we are multiplying that number by a power of two. For example, 1 = 0001. If we left shift it by 1, we'll have 1 << 1 = 0010 = 2 = 1 * 2^1. If we left shift it by 2, we'll have 1 << 2 = 0100 = 4 = 1 * 2^2. Thus, the general formula is:

a << b = a * 2^b

2. Divide a number by a power of two using bit right shift

In opposite to left shift, when we right shift a number we divide it by a power of two. For example, 4 >> 2 = 0100 >> 2 = 0001 = 1 = 4 / 2^2. Here is the general formula:

a >> b = a / 2^b

3. Toggle a specified bit in a bit string without effecting other bits

For example, we have a bit string 0111 and you have to turn the left most bit on 0 -> 1. How can we do that? We'll use XOR (^), left shift operation (<<) and the 0001 (1) bit string.

1. Shift the 1 bit of 0001 to the position of the bit you want to change. In our example, we need to toggle the 3th bit (first bit is at position 0, that's why our target is at 3rd position not 4th). Thus, we shift 0001 to the left by 3. 0001 << 3 = 1000.
2. Lastly, we XOR our bit string with the helper bit string. So, we have 0111 ^ 1000 = 1111

The general formula is:

bit_string = bit_string ^ (1 << positionOfBitToToggle)

4. Checking if a bit is on or off without affecting other bits

Let's say that we have a bit string of 1101 and we want to know if the 2nd bit is on or off. Here is a way to do it:

int isAvailable (int bitString, int targetNum)
{
  return bit_string & (1 << targetNum);
}

• bit_string: the bit string whose bits we are interested in. For example, 1101 and we are interested in the 2nd bit which is the bit in bold.
• 1: is just our helper bit string. Its binary value is 0001
• targetNum: is the position of the bit we're interested in. For example, targetNum is 2 if we're interested in the 2nd bit of 1101.

According to our example, to find out if the 2nd bit of 1101 is on or off, we'll just apply the formula like this: 1101 & (0001 << 2) = 1101 & 0100 = 0100 = 4. The result is 4 which is greater than 0, so we know that the bit we're interested in is on (1).

Let's do another example, if our bit string is 1001 and we're interested in the 1st bit which is 0 (in bold). Again, just apply the formula: 1001 & (0001 << 1) = 1001 & 0010 = 0000 = 0. The result is 0, so we know that our bit is off (0).

This trick concludes the first part of our series. Please stay tuned. Thanks for reading.