How do you check if a number is a power of two?
Short answer: x && !(x & (x - 1)). A power of two has exactly one bit set, and x & (x - 1) clears the lowest set bit, so the result is zero only when there was a single bit.
#include <stdbool.h>
#include <stdint.h>
bool is_pow2(uint32_t x)
{
return x != 0 && (x & (x - 1)) == 0;
}
Why x - 1 works: subtracting 1 turns the lowest set bit into 0 and every bit below it into 1. Bits above it do not change.
x = 0b0100_0000 (64)
x - 1 = 0b0011_1111
x&(x-1) = 0b0000_0000 -> power of two
x = 0b0101_0000 (80)
x - 1 = 0b0100_1111
x&(x-1) = 0b0100_0000 -> not a power of two
Why x != 0: for x = 0, x - 1 wraps to 0xFFFFFFFF and the AND is 0, so without the check 0 would wrongly count as a power of two.
Alternatives: __builtin_popcount(x) == 1, or C23 stdc_has_single_bit(x).
Where it is used: checking that a ring-buffer size, DMA block size or alignment is a power of two before using & (size - 1) instead of % size.
Follow-up: "Check if x is a power of four?" It must be a power of two and the bit must be in an even position: is_pow2(x) && (x & 0x55555555u).