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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does XOR help find a single unique number in an array of duplicates?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”XOR has two key properties: a ^ a = 0 (any number XORed with itself cancels) and a ^ 0 = a (XOR with zero is identity). For an array where every element appears twice except one: XOR all elements together. The duplicates cancel out (each pair XORs to 0), leaving only the unique number. Example: [4,1,2,1,2] -> 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4. Time: O(N). Space: O(1). No sorting, no hash map needed. This extends to Single Number III (two unique numbers): XOR all elements to get a^b. Find any bit where a and b differ (a set bit in a^b). Split numbers into two groups based on that bit. XOR each group to isolate a and b separately.”}},{“@type”:”Question”,”name”:”How does n AND (n-1) work and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”n & (n-1) removes the lowest set bit of n. Example: n=12 (1100), n-1=11 (1011), n&(n-1)=8 (1000). The lowest set bit (position 2) was cleared. Why it works: subtracting 1 flips the lowest set bit and all lower bits. ANDing with the original clears the lowest set bit while preserving all higher bits. Applications: (1) Count set bits (Hamming weight): repeatedly apply n = n & (n-1) and count iterations until n=0. Each iteration removes one set bit. Time: O(k) where k is set bits. (2) Power of two check: n is a power of two if n > 0 and n & (n-1) == 0. Powers of two have exactly one set bit; removing it gives 0. (3) Counting bits DP: dp[i] = dp[i & (i-1)] + 1. The number with its lowest bit removed has one fewer set bit.”}},{“@type”:”Question”,”name”:”How do bitmasks represent subsets in coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A bitmask uses an N-bit integer to represent a subset of N elements. Bit k is 1 if element k is included, 0 if not. For 3 elements {a,b,c}: bitmask 101 (decimal 5) represents {a,c}. Operations: check if element k is in subset: mask & (1 << k) != 0. Add element k: mask | (1 << k). Remove element k: mask & ~(1 << k). Enumerate all 2^N subsets: iterate from 0 to 2^N – 1. Applications: Traveling Salesman Problem — dp[mask][i] = minimum cost visiting cities in mask, ending at i. Assignment problems — dp[mask] = optimal result assigning tasks to workers in mask. Game state compression — represent board positions or resource availability in a compact integer. Bitmask DP reduces exponential backtracking to O(2^N * N) which is feasible for N XOR. Binary properties (power of two, bit count) -> n & (n-1). Subset or state compression -> bitmask. Optimizing over binary representations -> trie on bits.”}}]}