vault

Bit Tricks for Powers of Two

28 min read

Bit Tricks for Powers of Two

The set of bit-level idioms that operate on, query for, or generate powers of two is the most-used family in practical low-level code. Five idioms cover almost everything: n & (n - 1) == 0 (is n a power of two?), n & -n (“lowbit” — the lowest set bit, always a power of two), 1 << (n.bit_length()) (smallest power of two > n, in Python), n.bit_length() - 1 (floor-log-base-2 of n), and (n + (1 << k) - 1) & ~((1 << k) - 1) (round n up to the next multiple of 2^k). Together these idioms drive every component of modern systems software that depends on power-of-two sizing: hash tables that replace the modulo-by-capacity hash % cap with the cheaper hash & (cap - 1) (requiring cap to be a power of two), the Fenwick Tree traversal step i += i & -i, the buddy memory allocator’s “round up to nearest power of two” before bucket selection, the alignment of memory addresses in malloc/free implementations, the slab-allocator bitmap free-block search, the kmalloc size-class quantization in the Linux kernel, and the constraint that vector<T> capacity grows by powers of two so that the underlying realloc can avoid copies on average. Understanding why these tricks work — n & (n - 1) clears the lowest set bit because the borrow chain in n - 1 flips exactly the trailing 0...01 pattern, and n & -n isolates that same bit because -n = ~n + 1 agrees with n only at the lowest set bit position — turns a memorized recipe into structural insight that lets you derive new idioms when the standard ones don’t fit.

1. Intuition — Why Powers of Two Matter

A power of two is an integer of the form 2^k for some non-negative integer k: 1, 2, 4, 8, 16, 32, 64, 128, .... In binary, a power of two is a single 1 bit followed by zeros: 2^0 = 1 = 0b1, 2^3 = 8 = 0b1000, 2^7 = 128 = 0b10000000. The defining property — exactly one bit set — is what makes the bit tricks below work.

Powers of two are special in computer science because:

  1. Hardware multiplies and divides by powers of two are free — they are bit shifts (x * 2^k = x << k, x / 2^k = x >> k for non-negative x). The CPU completes them in one cycle, with no actual multiplication unit involvement.
  2. Modulo by a power of two is a bitwise AND — x mod 2^k = x & (2^k - 1). This is 3-10× faster than integer modulo on modern hardware (modulo requires a division-style instruction at ~20 cycles; AND is 1 cycle). Hash tables, ring buffers, and circular queues exploit this constantly.
  3. Memory alignment is a power-of-two constraint — malloc returns addresses divisible by 8 or 16 because CPUs read aligned addresses faster (often required for SIMD). The “round up to a multiple of 2^k” idiom is the alignment computation.
  4. Binary trees with 2^k leaves are perfectly balanced. Binary indexed trees, segment trees, heap data layouts, and FFT bit-reversal permutations all assume power-of-two sizes for cleanliness.

A real-world analogy: think of powers of two as the “tick marks” on a logarithmic ruler. Almost every clean computer-science quantity (cache-line size, page size, hash table capacity, vector capacity, FFT size, BCH code length) lives on a tick mark. The bit tricks in this note are the tools for navigating between tick marks: “what’s the next tick mark up from n?”, “which tick mark am I on?”, “is n exactly on a tick mark?“.

2. Tiny Worked Example — Tracing Each Idiom on Concrete Numbers

Let’s apply each idiom to a representative n. Choose n = 12 = 0b1100 (not a power of two), m = 16 = 0b10000 (a power of two), and p = 13 = 0b1101 (not a power of two, an odd value).

2.1 Is n a power of two? — n > 0 && (n & (n - 1)) == 0

For n = 12 = 0b1100:

n      = 0b1100
n - 1  = 0b1011        (decrement; the lowest 1 flips to 0, all bits below flip to 1)
n & (n-1) = 0b1000     (AND keeps only the bits set in BOTH; the lowest 1 of n is gone)
result    ≠ 0          → not a power of two

For m = 16 = 0b10000:

m      = 0b10000
m - 1  = 0b01111       (single bit flips to 0; all below flip to 1)
m & (m-1) = 0b00000    (no bits in common)
result    == 0         → power of two ✓

