· software-engineers Editorial · Career · 5 min read
Swe Interview Bit Manipulation Techniques
Essential bit manipulation techniques for 2026 SWE coding interviews, with patterns, complexity, and worked examples.
Swe Interview: Bit Manipulation Techniques
Bit manipulation questions test whether a candidate can reason at a lower level of abstraction than typical array/hashmap problems, and they remain a fixture of 2026 coding interview loops precisely because a handful of memorized-but-understood tricks solve a surprisingly large fraction of the problem space. This guide covers the core techniques, when to reach for them, and the complexity guarantees that make them attractive over naive approaches.
Core Bitwise Operators and What They’re Actually For
The five operators — AND (&), OR (|), XOR (^), NOT (~), and shifts (<<, >>) — each map to a specific class of problem.
AND (&) is used to check or clear specific bits. n & 1 checks if the lowest bit is set (odd/even check in O(1) versus a modulo operation). n & (n-1) clears the lowest set bit — this single trick underlies several classic problems.
OR (|) sets bits. n | (1 << k) sets the k-th bit.
XOR (^) is the most interview-relevant operator because of one property: x ^ x = 0 and x ^ 0 = x. This means XOR-ing a list of numbers where every element appears twice except one cancels all the pairs, leaving the unpaired element — solving “Single Number” in O(n) time and O(1) space, versus O(n) space for a hashmap-based approach.
Shifts (<<, >>) multiply/divide by powers of two and are used to construct or extract bitmasks, particularly in dynamic programming over subsets (bitmask DP).
Pattern 1: Counting Set Bits (Brian Kernighan’s Algorithm)
The naive approach to counting set bits in a number checks all 32 (or 64) bits one at a time — O(bits) per number. Brian Kernighan’s trick uses n & (n-1) to clear the lowest set bit on each iteration, so the loop runs exactly once per set bit rather than once per bit position — O(popcount(n)) instead of O(bit-width). This is the standard approach for “Number of 1 Bits” and the basis for the DP recurrence in “Counting Bits” (bits[i] = bits[i & (i-1)] + 1).
Pattern 2: Single Number Family (XOR Cancellation)
“Single Number” (every element appears twice except one — XOR all elements) is the base case. Variants raise the stakes: “Single Number II” (every element appears three times except one) requires tracking bit counts modulo 3 using two bitmasks (ones and twos) rather than simple XOR. “Single Number III” (exactly two elements appear once, rest appear twice) XORs everything to get a ^ b, then uses the lowest set bit of that result to partition all numbers into two groups, each containing exactly one of the two unique elements, and XORs within each group independently.
Pattern 3: Bitmask for Subset Representation
Any problem involving “consider all subsets of a set of size n” (where n is small, typically ≤ 20-24) can represent each subset as an integer from 0 to 2^n - 1, where bit i indicates whether element i is included. This underlies bitmask DP problems like the Traveling Salesman Problem on small graphs (dp[mask][i] = shortest path visiting exactly the set of cities in mask, ending at city i), and “assign tasks to workers” style problems where checking bit membership (mask & (1 << i)) and toggling it (mask ^ (1 << i)) replace slower set operations.
Pattern 4: Power of Two Checks
n > 0 && (n & (n-1)) == 0 checks if a number is a power of two in O(1) — a power of two has exactly one set bit, and clearing the lowest set bit of a number with exactly one set bit yields zero. This is a direct application of the same n & (n-1) trick from Kernighan’s algorithm, reused for a different purpose — recognizing this reuse is itself a signal of strong bit manipulation fluency in an interview.
Comparison Table: Approach Complexity
| Problem Type | Naive Approach | Bit Manipulation Approach | Complexity Gain |
|---|---|---|---|
| Find single non-duplicate (pairs) | Hashmap count | XOR all elements | O(n) space → O(1) space |
| Count set bits | Check every bit position | Kernighan’s n & (n-1) | O(32) → O(popcount) |
| Check power of two | Repeated division by 2 | n & (n-1) == 0 | O(log n) → O(1) |
| Subset enumeration (n≤24) | Recursive combinations | Bitmask integer (0 to 2^n-1) | Cleaner state, O(1) membership check |
| Swap two variables | Temp variable | XOR swap (a^=b; b^=a; a^=b) | No extra memory (rarely used in practice) |
FAQ
Q: How much bit manipulation do I actually need for 2026 SWE interviews?
A: Enough to recognize the four patterns above and explain the n & (n-1) trick fluently — most companies ask at most one bit manipulation question per loop, and it’s rarely the hardest question. The bigger risk is freezing on an unfamiliar-looking problem that’s secretly XOR cancellation in disguise, so pattern recognition matters more than memorizing dozens of tricks.
Q: Is the XOR swap trick actually used in production code?
A: Almost never — modern compilers optimize a temp-variable swap identically, and the XOR version is less readable and fails if a and b reference the same memory location. It’s asked purely to test understanding of XOR properties, not because anyone should write it in real code.
Q: What’s the fastest way to recognize a bitmask DP problem? A: Look for a small constraint (n ≤ ~20-24) combined with language like “all possible subsets,” “assignments,” or “visiting order” — that constraint size is a strong signal the intended state space is 2^n, which is only tractable as a bitmask integer rather than an explicit set data structure.
Bit manipulation is one of several pattern families that reward deliberate practice over blind repetition. The 0-to-1 SWE Interview Playbook (https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20) organizes these patterns systematically so you build recognition speed for bitmask, XOR, and counting problems before walking into a 2026 interview loop.