In the book The C programming language (2nd edition, Chapter 2.10, Assignment Operators and Expressions) an algorithm is shown to count the number of 1-bits in an integer:
int bitcnt(int x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
This is the algorithm that we all normally would write. Note that if we consider an integer which has all the bits zero except the leftmost one, it does exactly the same number of iterations as bits in the integer. For example, the 8-bit integer with only the leftmost bit set is -128 in decimal, or ‘1000 0000’ in binary, and the algorithm will do 8 iterations.
In the same chapter, the authors present this exercise:
Exercise 2-9. In a two’s complement number system, ‘x & (x - > 1)’ deletes the rightmost 1-bit in ‘x’. Explain why. Use this observation to write a faster version of ‘bitcount’.
Interesting. The expression ‘x & (x - 1)’ deletes the rightmost 1-bit in an integer?! Let’s see some examples with 8-bit integers:
| x - 1 | x - 1 | x & (x - 1) |
|---|---|---|
| 0000 0001 | 0000 0000 | 0000 0000 |
| 0000 0000 | 1111 1111 | 0000 0000 |
| 0000 1000 | 0000 0111 | 0000 0000 |
| 1000 0000 | 0111 1111 | 0000 0000 |
| 1010 1000 | 1010 0111 | 1010 0000 |
Therefore, the expression ‘x & (x - 1)’ resets the first bit on the right whose value is 1, and keeps the rest intact.
This can help us to write a faster version of the original algorithm. This improved version is taken from here, where you can see other solutions to the exercises in the book (and help solve others).
int bitcnt(int x)
{
int b;
for (b = 0; x != 0; x &= (x - 1))
b++;
return b;
}
This algorithm can be faster than the original one because it only executes the loop once for each bit which is set in the input. If ‘x’ has only the leftmost bit set, we saw that the first algorithm did as many iterations as bits in the integer. But this second algorithm will only do one! Of course, the worst case will be the same for both: do as many iterations as bits in ‘x’.
Let us explore some traces of the second algorithm. We will use 8 bit integers. Consider the value -128:
| iteration | x | b | x - 1 | x = x & (x - 1) | x != 0 |
|---|---|---|---|---|---|
| 0 | 1000 0000 | 1 | 0111 1111 | 0000 0000 | yes, stop |
Another example, value -119:
| iteration | x | b | x - 1 | x = x & (x - 1) | x != 0 |
|---|---|---|---|---|---|
| 0 | 1000 1001 | 1 | 1000 1000 | 1000 1000 | no |
| 0 | 1000 1000 | 2 | 1000 0111 | 1000 0000 | no |
| 0 | 1000 0000 | 3 | 0111 1111 | 0000 0000 | yes, stop |
Therefore, the new algorith only does as many iterations as 1-bits in the integer. For a 32-bit integer with only the leftmost bit set, the first algorithm will do 32 iterations; the second will do one.