Bit manipulation questions look intimidating but they cluster around five patterns: XOR cancellation, bit counting and toggling, masking to test or set individual bits, bitmask subset enumeration, and constructing a number bit by bit. If you can recognize these five and you have the core operations memorized cold, you can solve the vast majority of what interviewers throw at you. This article walks through each pattern with concrete problems from our question bank so you know exactly what to drill.
We run mock interviews all day, and the single biggest failure mode we see on bit problems is not the algorithm. It is candidates fumbling the basic operators under pressure: forgetting that x & (x - 1) clears the lowest set bit, or blanking on how to check whether bit i is set. Get the primitives automatic first, then learn the patterns.
The core operations to have memorized
Before any pattern, these need to be reflexive. If you have to derive them at the whiteboard you have already lost time.
| Goal | Expression |
|---|---|
Check if bit i is set | (x >> i) & 1 |
Set bit i | x | (1 << i) |
Clear bit i | x & ~(1 << i) |
Toggle bit i | x ^ (1 << i) |
| Isolate lowest set bit | x & (-x) |
| Clear lowest set bit | x & (x - 1) |
| Test if power of two | x > 0 && (x & (x - 1)) == 0 |
The two workhorses are x & (x - 1) and x & (-x). The first shows up everywhere because subtracting one flips every bit from the lowest set bit down, so ANDing with the original erases exactly that bit. That single fact powers set-bit counting, power-of-two checks, and subset tricks.
Also memorize the XOR identities, because a whole pattern rests on them: a ^ a = 0, a ^ 0 = a, and XOR is commutative and associative. That means order does not matter and any value XORed an even number of times cancels out.
Pattern 1: XOR cancellation
This is the highest-value pattern to know because it turns O(n) space solutions into O(1) and O(n log n) into O(n). The idea: XOR the whole collection together and let duplicates or matching pairs cancel, leaving only the answer.
Set Mismatch (junior) is the cleanest entry point. You have the numbers 1 to n, but one got duplicated and replaced another, so one value appears twice and one is missing. You can solve it with a frequency count, but the elegant approach XORs all array elements with all of 1..n; the missing and duplicate values survive, and you separate them using the lowest set bit of that combined XOR. It is a great problem to practice because the naive hash-set solution and the XOR solution are both worth being able to explain.
Count Triplets That Can Form Two Arrays of Equal XOR (mid_senior) is the pattern dressed up. You need indices i < j <= k where the XOR of arr[i..j-1] equals the XOR of arr[j..k]. The insight: if those two segments have equal XOR, then the XOR of the whole range arr[i..k] is zero. So you are really counting subarrays with XOR zero, which reduces to a prefix-XOR argument. If prefix-XOR at i equals prefix-XOR at k+1, every split point between them works. This is where XOR meets the prefix sum mindset, and interviewers love that crossover.
Minimum Number of Operations to Make Array XOR Equal to K (mid_senior) is the one-liner of the group once you see it. You can flip any single bit of any element any number of times, and you want the total XOR of the array to equal k. XOR everything together, XOR with k, and the answer is simply the number of set bits in the result, because each differing bit costs exactly one flip. Recognizing that the answer is a popcount is the whole problem.
Pattern 2: Counting and toggling bits
Counting set bits (the "Hamming weight") is a standalone skill and a subroutine inside larger problems. Interviewers will ask you to count them and then ask you to do it better than looping 32 times.
The upgrade is Brian Kernighan's algorithm. Identify the lowest set bit using the expression n & (n - 1), which clears the least significant set bit of n, then repeat until the number becomes zero and count the iterations. The number of iterations required equals the number of set bits in the integer, rather than the total number of bits, so a number with three ones loops three times instead of thirty-two.
Binary Watch (junior) is a friendly application. The watch has 4 LEDs for hours (0-11) and 6 for minutes (0-59), and given a number of lit LEDs you enumerate every valid time whose total set-bit count matches. The clean solution just iterates all 12 * 60 times and keeps those where popcount(hour) + popcount(minute) equals the target. It rewards knowing your built-in bit-count function and reasoning about small search spaces.
When you need the set-bit count for every integer from 0 to n, there is a linear DP worth memorizing. Since i & (i - 1) has exactly one fewer 1-bit than i, the recurrence is ans[i] = ans[i & (i - 1)] + 1. That connects bit counting to dynamic programming, and it is a common follow-up after the naive count.
Range Product Queries of Powers (mid_senior) lives here too. You decompose n into its minimum set of powers of two, which is literally reading off its set bits, then answer product-over-range queries on that sorted list. The first step is pure bit extraction: walk the bits of n, and each set bit at position i contributes 2^i.
Pattern 3: Bitmask subset enumeration
When the input is small (roughly n <= 20), you can iterate over every subset by counting an integer from 0 to 2^n - 1 and treating each bit as "include this element or not." This is the bridge from bit manipulation to brute-force combinatorics.
Split Array With Same Average (staff) is a hard problem where this thinking helps. You partition nums into two non-empty groups with equal average. A key reduction is that a subset of size k works only if its sum equals total * k / n, and for small halves you enumerate subsets with bitmasks (often meet-in-the-middle to keep it tractable). It is not a pure bit problem, but the enumeration machinery is bitmask-driven, and being fluent with "loop mask from 1 to (1<<n)-1, test bit j with mask & (1<<j)" is what makes it writable in an interview.
The idiom to know for iterating submasks of a mask is for (sub = mask; sub; sub = (sub - 1) & mask). It is worth memorizing because it appears in bitmask DP problems that senior and staff loops reach for.
Pattern 4: Constructing a number from bits
Some problems ask you to build a target value by choosing bits directly, usually with a greedy or per-bit argument.
Maximum Possible Number by Binary Concatenation (mid_senior) gives you three integers and asks for the largest number formed by concatenating their binary representations in some order. With only three elements you can try all six permutations, shifting each accumulator left by the bit-length of the next number and ORing it in. The trick is computing each value's bit length correctly and handling the shift, which is exactly the primitive work from the first section.
Construct the Minimum Bitwise Array II (mid_senior) asks, for each prime p, for the smallest ans[i] such that ans[i] | (ans[i] + 1) == p. This is a per-bit construction: you reason about where the lowest zero bit of p must sit and clear the appropriate bit to get the minimum. It is a good test of whether you actually understand what OR with x + 1 does to the bit pattern, rather than pattern-matching a memorized template.
What to actually practice
Our advice from watching these interviews: do not rabbit-hole on exotic bit hacks. Interviewers reuse the same handful of ideas. Spend your time until XOR cancellation, x & (x - 1), and mask testing are automatic, then do two or three problems per pattern above. The Set Mismatch to Count Triplets progression teaches XOR reasoning better than any single problem. You can drill the full set on the Bit Manipulation track and get feedback on how you explain the tricks, which matters as much as landing them, in a mock interview.
One more thing we see constantly: candidates solve the bit problem silently and then cannot explain why x & (x - 1) works. Interviewers ask. Have the one-sentence justification ready for every trick you use.
FAQ
How common are bit manipulation questions in interviews?
They are less frequent than arrays or trees but show up regularly at companies that value low-level fluency, and they appear often as follow-up twists ("now do it in O(1) space"). Because they are lower frequency, many candidates skip them, which makes them a cheap way to stand out when one does appear.
What is the single most important trick to know?
XOR cancellation. The identities a ^ a = 0 and a ^ 0 = a let you find missing or duplicated values in O(1) extra space, and they underpin at least three of the problems above. Learn it first.
Do I need to memorize Brian Kernighan's algorithm?
Yes, or at least be able to derive it on the spot. It is the standard "better than looping 32 bits" answer for counting set bits, and interviewers frequently ask for the optimization after you give the naive loop. Knowing x & (x - 1) clears the lowest set bit gets you there.
How do I know when a problem wants bitmasks?
Look at the constraints. When n is small (around 20 or fewer) and the problem involves subsets, partitions, or "try every combination," bitmask enumeration over 0 to 2^n - 1 is usually the intended tool. Large n rules it out because 2^n explodes.