← Learn DSA · Lesson 11 of 11
Bit Manipulation
When the state is small enough to be a number, arithmetic replaces the data structure.
The idea
Bit manipulation is worth learning for one reason: it turns a whole set into a single integer. Thirty-two booleans become one number you can compare, hash, store in an array index, and pass around for free.
The operations that carry most of the weight:
x & 1 is x odd
x >> 1 halve it
x & (1 << i) is bit i set
x | (1 << i) set bit i
x & ~(1 << i) clear bit i
x ^ (1 << i) flip bit iAnd three identities that solve entire problems on their own:
x & (x - 1) clears the lowest set bit. Loop on it and you count set bits
in as many steps as there are ones, not as there are bits. It is also the test
for a power of two: exactly one bit set means x & (x - 1) is zero.
XOR cancels. a ^ a = 0 and a ^ 0 = a, so XOR-ing everything in an
array where each value appears twice except one leaves exactly that one — in
O(n) time and O(1) space, with no hash map.
A subset is a number. Iterating mask from 0 to 2^n - 1 enumerates
every subset of n items, and mask & (1 << i) asks whether item i is in this
one. That is the basis of bitmask dynamic programming.
The trap is language semantics. JavaScript's bitwise operators coerce to 32-bit
signed integers, so they silently break above 2³¹. Python's integers are
arbitrary precision and its >> on negatives is an arithmetic shift with no
32-bit wrap at all. The same expression genuinely differs between the two.
Walkthrough
Each value is replaced by its number of set bits. The inner loop runs once per one-bit, not once per bit — 8 finishes in a single step where a naive shift would take four.
What it costs
- time
- O(1) per operation; O(set bits) for the clear-lowest-bit loop
- space
- O(1) — a set of up to 32 or 64 members costs one integer
Subset enumeration is O(2^n) by definition, and bitmask DP is O(2^n · n). Those are only tractable because n is small — around 20 — which the constraints will tell you.
When to reach for it
- A set of at most ~32 or 64 items, where the whole set needs to be one comparable value.
- Bitmask DP over subsets, which the constraints signal by keeping n around 20.
- The classic XOR problems: find the single unpaired value, or the missing number.
- Flags and permissions, where combining and testing sets should be one instruction.
Rather than the obvious alternative
A hash set
Clearer and unbounded, and the right default. A bitmask wins when the universe is small and fixed and you need the set itself to be a value — a key, an array index, a DP state.
An array of booleans
Easier to read and usually fast enough. The bitmask is worth it when you need union, intersection or difference of whole sets in a single operation.
Arithmetic
Sum-based tricks for "find the missing number" are simpler to explain but overflow on large inputs. XOR has no such failure mode.
How to spot it
- Constraints cap n around 20 — that is an explicit invitation to enumerate subsets.
- The problem is about subsets, masks, flags, or "every combination".
- Values appear in pairs except one, which is XOR.
- The words "without extra space" alongside a counting problem.
Where it goes wrong
Operator precedence
`&` and `|` bind more loosely than `==` in most C-family languages, so `x & 1 == 0` parses as `x & (1 == 0)`. Parenthesise everything.
Assuming 32-bit behaviour in Python
Python integers do not wrap and `>>` on a negative is an arithmetic shift forever. Masking with `& 0xFFFFFFFF` is how you get JavaScript-like behaviour when a problem assumes it.
Shifting past the width
`1 << 32` is 1 in JavaScript, not 4294967296 — the shift count wraps at 32. Above that you need BigInt.
Signed right shift on negatives
`>>` preserves the sign bit and `>>>` does not. For bit counting on possibly-negative values, the difference is an infinite loop.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Return how many 1 bits n has. Use n & (n - 1) rather than checking each bit.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| countBits(7) | seven is three bits | 3 | — |
| countBits(8) | power of two | 1 | — |
| countBits(0) | zero | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Practise it
- Single Numbereasy