BitsAlgorithmaka n & (n-1), lowest set bit, next power of two, highest set bit

Power-of-Two Tricks

Test for powers of two with n & (n-1), isolate the lowest set bit with n & -n, and round up to the next power of two with shift-or smearing.

▶ Visualize Pattern: Bit Manipulation Practice (3)

Progress

Overview

A power of two has exactly one 1-bit, so n is a power of two iff n > 0 and n & (n - 1) == 0 — subtracting one clears that lone bit and leaves nothing. Example: 8 = 1000b, 7 = 0111b, 8 & 7 = 0; but 12 & 11 = 1100b & 1011b = 1000b ≠ 0.

n & -n isolates the lowest set bit as a power of two: 12 & -12 = 4. It is the step size of a Fenwick Tree and the key to enumerating set bits. The highest set bit is 1 << floor(log2 n), found by counting leading zeros or by smearing.

Next power of two ≥ n: decrement n, OR it with its own right shifts by 1, 2, 4, 8, 16 (and 32 for 64-bit) so every bit below the top one becomes 1, then add 1. Or in one call: 1 << (bit_length(n - 1)). Related: x & (2^k - 1) is x mod 2^k, (x + 2^k - 1) & ~(2^k - 1) rounds x up to a multiple of 2^k (alignment).

power of twon & (n-1)n & -nbit smearingO(1)

Intuition

A mental model before the formal terms.

A power of two in binary is a single lit bulb in a row of dark ones. Subtracting one "cascades" that bulb: it goes dark and every bulb to its right lights up. Overlay the two rows and nothing coincides — the AND is zero. If there had been a second lit bulb higher up, it would have survived in both rows and shown up in the AND.

Smearing to find the next power of two is like dragging the highest lit bulb rightwards until every bulb below it glows; adding one then carries all the way up into a single new bulb one position higher.

How it works

