A 32-bit integer is an array of 32 booleans you can operate on all at once. AND, OR, XOR, and the shifts let you inspect, set, clear, and move those bits in a single instruction, and the whole category of “bit” problems is really a small set of identities: you either recognize the one a problem wants or you fall back to looping over the bits by hand. There’s no framework to learn here, just a few tricks worth having in memory — so this hub is organized around the three that unlock almost all of them.
XOR remembers what has no partner
XOR has two properties that together do something magic: a ^ a == 0 and a ^ 0 == a. Fold XOR across a list and every value that appears an even number of times cancels itself to zero, leaving the XOR of whatever occurs an odd number of times. Single Number guarantees exactly one such value, so that leftover XOR is precisely the lone element — the whole array folded into one number, in space where a hash set would cost . Missing Number is the same idea with a twist: XOR together every value in the full range 0..n and every value present in the array, and each number that’s there cancels its counterpart, leaving the one that’s missing.
Stripping the lowest set bit
The expression n & (n - 1) clears the rightmost 1 bit of n — subtracting one flips that bit and everything below it, and the AND keeps only what stayed the same. That single identity powers Number of 1 Bits: loop n &= n - 1 and count the iterations, and you touch the loop exactly once per set bit rather than all 32. Counting Bits scales it to a range with a one-line recurrence — dp[i] = dp[i >> 1] + (i & 1), reusing the bit count of i halved and adding back the bit you shifted off. It’s a dynamic-programming recurrence hiding in a bitwise problem.
Rebuilding an operation by hand
Sum of Two Integers asks you to add without +, which forces you to rebuild what an adder does in hardware. XOR is addition with the carries ignored (1 ^ 1 == 0), and (a & b) << 1 is exactly those carries shifted into place; loop — add the carry-less sum, recompute the carry — until there’s no carry left, and you’ve reimplemented +. Reverse Bits shifts bits out of one end and into the other 32 times, and Reverse Integer does the decimal version while checking for overflow before it happens, since the reversed value can exceed the int range the original fit in.
The signed-int trap in Java
One language detail runs through several of these: a Java int is signed, and the ordinary right shift >> sign-extends — it copies the top bit down instead of feeding in zeros. Number of 1 Bits and Reverse Bits treat their input as an unsigned 32-bit pattern, so reach for the unsigned shift >>> whenever a loop’s termination depends on shifting the value down to zero — use >> there on a negative number and the sign bit floods it with ones and the loop never ends. (A fixed 32-iteration loop, or the n & (n - 1) count that uses no shift at all, sidesteps the trap; it only bites the shift-until-zero style.) It’s the kind of bug that passes every positive test case and dies on the one with the high bit set.
The tell, and the fallback
These problems announce themselves: constraints that mention “constant space,” inputs where every element but one appears twice, or an explicit ban on + or extra memory. When you spot the identity — XOR cancellation, the n & (n-1) strip, the carry loop — the solution is two lines. When you don’t, the honest fallback for the per-bit problems is always there: loop over all 32 bit positions and check each with (n >> i) & 1. Slower and less clever, but it can’t go wrong — the exception is Reverse Integer, which is decimal digits and overflow rather than bits at all, so it needs its own handling.
Where a bit is the right unit
Outside these puzzles, bits are how you pack many yes/no facts into one small number. Unix file permissions are three bits per class — the 7 in chmod 755 is rwx as a bitmask; feature flags get packed into a single integer and tested with an AND; a subnet mask is AND-ed against an IP address to extract its network portion; a Bloom filter sets bits chosen by hash to answer “probably present.” In application code I reach for a Set or a boolean[] over bit tricks most of the time because they read far more clearly — the exceptions are tight inner loops and flag-packing, where the bit genuinely is the natural unit and the density pays for the loss of readability.
Recognize or brute-force
There’s no unifying structure to internalize here, only a short vocabulary: XOR erases pairs, n & (n - 1) peels off one set bit, XOR-plus-shifted-carry is addition. Learn those three and most of the seven collapse to a couple of lines; miss them and, for the bit-level ones, the 32-position loop still gets you there. It’s the one category where “do you happen to know the identity” matters more than any reasoning you can derive at the whiteboard.
References
- NeetCode 150 — Bit Manipulation — the seven problems and the tricks behind them.
