Bit Manipulation Tips and Tricks (Part 1) | Code Samurai

Bit Manipulation Tips and Tricks (Part 1) | Code Samurai

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

Read full article from Bit Manipulation Tips and Tricks (Part 1) | Code Samurai