Bit manipulation playground
mediumx & (x−1) clears the lowest set bit; x & −x isolates it. Between them they give you popcount, power-of-two tests and subset enumeration, all in single instructions.
O(1) per operationSpace O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How bit manipulation playground works
An integer is 16 switches in a row, and five operators - AND, OR, XOR, NOT and shifts - flip them in bulk. Combined with a mask like 1 << i they give surgical control: x | (1 << i) forces bit i on, x & ~(1 << i) forces it off, x ^ (1 << i) flips it. Each is a single CPU instruction.
Two identities do most of the interesting work. x & (x-1) clears the lowest set bit: subtracting 1 borrows through the trailing zeros, so the AND wipes that bit and everything below it. x & -x isolates it instead - in two's complement, -x is ~x + 1, and the carry leaves exactly one bit that both values share.
From those two, useful tools fall out for free. A power of two has exactly one set bit, so x > 0 and x & (x-1) == 0 is the whole test. Brian Kernighan's popcount strips the lowest bit until zero, looping once per set bit - 3 iterations for 44, not 16.
Step by step
- Start with x = 44, which is 101100 in binary - three set bits, at positions 2, 3 and 5.
- x & -x: negating flips every bit above the lowest 1, so the AND leaves only bit 2 standing. Result: 4.
- x & (x-1): 43 is 101011, the subtraction having borrowed through the trailing zeros. 44 & 43 = 101000, which is 40 - the lowest set bit is gone.
- Kernighan's popcount repeats that strip until zero: 44 → 40 → 32 → 0. Three iterations for three set bits, against 16 for a bit-by-bit loop.
- The power-of-two test rides the same identity: 44 & 43 is 40, nonzero, so 44 fails; 32 & 31 is 0, so 32 passes.
- Shifts scale the whole word: x << 1 doubles 44 to 88, and x >> 1 halves it to 22 by discarding the low bit.
Complexity
| Worst case time | O(1) per operation |
|---|---|
| Space | O(1) |
Reference implementation
Python
def get_bit(x, i): return (x >> i) & 1
def set_bit(x, i): return x | (1 << i)
def clear_bit(x, i): return x & ~(1 << i)
def toggle_bit(x, i): return x ^ (1 << i)
def lowest_set_bit(x): return x & -x # isolates it
def clear_lowest(x): return x & (x - 1) # removes it
def is_power_of_two(x): return x > 0 and (x & (x - 1)) == 0
def popcount(x):
"""Brian Kernighan: loops once per set bit, not once per bit."""
n = 0
while x:
x &= x - 1
n += 1
return nJavaScript
const getBit = (x, i) => (x >> i) & 1;
const setBit = (x, i) => x | (1 << i);
const clearBit = (x, i) => x & ~(1 << i);
const toggleBit = (x, i) => x ^ (1 << i);
const lowestSetBit = (x) => x & -x;
const clearLowest = (x) => x & (x - 1);
const isPowerOfTwo = (x) => x > 0 && (x & (x - 1)) === 0;
function popcount(x) { // Brian Kernighan
let n = 0;
while (x) { x &= x - 1; n++; }
return n;
}Worth noticing
`x & (x - 1)` clears the lowest set bit
Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1. ANDing keeps only the bits above, so the lowest 1 vanishes. Watch the bit strip during 'clear lowest' - this one identity powers popcount, power-of-two tests and subset enumeration.
`x & -x` isolates it instead
In two's complement, −x is ~x + 1, which makes every bit above the lowest 1 the opposite of x. The AND therefore leaves exactly that one bit standing - the trick behind Fenwick trees.
A power of two has exactly one bit set
So clearing its lowest set bit leaves zero. That is the entire `x && !(x & (x-1))` test - constant time, no loop, no division.
Bitmasks are sets
A 32-bit integer is a subset of {0..31}: union is OR, intersection is AND, difference is AND-NOT, membership is a shift. This is what makes bitmask dynamic programming fast enough to be worth writing.
Common pitfalls
- Operator precedence. In C-family languages x & 1 == 0 parses as x & (1 == 0), because comparison binds tighter than AND. Parenthesise every bitwise subexpression.
- Calling 0 a power of two. x & (x-1) == 0 is true for zero, which has no set bits at all - the test needs the x > 0 guard in front.
- JavaScript's 32-bit trapdoor. Bitwise operators coerce numbers to signed 32-bit integers, so 1 << 31 comes out negative and values past 2³¹ silently corrupt. Reach for >>> or BigInt.
- Shifting too far. In C and C++, shifting a 32-bit int by 32 or more is undefined behaviour, not zero - the hardware may honour only the low five bits of the count.
- Mixing up the two right shifts. On negative numbers the arithmetic shift drags the sign bit along; use the unsigned variant when you mean to pull in zeros.
Where it is used
- Fenwick trees walk parent and sibling indices with x & -x - the identity is the data structure.
- Bitmask DP: a 20-element subset fits in one integer, so travelling-salesman states become array indices.
- Permission systems: Unix file modes and API scope flags pack booleans into one word, tested with a mask.
- Hash tables sized to powers of two replace the modulo with hash & (size - 1) - a single AND.
Frequently asked questions
What is the time complexity of bit manipulation operations?
O(1) per operation, with O(1) space - set, clear, toggle, shift and the x & (x-1) family each compile to a single instruction, whatever the value holds. The one loop here, Brian Kernighan's popcount, runs once per set bit: at most 16 rounds on this playground's 16-bit values, and only 3 for 44.
How does x & (x-1) clear the lowest set bit?
Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1 - the borrow ripples exactly that far and no further. ANDing with the original keeps only the untouched bits above. For 44: 101100 & 101011 = 101000, and bit 2 has vanished.
How do I check if a number is a power of two?
A power of two has exactly one set bit, so clearing its lowest set bit must leave zero: x > 0 and x & (x-1) == 0. Constant time, no loop, no division - 32 & 31 = 0 passes, while 44 & 43 = 40 fails.
Why does x & -x isolate the lowest set bit?
Two's complement defines -x as ~x + 1. The flip turns trailing zeros into ones, and adding 1 carries through them, stopping exactly at x's lowest set bit - so that position is 1 in both x and -x while every higher bit disagrees. Fenwick tree indexing is built on this.