Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits

This bit manipulation LeetCode pattern guide focuses on the few ideas that unlock most interview problems: XOR tricks, masks, and counting bits. Bit problems can feel like trivia, but the reliable approach is to translate each operation into a small set of questions: Which bit do I care about? Do I need to set, clear, toggle, test, or count it? What invariant does XOR preserve? Once you can answer those, the code is usually short.

Bit manipulation appears in interviews because it tests precision. Off-by-one errors, sign behavior, and operator precedence all matter. The goal is not to memorize every clever trick; it is to know the handful of operations that explain the clever tricks.

The operations you must know

| Operation | Expression | Meaning | |---|---|---| | Test bit i | (x >> i) & 1 | Is bit i set? | | Set bit i | x | (1 << i) | Force bit i to 1 | | Clear bit i | x & ~(1 << i) | Force bit i to 0 | | Toggle bit i | x ^ (1 << i) | Flip bit i | | Keep low k bits | x & ((1 << k) - 1) | Mask lower bits | | Remove lowest set bit | x & (x - 1) | Drop the rightmost 1 | | Isolate lowest set bit | x & -x | Keep only the rightmost 1 |

Indexes are usually zero-based from the least significant bit. If the problem says “the 1st bit,” clarify whether it means human counting from 1 or programmer counting from 0.

XOR tricks without magic

XOR has three properties that drive most tricks:

• a ^ a = 0
• a ^ 0 = a
• XOR is commutative and associative, so order does not matter.

The classic “single number” problem uses those properties:

def single_number(nums):
    ans = 0
    for x in nums:
        ans ^= x
    return ans

Every duplicated number cancels itself out, leaving the value that appears once.

For “two single numbers where every other number appears twice,” XOR all numbers to get a ^ b. Since a and b are different, this result has at least one set bit. Use one set bit to partition numbers into two groups; duplicates still cancel within each group.

