Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 10 of 32

Powers of Two

March 2026 · 22 min read

Recognizing Powers of Two

Powers of two have exactly one bit set: $1 = 0b0001$, $2 = 0b0010$, $4 = 0b0100$, $8 = 0b1000$, and so on. This gives us the classic test:

bool isPowerOf2(uint32_t n) {
    return n != 0 && (n & (n - 1)) == 0;
}
// Why: n - 1 flips all bits below the single set bit
// n & (n-1) then clears that bit, giving 0
// Example: 8 = 0b1000, 7 = 0b0111, 8 & 7 = 0

The n != 0 guard is essential: 0 & (0 - 1) == 0 & 0xFFFFFFFF == 0 would otherwise misclassify 0 as a power of two. Equivalent one-liners:

bool isPowerOf2(uint32_t n) { return __builtin_popcount(n) == 1; }
// C++20:
#include <bit>
bool isPowerOf2(uint32_t n) { return std::has_single_bit(n); }

▶ Power-of-Two Test: n & (n-1)

Step through to see why n & (n-1) == 0 identifies powers of two.

Rounding Up to the Next Power of Two

uint32_t next_pow2(uint32_t n) {
    if (n == 0) return 1;
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}
// This "smears" the highest bit rightward, filling all lower bits with 1s.
// Adding 1 then rolls over to the next power of 2.
// Example: n = 100 → 127 → 128

// C++20:
#include <bit>
uint32_t next = std::bit_ceil(100u);  // 128

Rounding Down to the Previous Power of Two

uint32_t prev_pow2(uint32_t n) {
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n - (n >> 1);
}
// C++20: std::bit_floor(n)

Computing $\lfloor \log_2 n \rfloor$

int log2_floor(uint32_t n) {
    return 31 - __builtin_clz(n);
}
// clz = count leading zeros
// For n = 100: binary = 0b01100100, clz = 25, log2 = 6
// C++20: std::bit_width(n) - 1

Memory Alignment

Many systems require data addresses to be aligned to power-of-two boundaries. Alignment means the address is divisible by the alignment value.

// Align 'addr' up to the next multiple of 'align' (must be power of 2)
uintptr_t align_up(uintptr_t addr, size_t align) {
    return (addr + align - 1) & ~(align - 1);
}
// ~(align - 1) creates a mask that clears the low bits
// Example: align_up(0x1003, 16) = 0x1010

// Align down:
uintptr_t align_down(uintptr_t addr, size_t align) {
    return addr & ~(align - 1);
}
// align_down(0x1003, 16) = 0x1000

Modulo by a Power of Two

// x % (2^n) is the same as x & (2^n - 1)
uint32_t mod = x & (n - 1);  // n must be a power of 2

// Example: x % 16 = x & 15 = x & 0xF
// This is a single AND instruction instead of an expensive division

// Ring buffers use this for index wrapping:
int next_index = (current + 1) & (buffer_size - 1);

Why Powers of Two Are Everywhere

Competitive Programming Toolkit

Round Up to Next Power of Two with clz

// Smallest power of 2 that is >= n  (requires n > 1; n == 1 gives 1)
uint32_t bit_ceil_gcc(uint32_t n) {
    if (n <= 1) return 1;
    return 1u << (32 - __builtin_clz(n - 1));
}

// Largest power of 2 that is <= n  (n > 0)
uint32_t bit_floor_gcc(uint32_t n) {
    return 1u << (31 - __builtin_clz(n));
}

These compile to a few instructions (lzcnt + shift) and are typically faster than the bit-smearing version on modern hardware, but the smearing form is portable to environments without __builtin_clz.

C++20 <bit> Header

#include <bit>
std::has_single_bit(n);  // is n a power of 2?  (false for n == 0)
std::bit_ceil(n);        // smallest 2^k >= n   (UB if result not representable)
std::bit_floor(n);       // largest  2^k <= n   (0 if n == 0)
std::bit_width(n);       // number of bits to represent n; equals 1+log2(n) for n > 0
std::countl_zero(n);     // portable __builtin_clz
std::countr_zero(n);     // portable __builtin_ctz

Power-of-Two Hash Tables

If a hash table's capacity is a power of two, the modulo collapses into a bitwise AND:

// capacity is a power of 2; mask = capacity - 1
size_t idx = hash(key) & mask;     // replaces hash % capacity

This is only correct when capacity is a power of 2 — otherwise the AND drops high bits and clusters keys. Most fast hash tables (Robin Hood, Swiss tables, Java HashMap) grow by doubling for exactly this reason. The downside: a weak hash that varies only in the high bits will collide en masse, so production tables mix the hash (e.g. xor with high bits, Fibonacci hashing) before masking.

Summary

Practice Problems