Bit Manipulation Interview Patterns

Bit manipulation questions are a staple of coding interviews because they test your understanding of computer fundamentals, logical reasoning, and ability to devise clever, efficient solutions. Mastering a few core patterns can transform these seemingly cryptic problems into straightforward applications of binary logic and bitwise operators, allowing you to solve problems in $O(1)$ space and $O(n)$ time where others might use hash maps or nested loops.

Core Pattern 1: Finding the Unique Element with XOR

The most elegant application of bitwise operations is using the XOR (exclusive OR) operator to find a unique element in a collection of duplicates. This relies on two fundamental properties of XOR: it is self-inverse ($a\oplus a=0$) and commutative ($a\oplus b=b\oplus a$).

Consider the classic problem: "Every number in an array appears twice except for one. Find the single number." A brute-force approach might involve counting frequencies, but XOR provides an $O(n)$ time, $O(1)$ space solution. The logic is cumulative: XOR-ing all numbers together cancels out paired duplicates ($a\oplus a=0$), and the commutative property ensures order doesn't matter. The final result is the unique number ($0\oplus b=b$).

Example: Find the single number in [4, 1, 2, 1, 2].

1. Start with result = 0.
2. $0\oplus 4=4$ (binary 100)
3. $4\oplus 1=5$ (101 $\oplus$ 001 = 100 then 100? Wait, let's compute carefully: 4 is 100, 1 is 001. 100 XOR 001 = 101, which is 5.)
4. $5\oplus 2=7$ (101 $\oplus$ 010 = 111)
5. $7\oplus 1=6$ (111 $\oplus$ 001 = 110)
6. $6\oplus 2=4$ (110 $\oplus$ 010 = 100)

The final result is 4. The pairs (1,1) and (2,2) canceled themselves out.

This pattern extends to variations like finding two unique numbers among duplicates, which involves partitioning the set based on a set bit in the final XOR result.

Core Pattern 2: Counting and Checking Set Bits

Many problems revolve around the state of individual bits. The foundational operation here is bit masking, where you use the AND operator (&) with a mask to isolate a specific bit. A common task is counting the number of set bits (bits with value 1) in an integer, known as its Hamming weight.

The naive method checks each of the 32 bits in an integer. A more efficient algorithm, Brian Kernighan's method, leverages the trick that n & (n - 1) unsets the rightmost set bit in n. You can count bits by repeatedly applying this operation until the number becomes zero.

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # Drops the lowest set bit
        count += 1
    return count

This runs in $O(k)$ time where $k$ is the number of set bits, often more efficient than $O(32)$. This operation is also the key to checking if a number is a power of two. A positive integer is a power of two if it has exactly one set bit. Therefore, the condition n > 0 and (n & (n - 1)) == 0 provides an $O(1)$ check, as it tests if unsetting the rightmost bit results in zero.

Core Pattern 3: Multiplication, Division, and Bit Shifting

Bit shifting is a cornerstone for efficient arithmetic. A left shift (<<) multiplies a number by two for each shift position, effectively adding zeros to the right in binary. A right shift (>>) performs integer division by two, discarding the least significant bit.

For example, n << 3 is equivalent to $n\times 2^3=n\times 8$. Conversely, n >> 2 is equivalent to $\lfloor n/2^2\rfloor =\lfloor n/4\rfloor$. This is far more efficient than using arithmetic operators and is critical in systems programming and embedded environments. Interview problems might ask you to implement multiplication or division using only bitwise operators and addition, which relies on decomposing one number into its binary components (powers of two) and summing shifted values.

Core Pattern 4: Generating Subsets with Bitmasks

One of the most powerful applications is using an integer's binary representation as a bitmask to represent subsets of a set. If you have an array of size n, every integer from 0 to $2^n-1$ represents a unique subset. Each bit position i corresponds to whether the element at index i is included (bit is 1) or excluded (bit is 0).

This provides an elegant, $O(n\times 2^n)$ method to generate all subsets without recursion. You iterate through all mask values from 0 to $2^n-1$, and for each mask, iterate through bits i to build the subset by checking if the i-th bit is set using mask & (1 << i).

Example: For set ['A', 'B', 'C'] (n=3), mask 5 (binary 101) corresponds to the subset ['A', 'C']. This pattern solves a wide range of combinatorial search problems, such as finding a subset that meets a target sum or evaluating all possible configurations, with minimal code.

Common Pitfalls

1. Operator Precedence: Bitwise operators (&, |, ^) have lower precedence than comparison operators (==, <). Forgetting parentheses is a classic bug. if (n & 1) == 0: checks if n is even. if n & 1 == 0: is interpreted as if n & (1 == 0):, which is if n & 0:, always false.
2. Overlooking Two's Complement and Sign: Right shifting (>>) on negative integers is arithmetic shift in many languages; it preserves the sign bit by filling with 1s on the left. This can lead to infinite loops if you use while n > 0 with negative inputs. For bit-counting, always work with the unsigned representation.
3. Misapplying the Power-of-Two Check: The elegant check (n & (n-1)) == 0 only works for n > 0. It incorrectly returns True for n=0, which is not a power of two. Always include the positive check.
4. Inefficient Bit Counting in Interviews: While the bin(n).count('1') method works in Python, it's often considered a library trick that misses the point of the interview question. Demonstrating the n & (n-1) method shows a deeper understanding of binary representation and optimization.

Summary

• The XOR operator’s self-inverse and commutative properties provide elegant $O(n)$/$O(1)$ solutions to "unique element" problems by canceling out paired duplicates.
• Counting set bits efficiently is done via n & (n-1), which unsets the lowest set bit. This same operation allows for an $O(1)$ check to see if a positive integer is a power of two.
• Bit shifting (<< and >>) performs efficient multiplication and division by powers of two, a fundamental low-level optimization technique.
• Bitmasking uses an integer's binary digits to represent subsets, enabling the systematic generation and iteration over all combinations of a set without recursion.