The mechanism: in any positive integer n, the bits below the lowest set bit are zero; subtracting 1 flips that lowest set bit to 0 and turns all the (previously zero) bits below it into 1s. The bits above the lowest set bit are untouched by the borrow. The AND of n and n - 1 therefore zeroes out the lowest set bit and preserves everything above it. If there was something above (n had ≥ 2 set bits), the AND is non-zero. If the lowest set bit was the only set bit (n is a power of two), the AND is zero.

Edge case: n = 0. 0 - 1 = -1 (in two’s complement: all 1s), 0 & -1 = 0, so the test (n & (n - 1)) == 0 fires for n = 0. Most definitions say zero is not a power of two; always guard with n > 0.

2.2 Lowbit — n & -n

For n = 12 = 0b1100 (8-bit two’s complement for clarity):

n        = 0b00001100  (12)
~n       = 0b11110011
~n + 1   = 0b11110100  (= -12 in two's complement)
n & -n   = 0b00000100  (= 4)

The result 4 = 2^2 is the value of the lowest set bit of n — the bit at position 2. For n = 13 = 0b1101:

n        = 0b00001101
-n       = 0b11110011
n & -n   = 0b00000001  (= 1, the bit at position 0)

The lowbit is always a power of two (at most one bit set). This is the universal “extract the lowest 1” operation, used in:

  • Fenwick Tree traversal: i += i & -i walks up the tree; i -= i & -i walks down.
  • Iterating over set bits one at a time: lo = n & -n; ...; n ^= lo.
  • Branchless first-set-bit position via (n & -n).bit_length() - 1.

The proof that n & -n isolates the lowest set bit: in two’s complement, -n = ~n + 1. The +1 propagates a carry through the trailing zeros of ~n (which are the trailing ones of ~n — i.e., the trailing zeros of n)… actually the trailing 0s of n are 1s in ~n; adding 1 turns those 1s into 0s with a carry, until the carry hits the lowest 0 of ~n (= lowest 1 of n) and stops there, flipping that position from 0 to 1. So -n agrees with n only at the lowest set bit position; below, both are 0; above, they are bitwise complements. The AND therefore has exactly that one bit set. See Bit Manipulation Tricks §5 for the formal version.

2.3 Round up to next power of two

In Python (arbitrary-precision integers), the cleanest idiom uses bit_length():

def next_power_of_two(n: int) -> int:
    if n <= 1:
        return 1
    return 1 << (n - 1).bit_length()

For n = 12: (12 - 1).bit_length() = 11.bit_length() = 4 (since 11 = 0b1011, 4 bits), so 1 << 4 = 16. Correct.

For n = 8: (8 - 1).bit_length() = 7.bit_length() = 3 (7 = 0b111, 3 bits), so 1 << 3 = 8. The n - 1 ensures exact powers of two map to themselves (rather than being rounded up to the next).

For n = 17: (17 - 1).bit_length() = 16.bit_length() = 5 (16 = 0b10000, 5 bits), so 1 << 5 = 32. Correct.

In C, the equivalent uses __builtin_clz (count leading zeros) on a uint32_t:

uint32_t next_pow2_u32(uint32_t n) {
    if (n <= 1) return 1;
    return 1u << (32 - __builtin_clz(n - 1));
}

__builtin_clz compiles to one BSR (or LZCNT on modern CPUs) instruction. The expression 32 - __builtin_clz(n - 1) is the bit-position of the highest set bit of n - 1, plus one — equivalent to bit_length(n - 1) in Python.

A branchless version using shift-and-OR (Stanford bit hacks):

uint32_t next_pow2_branchless(uint32_t n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

This “smear-down” propagates the highest set bit into all lower positions (turning 0b00010000 into 0b00011111), then adds 1 to roll over to 0b00100000. Five shifts, five ORs, no loop. Pre-LZCNT hardware preferred this; modern code uses __builtin_clz.

2.4 Floor of log base 2 — n.bit_length() - 1

For n = 12 = 0b1100: bit_length(12) = 4 (it takes 4 bits to write 12 in binary, namely 1100), so floor-log2 is 4 - 1 = 3. Verify: 2^3 = 8 ≤ 12 < 16 = 2^4. ✓

For n = 16 = 0b10000: bit_length(16) = 5, floor-log2 is 4. Verify: 2^4 = 16 ≤ 16 < 32 = 2^5. ✓

In C with __builtin_clz for a 32-bit unsigned n:

int floor_log2_u32(uint32_t n) {
    return 31 - __builtin_clz(n);   // undefined if n == 0
}

This is the highest set bit position. Used in Sparse Table preprocessing (which needs floor(log2(n)) levels), in MSB-based binary tries, and in computing FFT lengths.

2.5 Round up to multiple of 2^k — (n + (1 << k) - 1) & ~((1 << k) - 1)

To align a memory address n to a 16-byte boundary (k = 4):

mask = (1 << 4) - 1 = 15 = 0b1111
n + 15:                                       (e.g., n = 33 → 48)
33 + 15 = 48
~mask  = ~0b1111 = 0b...11110000
48 & ~mask = 0b00110000 = 48                  (bit-and with mask cleared rounds down to multiple of 16)

For n = 33: aligned-up is 48. For n = 48 (already aligned): 48 + 15 = 63, 63 & ~15 = 48. The ”+ mask” ensures already-aligned values map to themselves; the AND with ~mask clears the low k bits, leaving a multiple of 2^k.

Rule: adding (2^k - 1) “pushes” n to the next aligned position; ANDing with ~(2^k - 1) “rounds down” to that position. This is the alignment formula, reused identically in malloc, in page-table code, in compilers’ stack-frame layout, and in SIMD code that needs aligned loads.

3. The Identities — Reference Card

OperationIdiomUse case
Test if n is a power of twon > 0 && (n & (n - 1)) == 0Hash table capacity check
Lowest set bit (value, a power of two)n & -nFenwick Tree step
Lowest set bit (position)(n & -n).bit_length() - 1; C: __builtin_ctz(n)First-free-bit in a bitmap allocator
Highest set bit (position)n.bit_length() - 1; C: 31 - __builtin_clz(n)Floor-log2
Floor log base 2n.bit_length() - 1Levels in Sparse Table, Segment Tree
Ceiling log base 2(n - 1).bit_length() for n > 1Number of bits to encode n distinct values
Smallest power of two ≥ n1 << ((n - 1).bit_length()) for n > 1Hash table grow, FFT length
Largest power of two ≤ n1 << (n.bit_length() - 1) for n > 0Largest Fenwick stride for size n
x mod 2^kx & ((1 << k) - 1)Hash bucket index
Round n down to multiple of 2^kn & ~((1 << k) - 1)Page-frame address
Round n up to multiple of 2^k(n + (1 << k) - 1) & ~((1 << k) - 1)Memory alignment
Multiply by 2^kn << kReplace n * 8 etc.
Divide by 2^k (unsigned n)n >> kReplace n / 8 etc.
Set bit k (mark a power of two)`n(1 << k)`

The first three are the “atomic” operations that everything else builds on; the rest are compositions or applications.

4. Powers of Two in Production: Hash Table Capacity

The most-cited application of (n & (n - 1)) == 0 is enforcing power-of-two capacity in a hash table. The relevant hash-table operation is mapping a hash value h to a bucket index in [0, cap):

bucket = h % cap

If cap is arbitrary, this is one DIV-style instruction (~20 cycles on modern x86). If cap is a power of two, the compiler can replace the modulo with h & (cap - 1) — a 1-cycle AND. 20× faster on the hot path.

Concrete production examples:

  • Java’s HashMap (java.util.HashMap) requires a power-of-two table size. Its source code rounds the user-requested initial capacity up to the next power of two via the smear-and-OR idiom (§2.3). The bucket lookup is h & (table.length - 1).
  • Go’s map uses a power-of-two number of buckets. Resizing doubles the bucket count.
  • Linux kernel hash tables (include/linux/hashtable.h) use a HASH_BITS(name) macro to enforce power-of-two sizing; lookup is hash & ((1 << bits) - 1).
  • Redis dict: dictht.size is always a power of two; dictht.sizemask = size - 1; lookup is hash & sizemask.
  • Python’s dict (CPython): the underlying table is power-of-two-sized; lookup uses hash & (size - 1) after a perturbation step.

The trade-off: power-of-two sizing makes mod cheap but means the bucket index uses only the low bits of the hash. If the hash is poorly distributed in its low bits, all entries collide. The mitigation is the bit-mixing finalizer: hash functions for power-of-two-sized tables include a final round of XOR-shift-multiply to spread the entropy across all bit positions before the AND. CPython does hash ^= (hash >> 16)-style mixes; Java’s HashMap.hash does (h = key.hashCode()) ^ (h >>> 16). These mitigation steps exist precisely because & keeps only the low bits.

CPython’s exact probing formula (verified against the current Objects/dictobject.c on the main branch as of 2026-05-30): the probe loop body is

perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);

with #define PERTURB_SHIFT 5 near the top of the same file. The 5 in i*5 (the linear-congruential multiplier) and the PERTURB_SHIFT = 5 shift amount happen to be the same digit but are independent choices — the multiplier was selected to make the probe sequence visit every slot in a power-of-two-sized table (the recurrence i ← 5*i + 1 (mod 2^k) is full-period because gcd(5, 2^k) = 1 and 1 is odd, per Hull-Dobell), and PERTURB_SHIFT controls how quickly the high bits of the hash are folded into the probe sequence. Both were tuned by Tim Peters and refined by subsequent CPython contributors. The accompanying explanatory comment block in dictobject.c (around lines 320–400) walks through the reasoning at length.

5. Powers of Two in Production: Buddy Memory Allocator

A buddy allocator maintains free blocks of every size 2^k for k = MIN..MAX. Allocation requests get rounded up to the next power of two (§2.3); a block of that size is split off from the smallest available bucket, with leftover halves recursively split and bucketed.

The bit tricks involved:

  1. Round request up: block_size = 1 << ((req - 1).bit_length()).
  2. Index into bucket array: bucket = (block_size).bit_length() - 1, the floor-log2 of block_size.
  3. Split a block: a block at address a of size 2^k splits into two halves at a and a + 2^(k-1).
  4. Find buddy: a block at address a of size 2^k has buddy at a XOR 2^k. The XOR flips the k-th address bit, swapping the two halves of the parent block. On free, check whether buddy is also free; if so, merge.

Buddy allocators appear in the Linux kernel’s page allocator (mm/page_alloc.c), in glibc’s malloc internals (transitively, via fastbins/largebins variations), in jemalloc and tcmalloc heuristics, and in many embedded / RTOS heap implementations. The key invariant — that all block sizes are powers of two — makes the address arithmetic clean and the buddy-find operation a single XOR.

6. Powers of Two in Production: Memory Alignment

When malloc(size) returns address p, p must be aligned to max_align_t’s alignment (typically 8 or 16 bytes on 64-bit systems) so that any primitive type can be stored there. SIMD types (e.g., __m128) need 16-byte alignment; __m256 needs 32-byte; __m512 needs 64-byte alignment.

The alignment computation is invariably:

size_t aligned = (size + alignment - 1) & ~(alignment - 1);

where alignment is required to be a power of two (so alignment - 1 is a clean low-bit mask). C++17’s std::align, Java’s MemorySegment.alignedSlice, Rust’s align_of_val_raw all apply this idiom under the hood.

The requirement that alignment be a power of two is itself enforced by (alignment & (alignment - 1)) == 0 checks at API boundaries (§2.1). C++‘s std::align_val_t constructor and Rust’s Layout::from_size_align both check power-of-two-ness and panic / fail otherwise.

7. Powers of Two in Fenwick Tree (Binary Indexed Tree)

The signature operation in a Binary Indexed Tree is the traversal step:

i += i & -i      // walk up to the next responsible node

The lowbit i & -i is always a power of two; it is the width of node i’s responsibility interval. Adding it to i jumps to the next node up the implicit binary tree. The whole tree’s structure — which nodes are responsible for which ranges — falls out of the power-of-two structure of the index. See Fenwick Tree for the full derivation.

The “lowbit” idiom is the canonical interview test of whether the candidate understands how power-of-two arithmetic and tree structure interact. The same arithmetic appears in Sparse Table (which preprocesses floor(log2(n)) + 1 levels), in heap-as-array indexing (which depends on 2*i and 2*i + 1 for left/right children), and in FFT bit-reversal permutations (which require n to be a power of two).

8. Pseudocode

8.1 Is Power of Two

is_power_of_two(n):
    return n > 0 AND (n AND (n - 1)) == 0

8.2 Lowest Set Bit

lowest_set_bit_value(n):
    return n AND (-n)               # value, a power of two

lowest_set_bit_position(n):
    if n == 0: return -1
    return floor(log2(n AND -n))    # via bit_length / __builtin_ctz

8.3 Floor and Ceiling Log2

floor_log2(n):                      # for n > 0
    return bit_length(n) - 1

ceiling_log2(n):                    # for n > 1
    return bit_length(n - 1)        # equivalently, ceil(log2(n))

8.4 Next and Previous Power of Two

next_power_of_two(n):
    if n <= 1: return 1
    return 1 << bit_length(n - 1)

prev_power_of_two(n):
    if n <= 0: return 0             # convention: undefined, return 0 or raise
    return 1 << (bit_length(n) - 1)

8.5 Round Up / Down to Multiple of 2^k

round_down_to_2k(n, k):
    return n AND NOT((1 << k) - 1)

round_up_to_2k(n, k):
    return (n + (1 << k) - 1) AND NOT((1 << k) - 1)

9. Python Implementations

def is_power_of_two(n: int) -> bool:
    """True iff n is a positive power of two."""
    return n > 0 and (n & (n - 1)) == 0
 
 
def lowest_set_bit(n: int) -> int:
    """Return 2^k where k is the lowest set bit position of n.
    Returns 0 if n == 0. Always a power of two for n > 0."""
    return n & -n
 
 
def lowest_set_bit_position(n: int) -> int:
    """Return k where 2^k is the lowest set bit of n. -1 if n == 0."""
    if n == 0:
        return -1
    return (n & -n).bit_length() - 1
 
 
def floor_log2(n: int) -> int:
    """floor(log2(n)) for n >= 1. -1 for n == 0 (sentinel)."""
    if n <= 0:
        return -1
    return n.bit_length() - 1
 
 
def ceiling_log2(n: int) -> int:
    """ceil(log2(n)) for n >= 1. Returns 0 for n == 1."""
    if n <= 0:
        raise ValueError("ceiling_log2 undefined for n <= 0")
    return (n - 1).bit_length() if n > 1 else 0
 
 
def next_power_of_two(n: int) -> int:
    """Smallest 2^k >= n. Returns 1 for n <= 1."""
    if n <= 1:
        return 1
    return 1 << (n - 1).bit_length()
 
 
def prev_power_of_two(n: int) -> int:
    """Largest 2^k <= n. Returns 0 for n <= 0."""
    if n <= 0:
        return 0
    return 1 << (n.bit_length() - 1)
 
 
def round_up_to_2k(n: int, k: int) -> int:
    """Smallest multiple of 2^k that is >= n."""
    mask = (1 << k) - 1
    return (n + mask) & ~mask
 
 
def round_down_to_2k(n: int, k: int) -> int:
    """Largest multiple of 2^k that is <= n."""
    return n & ~((1 << k) - 1)
 
 
def mod_2k(x: int, k: int) -> int:
    """x mod 2^k, computed as x & (2^k - 1). Works for x >= 0."""
    return x & ((1 << k) - 1)
 
 
# Sanity checks
assert is_power_of_two(16) and not is_power_of_two(12)
assert lowest_set_bit(12) == 4 and lowest_set_bit_position(12) == 2
assert floor_log2(12) == 3 and ceiling_log2(12) == 4
assert next_power_of_two(12) == 16 and next_power_of_two(16) == 16
assert prev_power_of_two(12) == 8 and prev_power_of_two(16) == 16
assert round_up_to_2k(33, 4) == 48 and round_down_to_2k(33, 4) == 32
assert mod_2k(33, 4) == 1

A subtle point: next_power_of_two(1) returns 1 (1 is 2^0), which is the desired behavior. next_power_of_two(0) returns 1 by convention; some libraries return 0 instead. Decide once per project and stick with it.

10. Complexity

All operations in this note are O(1) wall-clock time on fixed-width integers: each compiles to between 1 and 5 hardware instructions. On Python’s arbitrary-precision integers, bit_length() is O(log n / w) where w is the machine word size, but for n fitting in one or two machine words, it is effectively O(1).

Memory: O(1) per operation; no allocation.

The interesting complexity comparison is against non-bit-trick alternatives:

TaskBit trickNaïve loopSpeedup
Is power of two(n & (n-1)) == 0 (1 instr)Loop dividing by 2~30×
Floor log2bit_length - 1 or __builtin_clz (1 instr)Loop shifting until 0~30×
Lowest set bitn & -n (2 instr)Loop checking bits~30×
Next power of twosmear-down (5 instr) or __builtin_clz + shiftLoop multiplying by 2~30×
x mod 2^kx & mask (1 instr)Hardware DIV (~20 cycles)~20×

The 30× speedups are not exaggerations; in tight inner loops (hash table probing, allocator fast paths) replacing a divide with an AND has been measured to give exactly that speedup at the application level.

11. Diagram — Power-of-Two Bit Patterns and Their Predecessors

flowchart LR
    subgraph A ["Power of two: n = 16 = 0b00010000"]
        a4["1"] --- a3["0"] --- a2["0"] --- a1["0"] --- a0["0"]
    end
    subgraph B ["n - 1 = 15 = 0b00001111"]
        b4["0"] --- b3["1"] --- b2["1"] --- b1["1"] --- b0["1"]
    end
    subgraph C ["n & (n-1) = 0"]
        c4["0"] --- c3["0"] --- c2["0"] --- c1["0"] --- c0["0"]
    end
    A --> C
    B --> C

    subgraph D ["Not a power of two: n = 12 = 0b00001100"]
        d4["0"] --- d3["1"] --- d2["1"] --- d1["0"] --- d0["0"]
    end
    subgraph E ["n - 1 = 11 = 0b00001011"]
        e4["0"] --- e3["1"] --- e2["0"] --- e1["1"] --- e0["1"]
    end
    subgraph F ["n & (n-1) = 8 = 0b00001000 (≠ 0)"]
        f4["0"] --- f3["1"] --- f2["0"] --- f1["0"] --- f0["0"]
    end
    D --> F
    E --> F

What this diagram shows. Two side-by-side cases of the (n & (n - 1)) test. Top: n = 16, a power of two, whose binary representation has exactly one 1 (at bit 4). Subtracting 1 borrows through that single 1, turning it into 0 and the four bits below into 1s — the pattern flips from 0b10000 to 0b01111. The two bit-patterns share no set bit, so their AND is zero — confirming n is a power of two. Bottom: n = 12, not a power of two, with two set bits at positions 2 and 3. Decrementing affects only the lowest set bit (position 2): it flips to 0, and the bits below it (positions 0 and 1) flip to 1, giving 0b1011. The bit at position 3 (above the lowest set bit) is untouched in both n and n - 1. So the AND retains that bit, giving 0b1000 = 8 ≠ 0 — confirming n is not a power of two. The general principle visible here is: n - 1 differs from n only in the trailing-zeros region of n (everything from the lowest set bit downward); the bits strictly above are identical. Hence n & (n - 1) zeros out the lowest set bit and preserves everything above. If n had more than one set bit, the AND has remnants; if n had exactly one set bit (it’s a power of two), the AND is zero.

12. Variants and Generalizations

12.1 __builtin_popcount, __builtin_clz, __builtin_ctz

GCC and Clang expose three intrinsics for bit-position queries:

  • __builtin_popcount(n) — count of set bits (Hamming weight). Compiles to POPCNT on x86 SSE4.2+.
  • __builtin_clz(n) — count of leading zeros. Compiles to BSR (or LZCNT on AMD/Intel since ~2013). Undefined when n == 0.
  • __builtin_ctz(n) — count of trailing zeros (= position of lowest set bit). Compiles to BSF (or TZCNT). Undefined when n == 0.

These are the single-instruction underpinnings of “highest bit position” (= 31 - clz(n) for 32-bit) and “lowest bit position” (= ctz(n)). On hardware lacking POPCNT/LZCNT, the compiler falls back to a SWAR / lookup-table implementation; the call still works, just with more instructions. See Bit Manipulation Tricks §12.6.

Java exposes Integer.numberOfLeadingZeros, Integer.numberOfTrailingZeros, and Integer.bitCount with similar semantics (and identical JIT optimization on hot paths).

12.2 .bit_count() and .bit_length() in Python

Python 3.10+ has both built-in:

  • n.bit_length() — number of bits needed to write n in binary, ignoring sign and leading zeros. 0.bit_length() == 0. Floor-log2 is n.bit_length() - 1 for n > 0.
  • n.bit_count() — number of set bits (popcount). Equivalent to bin(n).count('1') but ~10× faster.

12.3 Power-of-Two Caps in Vector Growth

std::vector<T> (libstdc++ and libc++), Java’s ArrayList, Go’s slice grow strategy, and most dynamic-array implementations grow capacity by a fixed factor (1.5× or 2×) and round to a power of two. This guarantees that the amortized cost per push_back is O(1) and that the underlying allocator (often a slab allocator with power-of-two size classes) can give you the new chunk efficiently.

12.4 Lookup Tables for Tiny Bit Operations

For embedded systems lacking POPCNT / LZCNT, a 256-entry byte-popcount lookup table (or an 8-entry log2-of-power-of-two table indexed by the popcount of the next-power-of-two minus one) gives O(1) bit operations using only loads. The BitTable approach is the basis of __builtin_popcount fallbacks and of older OS bitmap-allocator implementations.

12.5 De Bruijn Sequences for Lowest-Bit Position

A pre-computed De Bruijn sequence allows computing ctz(n) in O(1) without a hardware instruction:

static const int debruijn32[32] = { /* precomputed */ };
int ctz_debruijn_u32(uint32_t n) {
    return debruijn32[((n & -n) * 0x077CB531) >> 27];
}

The multiplication-and-table-lookup is faster than a software loop and works on any hardware. Used in old game engines, in the JVM’s HotSpot JIT for older targets, and in some embedded compilers.

12.6 Power-of-Two Reduction in Numerical Algorithms

FFT (Fast Fourier Transform) requires input length n = 2^k. When the natural input is not a power of two, code zero-pads to the next power of two via §2.3. This makes FFT an O(n log n) operation but with n rounded up; for a strictly non-power-of-two length, “Bluestein’s chirp z-transform” or “mixed-radix FFT” exist but are more complex. See FFT (planned).

13. Pitfalls

13.1 (n & (n - 1)) == 0 Treats Zero as a Power of Two

0 - 1 = -1 (all 1s in two’s complement), 0 & -1 = 0. The test fires for n = 0. Always guard: n > 0 && (n & (n - 1)) == 0. In Python, (0 & -1) == 0 is also True because -1 in Python is “infinite leading 1s,” and AND with 0 is 0. Same fix.

13.2 next_power_of_two(1) Conventions

Should next_power_of_two(1) return 1 (since 1 = 2^0 is itself a power of two, the smallest one ≥ 1) or 2 (the next power of two strictly greater than 1)? Most libraries return 1. Java’s Integer.highestOneBit(1) == 1, but next_power_of_two is not in the Java standard library; user implementations vary. Check the convention in your codebase before relying on it.

13.3 Overflow in 1 << k When k == BIT_WIDTH

In a 32-bit unsigned integer, 1 << 32 is undefined behavior in C/C++. On x86, the shift hardware masks k to its low 5 bits, so 1 << 32 == 1 << 0 == 1 — a wrong answer that compiles silently. The smear-down next_power_of_two in §2.3 has this hazard for inputs where bit_length(n - 1) == 32: 1 << 32 overflows. Guard with n <= 1u << 31 for 32-bit, or use uint64_t. Python is immune (arbitrary precision).

13.4 Signed vs Unsigned Right Shift

-1 >> 1 is -1 in C (arithmetic shift, signed) but in Java’s >>> operator (logical shift, unsigned) it is 0x7FFFFFFF. Python uses arithmetic shift (-1 >> 1 == -1). This matters for bit-twiddling: any code that uses >> to “scan from the top” must work on unsigned types or mask explicitly. See Bit Manipulation Tricks §10.3.

13.5 n.bit_length() on Negative Integers

In Python, (-12).bit_length() == 4 — it ignores the sign and reports the bit-length of the absolute value. This means floor_log2(-12) via bit_length - 1 gives 3, which is meaningless (log of negative is undefined). Always guard the sign on inputs.

13.6 Confusing “next power of two” vs “next-greater power of two”

For n = 16:

  • “Smallest power of two ≥ n” → 16.
  • “Smallest power of two > n” → 32.

The two differ at exact powers of two. 1 << ((n - 1).bit_length()) gives the first; 1 << (n.bit_length()) gives the second. Pick the right one for the use case. Hash table grow (“we hit capacity, double it”) wants 1 << (n.bit_length()); alignment (“round up to nearest 2^k boundary”) wants ≥.

13.7 lowbit of INT_MIN Overflows in Signed Arithmetic

In 32-bit signed two’s complement, -INT_MIN overflows: -(-2^31) = 2^31, which doesn’t fit. C compilers may emit undefined behavior. The bit pattern works out — INT_MIN & -INT_MIN = INT_MIN (the lowest set bit is bit 31, the only one set) — but the standard doesn’t guarantee it. In Python, no issue. In C, use unsigned types for bit math.

13.8 Forgetting That Powers of Two Are Implicitly Required for & (cap - 1)

A code review smell: bucket = hash & (cap - 1) without anywhere a power-of-two check on cap. If cap = 100, then cap - 1 = 99 = 0b1100011, and hash & 99 returns values in {0, 1, 2, 3, 32, 33, 34, 35, 64, ...} — only ~25 distinct values out of cap = 100 possible. Buckets 4..31, 36..63, ... are unreachable. Catastrophic collision pile-up. Always pair & (cap - 1) with a power-of-two enforcement.

13.9 Underestimating the Speedup of & mask Over % n

A common claim: “% is fine, the compiler optimizes it.” It does not unless cap is a compile-time constant. For runtime cap, the compiler emits a DIV. Benchmarking shows a 5-10× regression versus & (cap - 1) in tight loops. If you control cap, force it to a power of two and use AND.

13.10 Mistaking bit_length for popcount

(12).bit_length() == 4 (number of bits to write 12 in binary), but bin(12).count('1') == 2 (number of set bits). The two are very different — one is “what’s the highest bit set,” the other is “how many bits are set.” Easy to mix up under interview pressure. Memorize: bit_length answers “how big,” popcount / bit_count answers “how dense.”

14. Common Interview Problems

ProblemLeetCode #What’s tested
Power of TwoLC 231n > 0 && (n & (n - 1)) == 0
Power of FourLC 342Power of two + bit-position parity (& 0x55555555)
Next Greatest Power of TwoclassicalSmear-down or 1 << bit_length(n - 1)
Number of 1 BitsLC 191popcount / Brian Kernighan
Counting BitsLC 338dp[i] = dp[i & (i-1)] + 1
Reverse BitsLC 190Shift-and-mask cascade (5-step bit reversal)
Single NumberLC 136XOR; lowbit not directly used here
Hamming DistanceLC 461popcount(a ^ b)
Sum of Two IntegersLC 371Addition without +, requires lowbit-style carry handling
Bitwise AND of Numbers RangeLC 201Common high-bit prefix via right-shift
Maximum XOR of Two NumbersLC 421Trie of bits, greedy from MSB (uses bit-length)
Find the Highest Power of 2 ≤ Nclassical1 << (n.bit_length() - 1)
Align Up / Align Downsystems(n + mask) & ~mask and n & ~mask
Capacity-doubling hash tablesystemsPower-of-two enforcement and & (cap - 1)
Fenwick Tree index stepsystemsi += i & -i

The bit-trick interview theme is broad; the specific power-of-two recipes in this note are tested by ~30% of bit-manipulation problems and ~all systems-programming problems.

15. Open Questions

  • When does the smear-down next_power_of_two beat __builtin_clz-based code in practice? On modern x86 with hardware LZCNT, the intrinsic is faster (1 cycle). On older x86 without LZCNT, the smear-down (~5 cycles) ties or beats BSR (~3 cycles + sign-extend). On RISC architectures without count-leading-zeros, the smear-down is the only portable option.
  • Why do some hash table implementations (e.g., abseil’s flat_hash_map) use prime-sized tables instead of power-of-two? Prime sizes give better collision behavior with weak hash functions but lose the AND-instead-of-modulo speedup. Abseil mitigates with custom hash-finalizer mixing and accepts the slower modulo. The trade-off is implementation-dependent.
  • Is there a portable way to test n is a power of two in constant time without branches? (n & (n - 1)) == 0 && n != 0 involves a comparison and an AND. Fully branchless: ((n & (n - 1)) == 0) & (n != 0). Usually irrelevant; the comparison is itself constant-time on modern CPUs.

16. See Also

Graph View

Backlinks