Bit manipulation questions test your understanding of how data is represented at the binary level. These problems appear less frequently than arrays or trees but are considered “hard” by many candidates because the techniques are less intuitive. The good news: a handful of patterns cover 90% of bit manipulation interview questions. This guide covers the essential bitwise operations, XOR tricks, and bitmask patterns for coding interviews.
Essential Bitwise Operations
Six operators: AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>). Key properties: (1) x & 1 extracts the last bit (0 or 1). (2) x & (x-1) removes the lowest set bit. For x=12 (1100), x-1=11 (1011), x & (x-1) = 8 (1000). This is the basis for counting bits and checking powers of two. (3) x | (1 << k) sets bit k to 1. (4) x & ~(1 << k) clears bit k to 0. (5) x ^ (1 << k) toggles bit k. (6) x << k multiplies x by 2^k. x >> k divides x by 2^k (integer division). (7) x ^ x = 0 (any number XORed with itself is 0). (8) x ^ 0 = x (any number XORed with 0 is itself). These properties are the building blocks for all bit manipulation tricks.
XOR Tricks
XOR is the most useful bitwise operator for interviews because of its unique properties: a ^ a = 0 (cancellation) and a ^ 0 = a (identity). Single Number: given an array where every element appears twice except one, find the single element. XOR all elements: duplicates cancel (a ^ a = 0), leaving only the single number. Time: O(N), Space: O(1). Single Number II: every element appears three times except one. Use bit counting: for each bit position, count how many numbers have that bit set. If the count % 3 != 0, the single number has that bit set. Single Number III: two elements appear once, all others appear twice. XOR all elements to get a ^ b (the XOR of the two unique numbers). Find any set bit in the result (this bit differs between a and b). Split all numbers into two groups based on that bit. XOR each group separately to get a and b. Missing number: array of N numbers from 0 to N with one missing. XOR all array elements with 0 to N. Duplicates cancel, leaving the missing number.
Counting and Checking Bits
Count set bits (Hamming weight): count the number of 1 bits in an integer. Approach: repeatedly do n = n & (n-1) which removes the lowest set bit. Count iterations until n is 0. Time: O(k) where k is the number of set bits. Power of two: n is a power of two if and only if n > 0 and n & (n-1) == 0. A power of two has exactly one bit set: 8 = 1000, 8-1 = 0111, 8 & 7 = 0. Hamming distance: the number of positions where two numbers differ in binary. Compute x ^ y (bits that differ are set to 1), then count the set bits. Reverse bits: reverse the 32-bit representation. Swap bits from the outside in, or build the result bit by bit by extracting the last bit of the input and appending it to the result. Counting bits (dynamic programming): for each number from 0 to N, count set bits. dp[i] = dp[i & (i-1)] + 1. The number with the lowest bit removed has one fewer set bit. Time: O(N).
Bitmask for Subsets and State
A bitmask represents a subset of N elements using an N-bit integer. Bit k is set (1) if element k is in the subset, clear (0) if not. For N=3 elements {a,b,c}: bitmask 101 represents {a,c}. Enumerate all subsets: iterate from 0 to 2^N – 1. Each integer represents a unique subset. Check membership: mask & (1 << k) != 0 means element k is in the subset. Add element: mask | (1 << k). Remove element: mask & ~(1 << k). Enumerate subsets of a subset: for a bitmask mask, iterate its subsets: sub = mask; while sub > 0: process sub; sub = (sub – 1) & mask. This visits all subsets of mask in decreasing order. Applications: (1) Traveling Salesman Problem (TSP) — dp[mask][i] = minimum cost to visit the cities in mask, ending at city i. Iterate over all masks (subsets of cities). (2) Matching/assignment problems — dp[mask] = optimal assignment of first popcount(mask) tasks to the workers indicated by mask. (3) Game state — represent which tiles are taken, which positions are occupied, or which resources are used in a compact integer.
Common Bit Manipulation Interview Problems
Problems to practice: (1) Single Number (easy) — XOR all elements. (2) Number of 1 Bits (easy) — n & (n-1) loop. (3) Counting Bits (easy) — dp[i] = dp[i & (i-1)] + 1. (4) Power of Two (easy) — n > 0 and n & (n-1) == 0. (5) Reverse Bits (easy) — build result bit by bit. (6) Missing Number (easy) — XOR 0..N with array. (7) Single Number III (medium) — XOR all, split by differing bit. (8) Subsets using bitmask (medium) — iterate 0 to 2^N-1. (9) Maximum XOR of Two Numbers (medium) — trie-based approach, greedily maximize each bit from MSB. (10) Minimum Number of Flips (medium) — XOR the two numbers, count set bits. Pattern recognition: if the problem involves finding a unique element among duplicates, think XOR. If it involves subsets or state compression, think bitmask. If it involves binary properties (power of two, bit counting), think n & (n-1). If it involves finding an optimal XOR, think trie on binary representations.