</>EmbeddedInterview

How do you check if a number is a power of two?

EasyBit Manipulation

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).