Boosting Performance: Essential Bit-Hacks

Bitwise manipulation is music to the ears of our processors - a captivating blend of mathematics and boolean logic. Its geometric nature, intriguing patterns, and lightning-fast operations make it an aspect of programming that is entertaining, instructive and useful in performance-critical code.

In this article, we will look at some basic bit-hacks to reach commonly desired outcomes. We will also try to understand the underlying logic, which is an ideal way to solidify our knowledge.

To get the most out of this article, make sure you know the truth tables for logical AND, OR and XOR, and understand the following operators in C:
| & ^ |= &= ^= << ~

If you need a refresher, click here. Although we'll be employing the C language, these methods can be easily adapted to your language of choice. Numbers will be represented with 8 bits for simplicity.

Reading the Nth bit

First, we are creating a temporary value by shifting a set bit N times to the left. For different values of N, this number would be in binary:

00000001 ( N = 0 )
00000010 ( N = 1 )
00000100 ( N = 2 )

Now, if you AND this number with the initial value, there are two cases: the result will be a nonzero value if that set bit is ANDed with 1, otherwise it will be zero. As those two cases in C can be interpreted as true and false respectively, we can do it like this:

(num & (1 << N)) //to be used in a condition

Setting the Nth bit

The same logic applies here. We create our second operant the same way we did before. Now, if we OR the num with ( 1 << N), nothing else will change except the Nth bit, because

x | 0 == x (the value is maintained)
x | 1 == 1 (the Nth bit will be set, no matter if x is 0 or 1)

num |= (1 << N);

Clearing the Nth bit

Here, we are creating the number 2^N, and then flipping all of its bits with the help of one's complement operator. So our temporary number looks like this:

11111110 ( N = 0 )
11111101 ( N = 1 )
11111011 ( N = 2 )

Now what will happen if we AND this number with num? You guessed it, everything stays the same except the Nth bit, because:

x & 0 == 0
x & 1 == x

num &= ~(1 << N);

Toggling the Nth bit

We are applying the same logic, but this time with the XOR operator. This will flip the value of the Nth bit, because:

1 ^ 1 = 0
0 ^ 1 = 1

Everything else stays the same because:

x ^ 0 = x

num ^= (1 << N);

Determining parity

This one is quite simple, once we understand that every binary number is a multiple of 2, except if the LSb is set! So we get true if it is odd, and false if it is even.

(num & 1) //to be used in a condition

Clearing lowest set bit

We are looking here at an algorithm, that clears the rightmost set bit of a number.

To understand how it works, we need to first understand which bits of a binary number change when we subtract 1.

Here is a little exercise: Try to spot the differences between the minuend and the result. Can you notice a pattern?

00000001 - 1 = 00000000
00000010 - 1 = 00000001
00000100 - 1 = 00000011
01101100 - 1 = 01101011
11111111 - 1 = 11111110

...

Here's the answer: if we subtract 1 from a binary number, the lowest set bit will be cleared and all bits to its right will be set. Anything on the left side will stay the same.

Now, what will happen if we AND the minuend with the result? Let's get another visual:

10101010 | 10101001

Only the two least significant bits will change to zero, and anything that is on the left side of the lowest set bit will stay the same, because N & N = N, therefore the result of this operation will be:

10101000

num &= (num - 1);

In conclusion

We saw a few bit-hacks and understood why they work. If you are hungry for more, there are at least two excellent resources on this subject which go into much greater detail:

Bit Twiddling Hacks by Sean Eron Anderson (free)

Hacker's Delight by Henry S. Warren, Jr. (book)

I hope you found this article engaging and informative. Thank you for taking the time to read it. Take care and enjoy your coding journey!