BitsBit Manipulation
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.
n
0
7
0
6
1
5
0
4
1
3
0
2
0
1
0
0
= 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)) == 02lowest = n & -n3p = n - 14p |= p >> 1; p |= p >> 2; p |= p >> 4 # smear the top bit down5nextPow2 = p + 1Variables
n40
Complexity
best O(1)
avg O(1)
worst O(1)
space O(1)
Speed