def two_single_numbers(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x

    bit = xor_all & -xor_all
    a = b = 0
    for x in nums:
        if x & bit:
            a ^= x
        else:
            b ^= x
    return [a, b]

The insight is not the syntax. It is that a set bit in a ^ b marks a position where a and b differ, so it can separate them.

Counting bits

Counting set bits appears in Hamming distance, subsets, dynamic programming, and optimization constraints.

The simplest loop removes one set bit at a time:

def popcount(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

This runs in O(number of set bits), not O(number of total bits). In Python, x.bit_count() is available, but interviewers may want the manual version.

For “counting bits from 0 to n,” use DP:

def count_bits(n):
    ans = [0] * (n + 1)
    for x in range(1, n + 1):
        ans[x] = ans[x >> 1] + (x & 1)
    return ans

The recurrence says the number of ones in x equals the number in x // 2 plus the last bit. Another valid recurrence is ans[x] = ans[x & (x - 1)] + 1, which removes the lowest set bit.

Masks as sets

A mask is an integer used as a compact set of boolean flags. Bit i represents whether item i is included.

Common set operations:

| Set idea | Bit expression | |---|---| | Add item i | mask | (1 << i) | | Remove item i | mask & ~(1 << i) | | Toggle item i | mask ^ (1 << i) | | Check item i | mask & (1 << i) | | Union | a | b | | Intersection | a & b | | Difference | a & ~b |

This is useful when n is small, usually up to 20-25 for subset enumeration. 2^n is still exponential, but bit masks make each subset compact and fast to manipulate.

Subset enumeration template:

for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(items[i])

Enumerating submasks of a mask is a more advanced pattern:

sub = mask
while sub:
    # process sub
    sub = (sub - 1) & mask

This visits only submasks contained in mask. It is common in DP over subsets.

Hamming distance and parity

Hamming distance between two integers is the number of bit positions where they differ. XOR marks exactly those positions.

def hamming_distance(a, b):
    return (a ^ b).bit_count()

Parity asks whether the number of set bits is odd or even. XOR also models parity because toggling the same bit twice cancels. Problems about “odd occurrences,” “even counts,” and “same parity” often have a bit solution hiding underneath.

For characters, you can use a 26-bit mask to track odd counts:

mask = 0
for ch in s:
    mask ^= 1 << (ord(ch) - ord('a'))

If at most one bit is set, a string can be permuted into a palindrome:

mask == 0 or (mask & (mask - 1)) == 0

That expression checks whether the mask has zero or one set bit.

Signed integers and language traps

Bit manipulation is language-sensitive.

Python integers have arbitrary precision, so negative numbers behave as if they have infinitely many leading ones in two's complement. For LeetCode problems like “reverse bits” or “number of 1 bits,” mask to 32 bits when needed:

x &= 0xffffffff

In Java, >> is arithmetic shift and preserves the sign bit, while >>> is logical shift and fills with zero. In JavaScript, bitwise operators convert to 32-bit signed integers. In C and C++, shifting by a count greater than or equal to the bit width is undefined or problematic, and signed overflow is dangerous.

In interviews, say what width you assume: “I’ll treat this as a 32-bit unsigned integer because the prompt defines the input that way.”

Recognizing bit manipulation problems

Look for these signals:

• Values are bounded by small bit widths, like 32 or 64 bits.
• The prompt asks for uniqueness under duplicate counts.
• You need to represent many boolean choices compactly.
• The problem mentions masks, permissions, flags, subsets, parity, Hamming distance, or powers of two.
• A naive set or array solution works, but the interviewer asks for O(1) space.

If the input size is huge but each value is small, bitsets may help. If n is large and you are considering 2^n subsets, masks do not remove the exponential cost; they just make it cleaner.

Common interview problems and the key move

| Problem | Key bit idea | |---|---| | Single Number | XOR cancels duplicates | | Single Number II | Count each bit modulo 3 | | Missing Number | XOR indexes and values, or use sum | | Power of Two | x > 0 and (x & (x - 1)) == 0 | | Reverse Bits | Shift result left, append low bit | | Counting Bits | DP from x >> 1 or x & (x - 1) | | Maximum XOR | Trie by bits or greedy prefix mask | | Subsets | Mask represents included elements |

For “every number appears three times except one,” XOR alone is not enough because three copies do not cancel under XOR. Count bits column by column modulo 3:

def single_number_thrice(nums):
    ans = 0
    for i in range(32):
        total = sum((x >> i) & 1 for x in nums)
        if total % 3:
            ans |= 1 << i
    if ans >= 1 << 31:
        ans -= 1 << 32
    return ans

The final adjustment converts a 32-bit two's complement result back to a negative Python integer when needed.

Debugging checklist

Before submitting a bit solution, check:

1. Did I parenthesize shifts and masks clearly?
2. Are bit indexes zero-based?
3. Do I need to handle negative numbers or fixed width?
4. Is the result supposed to be signed or unsigned?
5. Does XOR cancellation match the exact duplicate count?
6. Is n small enough for 1 << n enumeration?
7. Have I tested 0, one-bit values, all bits set, and duplicates?

How to explain bit work in interviews and resumes

A strong interview explanation avoids “because it is a trick.” For XOR:

“XOR cancels equal pairs and leaves the unmatched value because a ^ a is zero and order does not matter. For the two-unique version, xor_all gives a ^ b; any set bit in that result separates the two unique values into different groups.”

For masks:

“I’m representing the selected set as an integer, where bit i means item i is present. That lets me test membership and transition states with constant-time bit operations.”

Resume phrasing:

• “Compressed boolean state into bit masks to reduce memory overhead and simplify subset transitions.”
• “Implemented parity-based validation with XOR masks instead of per-character hash maps.”
• “Optimized repeated set membership checks using integer flags and popcount-based scoring.”

Bit manipulation rewards slow, exact thinking. Write the invariant in words, test the smallest examples in binary, and be explicit about width. The tricks stop feeling like tricks when every operator has a job.

Operator precedence and readability

Bitwise code is compact enough that readability becomes part of correctness. In Python, Java, and JavaScript, shifts and bitwise operators have precedence rules that are easy to forget under interview pressure. Prefer explicit parentheses: write (mask & (1 << i)) != 0 instead of relying on memory. The same applies to x & (x - 1): without parentheses, the expression may still parse as intended in some languages, but the reader has to work harder.

Name intermediate masks when the idea matters:

bit = 1 << i
is_set = (mask & bit) != 0

This makes it easier to debug and easier for the interviewer to follow your reasoning.

A quick binary dry run

For every bit trick, test one value in binary. If x = 0b101100, then x - 1 = 0b101011, and x & (x - 1) = 0b101000; the lowest set bit disappeared. If x & -x is used, the result is 0b000100, the isolated lowest set bit. Saying this out loud demystifies the two's complement behavior and catches cases where x might be zero. For x = 0, both expressions return zero, so a power-of-two check must include x > 0.

Related guides

• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Divide and Conquer LeetCode Pattern Guide — Merge Sort, Quickselect, and Recursion — A practical LeetCode pattern guide for divide and conquer: master recursive contracts, merge sort variations, quickselect, tree recursion, complexity, and common interview traps.