Is power of two: n > 0 && (n & (n - 1)) == 0.
Lowest set bit: n & -n (two's complement -n = ~n + 1). Its index is ctz(n) (count trailing zeros).
Highest set bit: 31 - clz(n) for 32-bit n, or bit_length(n) - 1. The value is 1 << that.
Next power of two ≥ n (n ≥ 1): v = n - 1; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return v + 1.
Modulo and division by 2^k: x & (2^k - 1) and x >> k (non-negative x).
Is power of four: power of two and the set bit is in an even position: (n & 0x55555555) != 0.

Why it works

n - 1 flips the lowest set bit to 0 and all lower zeros to 1, leaving higher bits intact. If n had only one set bit, no higher bits exist and n & (n - 1) has nothing left. If it had two or more, the higher ones survive the AND.

-n = ~n + 1: ~n flips every bit; adding 1 carries through the trailing ones (which were trailing zeros of n) and stops at the first 0 of ~n, which is the lowest 1 of n. Above that, -n is the complement of n, so AND is 0 there; at the lowest set bit both are 1.

Smearing: after v |= v >> 1 the top two bits are set; after >> 2 the top four; the shifts by 1, 2, 4, 8, 16 cover 32 bits in five steps. All bits below the top are now 1, so v + 1 is a single bit above the original top bit — unless n was already a power of two, which the initial n - 1 handles.

Recognition

How to tell a problem wants this.

"Is n a power of two / four", "round up to a power of two", "align to 8 bytes".
Allocating a hash table or ring buffer whose size must be a power of two so that index & (size - 1) replaces index % size.
"Rightmost set bit", "lowest bit", Fenwick tree updates and queries.

“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

n — Integer between 1 and 128

= 40

1/9n = 40 (00101000). A power of two has exactly one set bit; several O(1) tricks follow from that shape.

Bits being examinedBits set by the operationBits cleared by the operation

PseudocodeLearn Power-of-Two Tricks →

1isPow2 = n > 0 and (n & (n - 1)) == 0
2lowest = n & -n
3p = n - 1
4p |= p >> 1; p |= p >> 2; p |= p >> 4   # smear the top bit down
5nextPow2 = p + 1

Variables

n40

Complexity

best O(1)

avg O(1)

worst O(1)

space O(1)

Speed

Pseudocode

1is_pow2(n)    = n > 0 and (n & (n - 1)) == 0
2lowest_bit(n) = n & -n
3highest_bit(n): p = 1; while p * 2 <= n: p *= 2; return p
4next_pow2(n):
5  v = n - 1
6  v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16
7  return v + 1

Implementations

11 · Power-of-two test
2def is_power_of_two(n: int) -> bool:
3    return n > 0 and (n & (n - 1)) == 0
4 
5 
62 · Lowest and highest set bit
7def lowest_set_bit(n: int) -> int:
8    return n & -n
9 
10 
11def highest_set_bit(n: int) -> int:
12    return 1 << (n.bit_length() - 1) if n > 0 else 0
13 
14 
153 · Next power of two
16def next_power_of_two(n: int) -> int:
17    """Smallest power of two >= n. bit_length works for any width."""
18    return 1 if n <= 1 else 1 << (n - 1).bit_length()
19 
20 
21def next_power_of_two_smear(n: int) -> int:
22    """Same result via smearing, restricted to 32-bit inputs."""
23    v = n - 1
24    v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16
25    return v + 1
26 
27 
284 · Power of four and alignment
29def is_power_of_four(n: int) -> bool:
30    return is_power_of_two(n) and (n.bit_length() - 1) % 2 == 0
31 
32 
33def align_up(x: int, k: int) -> int:
34    m = (1 << k) - 1
35    return (x + m) & ~m
36 
37 
38if __name__ == "__main__":
39    assert is_power_of_two(64) and not is_power_of_two(12) and not is_power_of_two(0)
40    assert lowest_set_bit(12) == 4 and highest_set_bit(12) == 8
41    assert next_power_of_two(13) == next_power_of_two_smear(13) == 16
42    assert next_power_of_two(16) == 16
43    assert is_power_of_four(16) and not is_power_of_four(8)
44    assert align_up(13, 3) == 16

Walkthrough

n & (n - 1) == 0 with the n > 0 guard works for any width because Python ints are unbounded.
int.bit_length() replaces both clz and the smear: 1 << (bit_length - 1) is the highest set bit and 1 << (n - 1).bit_length() the next power of two.
The smear version is included for comparison; its five shifts cover exactly 32 bits.
is_power_of_four checks that the single set bit sits at an even index — simpler than a magic mask and width-independent.

Complexity (this implementation)

time O(1) · space O(1)

O(digits) for enormous ints.

Language notes

math.log2(n).is_integer() fails for large n due to float rounding; stick to bit tricks.
n.bit_length() is exact for every int, including negatives (uses abs).
Python 3.11+ has no bit_ceil; 1 << (n - 1).bit_length() is the one-liner.

Common mistakes in this language

Using floating-point log2 for exact tests.
Applying the 32-bit smear to a number wider than 32 bits and getting a wrong result.
Omitting the n > 0 guard.

Language differences that matter here

Highest set bit: C++20 std::bit_floor / std::bit_width (or __builtin_clz, UB for 0); JS/TS Math.clz32 (32-bit only); Python int.bit_length() for any width.
Next power of two: C++ std::bit_ceil (UB if the result overflows the type); JS must use 2 ** k because 1 << 31 is negative; Python 1 << (n - 1).bit_length() never overflows.
Range of n & (n - 1): C++ per type width; JS/TS 31 bits then BigInt; Python unbounded.
Float log2 tests are unreliable in all four languages for large values; the bit tricks are exact everywhere.

Complexity

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(1)

Smearing costs a fixed log2(w) steps; clz/ctz-based versions are a single instruction.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Validating or computing power-of-two sizes for hash tables, ring buffers, segment trees (Segment Tree pads to the next power of two).
Replacing % and / by & and >> in hot loops where the divisor is a known power of two.
Fenwick tree traversal and iterating set bits via n & -n.

Avoid it when

When the divisor is not a power of two — the mask trick is simply wrong, not slow.
When n may be negative or zero and the code does not guard: 0 & -1 == 0 would wrongly report 0 as a power of two.
In JavaScript for values ≥ 2^31 — use BigInt or Math.log2 on floats.

Alternatives

Count Set Bits (Popcount)Set, Clear, Toggle & Test a Bit

Common mistakes

Omitting the n > 0 guard in is_power_of_two.
Skipping the initial n - 1 in next-power-of-two, which returns 2n when n is already a power of two.
Missing the v |= v >> 32 step for 64-bit values (or including it on 32-bit where it is harmless but misleading).
Signed overflow: nextPowerOfTwo(2^30 + 1) in 32-bit signed arithmetic wraps to a negative number.

Interview patterns

Power of Two / Power of Four in O(1) without loops.
Fenwick tree update/query loops driven by i & -i.
Bit reversal and "reverse bits" using masks of alternating patterns (0x55555555, 0x33333333, 0x0F0F0F0F).
Find the single set bit of a ^ b to partition two "single numbers" — see XOR Patterns.

Example problems

Single Numbereasy Counting Bitseasy Bit Counting Trickseasy