XOR tricks, masks, and shifts that turn set logic into constant-time integer operations.
What bit manipulation is
Treating integers as arrays of bits and operating on all 32 or 64 lanes at once with AND, OR, XOR, NOT, and shifts. The wins are constant-time set operations, O(1) space where hash sets would grow, and occasionally being the only tool allowed ('without using +').
Two identities carry most interview problems. XOR: x ^ x = 0 and x ^ 0 = x, with commutativity - so XOR-ing a whole array cancels every pair and leaves the odd one out. And n & (n-1): it clears the lowest set bit, because subtracting 1 flips that bit and everything below it.
How to recognize it
Explicit signals: 'without extra memory' on duplicate/missing-number problems, 'count set bits', 'power of two', 'implement arithmetic without operators'. Implicit ones: any set over a universe of at most ~30 elements can be a bitmask integer - subsets become numbers 0 to 2^n - 1, membership becomes AND, insertion becomes OR.
Bitmasking also appears as a supporting technique inside other patterns: DP over subsets keyed by mask, and visited-state encoding in BFS over configurations. Recognizing 'this set fits in an int' is the door.
The core toolkit
Read, set, clear, toggle bit i; extract the lowest set bit; strip it. These six one-liners are the entire vocabulary - everything else is composition.
pseudocode
read bit i: (x >> i) & 1
set bit i: x | (1 << i)
clear bit i: x & ~(1 << i)
toggle bit i: x ^ (1 << i)
lowest set bit: x & (-x)
strip lowest bit: x & (x - 1)
power of two test: x > 0 and (x & (x - 1)) == 0
XOR as pair-cancellation
Because XOR is associative, commutative, self-inverse, and has identity 0, XOR-ing any multiset cancels everything appearing an even number of times. Single-number problems, missing-number (XOR indices against values), and 'two numbers appear once' (XOR all, then split by any set bit of the result) are all this one algebra fact, applied with increasing craft.
Common pitfalls
Operator precedence: in C-family languages, == binds tighter than &, so parenthesize (x & 1) == 0 or suffer.
Signed shifts: right-shifting negative numbers is arithmetic (sign-extending) in most languages - loops 'until x is 0' never end. Use unsigned shifts (Java >>>) or bound the loop at 32.
Languages with unbounded ints (Python): ~ and negative masks behave differently; simulate 32-bit with explicit & 0xFFFFFFFF when porting.
Off-by-one on masks: n low bits set is (1 << n) - 1, not 1 << n.
Reaching for bit tricks when a readable arithmetic solution is equally fast - cleverness that costs clarity without buying complexity is a negative signal.
Worked examples
1. Single numbereasy
Every element of the array appears twice except one. Find it using O(1) extra memory.
The hash-set solution costs O(n) space, and the constraint forbids it - the cue for XOR.
XOR the entire array: pairs cancel (x ^ x = 0), the identity does nothing (0 ^ x = x), and order is irrelevant by commutativity.
The running result after one pass IS the unique element.
O(n) time, O(1) space, no branches. State the three algebra facts as your correctness argument - that is the interview answer.
pseudocode
result = 0
for x in nums:
result ^= x
return result
Remember: XOR is pair-annihilation: fold the array once and everything even-count vanishes, leaving the singleton.
2. Counting bits (0..n)easy
Return an array where ans[i] is the number of 1-bits in i, for every i from 0 to n, in O(n) total.
Counting each number independently costs O(n log n). The O(n) version reuses previous answers - a DP whose transition is a bit trick.
Key identity: i & (i - 1) strips i's lowest set bit, so it has exactly one fewer 1 than i.
Hence ans[i] = ans[i & (i - 1)] + 1, with base ans[0] = 0 - each entry is one array lookup plus one increment.
Alternative transition worth naming: ans[i] = ans[i >> 1] + (i & 1). Both are O(n); knowing two shows fluency rather than memorization.
pseudocode
ans = [0] * (n + 1)
for i in 1 .. n:
ans[i] = ans[i & (i - 1)] + 1
return ans
Remember: n & (n-1) removes exactly one set bit - which turns popcount-for-a-range into a one-line DP over smaller numbers.
3. Missing numbereasy
An array holds n distinct numbers from the range [0, n]. Find the one missing, without extra space.
Two O(1)-space routes exist; know both. Sum: expected total n(n+1)/2 minus actual sum - clean, but mind overflow in fixed-width languages.
XOR: fold together all indices 0..n and all array values. Every present number appears twice (once as index, once as value) and cancels.
What survives the cancellation is exactly the missing number - no overflow concerns at all.
Both are one pass. Offering the pair and the overflow trade-off is the strong answer.
pseudocode
result = n # start with the extra index n
for i in 0 .. n-1:
result ^= i ^ nums[i]
return result
Remember: Pair indices with values via XOR and everything present self-cancels - the missing value is the only unpaired survivor.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What does n & (n - 1) compute, and what is its most famous consequence?
It halves n; used for binary search
✓ It clears the lowest set bit; a positive n is a power of two exactly when the result is 0
It sets the lowest zero bit; used in masks
It negates n in two's complement
Subtracting 1 flips the lowest set bit and all bits below it; AND-ing erases them. Powers of two have exactly one set bit, so clearing it leaves zero - the classic O(1) test (guard n > 0).
2Which properties of XOR make the single-number trick correct?
It is idempotent and monotonic
✓ Self-inverse (x^x=0), identity 0, and commutativity/associativity - so any even-count element cancels regardless of order
It distributes over addition
It preserves sign
Commutativity lets you mentally reorder the fold so pairs sit adjacent; self-inverse annihilates them; identity keeps the lone survivor intact. All three are needed for the one-liner to be a proof.
3How do you produce a mask with the lowest n bits set?
1 << n
✓ (1 << n) - 1
~(1 << n)
n | (n - 1)
1 << n is a single bit at position n; subtracting 1 turns it into n ones below that position. Confusing the two is the standard mask off-by-one.
4Why can 'shift right until zero' loop forever on negative inputs in Java or C?
Negative numbers cannot be shifted
✓ The arithmetic right shift sign-extends, refilling the top bit with 1s so the value never reaches zero
The loop counter overflows
Compilers optimize the loop away
Signed >> preserves the sign bit, so -1 >> 1 is still -1. Use the unsigned shift (>>> in Java) or iterate a fixed 32 times - and mention it before the interviewer does.
Frequently asked questions
When should I represent a set as a bitmask?
When the universe has at most ~30-60 elements and you need fast membership, union, intersection, or enumeration of subsets - subset-DP and state-space BFS being the classic hosts. Beyond word size, use real sets.
Are bit tricks actually expected in interviews?
A small canon is: the XOR cancellation family, n & (n-1), masks and shifts, and power-of-two testing. Exotic tricks (bit reversal by magic constants, etc.) impress no one if fumbled; the canon plus clear explanations is the winning combination.
How do I keep bit code readable?
Name the masks (VISITED = 1 << 3), parenthesize every mixed-operator expression, and add a one-line comment stating the identity used ('clears lowest set bit'). Bit code without comments reads as noise even to its author a week later.