What it is
Bit manipulation problems ask you to compute something about the binary representation of an integer, or to use bitwise operators (&, |, ^, shifts) to simulate arithmetic or cancel out values, in place of an operator or loop you'd normally reach for. The technique rests on a handful of reusable identities — XOR cancels equal values and is its own inverse, n & (n - 1) clears the lowest set bit, subtracting one flips a specific run of bits — each of which turns an operation that looks like it needs a full scan into a constant number of word-level operations. The hard part is rarely the operator itself; it's recognizing which identity matches the structure of the problem, and handling the fact that most languages (Python especially) don't naturally bound integers to a fixed width the way real hardware does.
When it applies
- Values pair up or cancel in a way that XOR captures cleanly — everything appears twice except one value, or you need a difference-detecting operation that's commutative and self-cancelling.
- You need to count, clear, or manipulate individual set bits, and a per-bit-position loop would be correct but slower than necessary —
n & (n - 1)and its relatives turn an O(32) or O(bits) loop into work proportional to the number of set bits. - You're asked to simulate an operator (addition, subtraction) using only bitwise primitives, which is really asking you to describe how a hardware adder works: XOR for the sum without carry, AND-then-shift for the carry to propagate.
- It does not apply as a first resort when a hash set or count map already solves the problem within the stated space budget — bit tricks are usually the answer to "now do it in O(1) space," not the natural starting point; reach for them once a space or performance constraint rules out the obvious structure.
Tells in the problem
- "Every element appears twice (or three times) except one; find the singleton" — XOR accumulation for pairs, a per-bit count mod 3 for triples.
- "Count the number of set bits" or "for every number up to n, count its set bits" —
n & (n - 1)clears the lowest bit in one step; the "every number up to n" version becomes a DP that reuses a smaller already-computed index. - "Without using
+or-" — you're being asked to simulate an adder: XOR for the sum-without-carry, AND-shifted-left for the carry, repeated until no carry remains. - "Reverse the bits of a 32-bit integer" or any fixed-width bit-order operation — a byte/nibble/pair swap by divide-and-conquer beats a 32-iteration loop once "make it fast" is asked.
- Explicit mention of a fixed bit width (32-bit, unsigned) alongside a language (Python) that doesn't naturally enforce one — that combination is a direct hint that masking to that width is part of the expected solution, not an afterthought.
The classic mistake
The recurring bug is writing bit-manipulation code as if the language enforces a fixed word width when it doesn't — in Python, a loop that shifts a value right until it becomes zero never terminates on a value that's meant to represent a negative number in two's complement, because Python integers have no top bit to run out of. The fix is to explicitly mask every intermediate value to the stated width (& 0xFFFFFFFF) and reinterpret the final pattern as signed only at the end, rather than assuming the arithmetic "just works" the way it would in C or Java. A second common mistake is reaching for a bit trick that only works for the case shown in the prompt — treating a "cancel in pairs" XOR solution as if it generalizes to "cancel in triples" without changing the accumulator, when the triples case actually needs a per-bit count mod 3, not XOR at all.
Questions to start with
- Single Number — the foundational XOR-cancellation identity, plus the standard escalation to two singletons and to triples where XOR alone stops working.
- Number of 1 Bits — the
n & (n - 1)identity in its simplest form, isolating exactly one set bit per iteration. - Counting Bits — the same identity reused as a DP recurrence, referencing a smaller already-computed index instead of recomputing from scratch.
- Reverse Bits — fixed-width thinking made explicit: a 32-iteration loop versus a divide-and-conquer swap, and why the iteration count can't depend on the input's value.
- Sum of Two Integers — simulating a hardware adder with XOR and AND, and the Python-specific masking needed because the language has no fixed width of its own.