Step 5 of 5
Challenge: power of two
Bit tricks let you answer some questions in a single expression. The classic one: is a number a power of two?
A power of two has exactly one 1 bit: 1 is 0001, 2 is 0010, 4 is 0100, 8 is 1000.
The trick: x & (x - 1)
Subtracting 1 flips the lowest 1 bit to 0 and every 0 bit below it to 1. For example, 12 is 1100 and 11 is 1011. AND-ing them keeps only the bits both have: 1000, which is 8. So x & (x - 1) is x with its lowest set bit cleared.
If x had only one bit set, clearing it leaves 0. That's the power-of-two test. Zero needs special care, though: 0 & (0 - 1) is also 0, but 0 is not a power of two, so it has to be excluded separately.
The same trick gives a fast way to count bits: keep clearing the lowest set bit until nothing is left, counting as you go. The loop runs once per 1 bit instead of once per bit position.
#include <stdio.h>
int count_bits_fast(unsigned x) {
int n = 0;
while (x != 0) {
x &= x - 1;
n++;
}
return n;
}
int main(void) {
printf("%d %d %d\n", count_bits_fast(12), count_bits_fast(255), count_bits_fast(0));
printf("%u %u\n", 12u & (12u - 1), 16u & (16u - 1));
return 0;
}
2 8 0
8 0
16 & 15 is 0 because 16 is a power of two; 12 & 11 is 8 because 12 has two bits set.
Why bother with tricks like this?
They show up in performance-sensitive code (hash tables often require power-of-two sizes so that hash & (size - 1) can replace a slower %), in systems programming, and in interviews. More importantly, working them out builds a real understanding of how numbers are stored.
Your turn: write int is_pow2(unsigned x) returning 1 or 0, without loops.