Bit Manipulation
Bit manipulation is working with numbers at the binary level using bitwise operations.
8-BIT · A = 12 · B = 10
AND
A
B
=
Column 1: 0 AND 0 = 0. AND needs both.
Next
Column 2: 0 AND 1 = 0. AND needs both.
Op
A
B
Intuition
Computers store data as bits (0s and 1s). Bit manipulation allows us to operate directly on these bits, which is extremely fast and efficient.
Concept
- AND (&): 1 if both bits are 1.
- OR (|): 1 if at least one bit is 1.
- XOR (^): 1 if bits are different.
- NOT (~): Inverts all bits (0→1, 1→0).
- Left Shift (<<): Shifts bits left, filling with 0. Equivalent to multiplying by 2^k.
- Right Shift (>>): Shifts bits right. Equivalent to dividing by 2^k and rounding down. For non-negative numbers that is ordinary integer division. For negative numbers it is not: integer / in Java, C and C++ rounds toward zero, so -7 >> 1 is -4 while -7 / 2 is -3. (In C, shifting a negative number right is implementation-defined; mainstream compilers give -4.)
How it Works
Common Tricks:
x & 1: Check if odd (1) or even (0).x & (x - 1): Clear the lowest set bit.x ^ x = 0: XORing a number with itself is 0.x << 1: Multiply by 2.
Step-by-Step Breakdown
Watch the visualization:
- See how each bit column is processed independently (except shifts).
- Observe how shifts move the entire pattern left or right.
Trace: counting the set bits of 156
x = 156
10011100 in binary. Four bits are set, so the loop below will run four times rather than the eight a bit-by-bit scan would need.
count 0
x - 1 = 155
10011011. Subtracting 1 clears the lowest set bit, bit 2, and sets every bit below it — that is what a borrow does.
borrow
x &= x - 1
10011100 & 10011011 = 10011000. The AND keeps only the bits both values have, so the bits above are untouched, the bits the borrow set are dropped, and the lowest set bit is gone. x is now 152.
count 1
x = 152
10011000 & 10010111 = 10010000, clearing bit 3. x is now 144.
count 2
x = 144
10010000 & 10001111 = 10000000, clearing bit 4. x is now 128.
count 3
x = 128
10000000 & 01111111 = 0. The last set bit goes and the loop condition fails.
count 4
result
Four iterations for four set bits. On a 64-bit word holding a single bit, this does one iteration where a shift-and-test loop does 64.
4
same trick
x & (x - 1) == 0 is the power-of-two test, because clearing the only set bit leaves zero. It reports true for x = 0 as well, so a non-zero check goes with it.
x > 0 && !(x & (x - 1))
When to Use
- Optimizing space (flags, bitmasks).
- Low-level system programming.
- Competitive programming (subset generation, DP optimization).
When NOT to Use
- High-level logic where readability is more important than micro-optimization.
- Floating point arithmetic (unless you know IEEE 754 well).
How to Identify
"Single Number", "Number of 1 bits", "Power of two", "Subsets".
Applying for software engineering roles? Free, no sign-up: