Bit Manipulation / XOR Tricks

Single Number: The Motivating Problem

LeetCode 136. Single Number gives you a non-empty array of integers where every element appears exactly twice, except for one element that appears exactly once. Find that single element.

Given nums = [4, 1, 2, 1, 2], the output is 4. The numbers 1 and 2 each appear twice, while 4 appears only once.

Why Brute Force Is Wasteful

The naive approach is to count the frequency of every element using a hash map, then scan for the element with count 1. This works in $O(n)$ time but requires $O(n)$ extra space for the map. You could also sort the array and look for the element that does not match its neighbor, but that costs $O(n \log n)$ time.

The problem specifically asks: can you solve it in $O(n)$ time and $O(1)$ space? That is where XOR comes in.

The Core Idea: XOR Properties

XOR (exclusive or) has three properties that make it perfect for this problem:

1. Self-inverse: $a \oplus a = 0$. Any number XORed with itself is zero.
2. Identity: $a \oplus 0 = a$. Any number XORed with zero is itself.
3. Commutative and associative: The order in which you XOR values does not matter. You can rearrange and group them however you like.

These properties together mean that if you XOR all elements of the array, every pair cancels out to zero, and the single unpaired element remains.

Walking Through nums = [4, 1, 2, 1, 2]

Let us trace the running XOR step by step, showing the binary representation for clarity.

At step 4, XORing with 1 cancels the 1 from step 2. At step 5, XORing with 2 cancels the 2 from step 3. The final result is 4, the single number.

Because XOR is commutative and associative, you can think of the computation as: $(4) \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 = 4$.

Code for Single Number

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Three lines of logic. $O(n)$ time, $O(1)$ space. Every element is visited once, and no extra storage is needed beyond a single integer.

Key Bit Manipulation Techniques

The XOR trick for Single Number is just the beginning. Bit manipulation offers a toolkit of elegant constant-time operations that appear across many problems. Here are the most important ones.

Isolating the Lowest Set Bit: n & (-n)

The expression n & (-n) extracts the lowest set bit of n. In two's complement representation, -n is computed by flipping all bits of n and adding 1. This means every bit below the lowest set bit becomes 0 in both n and -n, the lowest set bit itself is 1 in both, and every bit above it differs. The AND therefore isolates exactly that one bit.

For example, if n = 12 (binary 1100), then -n = -12 (binary ...0100 in two's complement), and n & (-n) = 0100 = 4.

This technique is central to LeetCode 260. Single Number III, which we will explore in detail below.

Removing the Lowest Set Bit: n & (n - 1)

The expression n & (n - 1) clears the lowest set bit of n. Subtracting 1 from n flips the lowest set bit to 0 and sets all lower bits to 1. The AND with n preserves everything above the lowest set bit and zeroes out the rest.

For example, if n = 12 (binary 1100), then n - 1 = 11 (binary 1011), and n & (n - 1) = 1000 = 8.

This is the heart of Brian Kernighan's algorithm for counting set bits, used in LeetCode 191. Number of 1 Bits.

def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1  # remove lowest set bit
        count += 1
    return count

Each iteration removes exactly one set bit, so the loop runs exactly as many times as there are 1-bits. For a 32-bit integer, this is at most 32 iterations, but it is often far fewer.

Checking Power of 2: n & (n - 1) == 0

A power of 2 has exactly one set bit. Removing it with n & (n - 1) yields 0. So n > 0 and n & (n - 1) == 0 is a single-operation test for whether n is a power of 2. This appears in LeetCode 231. Power of Two.

def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Sum Without Arithmetic: XOR and AND

You can add two integers without using + or - by separating the addition into two parts:

• No-carry sum: a ^ b computes the sum of each bit position ignoring carries. Where both bits are 1, XOR gives 0, so the carry is lost.
• Carry: (a & b) << 1 computes the carry. The AND finds positions where both bits are 1, and the left shift moves the carry to the next higher position.

You then repeat the process: the new a is the XOR result, the new b is the carry, and you continue until the carry is 0. This is the basis of LeetCode 371. Sum of Two Integers.

def getSum(a, b):
    mask = 0xFFFFFFFF
    while b != 0:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    # If the sign bit is set, interpret as a negative 32-bit integer
    return a if a < 0x80000000 else a - 0x100000000

The mask keeps both operands inside 32 bits at every step, simulating fixed-width overflow. Once the loop ends, a holds the 32-bit unsigned bit pattern of the answer. If the top bit is set, we convert back to Python's signed view by subtracting $2^{32}$. In languages like Java or C++ with fixed-width integers, no mask or post-processing is needed.

Single Number III: A Deeper XOR Application

LeetCode 260. Single Number III raises the difficulty. Now the array has exactly two elements that appear once, and all other elements appear twice. Find both unique elements.

Given nums = [1, 2, 1, 3, 2, 5], the output is [3, 5] (in any order).

Why a Single XOR Pass Is Not Enough

If you XOR all elements, the pairs still cancel out, but you are left with 3 ^ 5 = 6 (binary 110). This is the XOR of the two unique numbers, not the numbers themselves. You need a way to separate them.

The Key Insight: Use a Differing Bit to Split

Since the two unique numbers are different, their XOR must have at least one set bit. That bit is a position where the two numbers differ: one has a 1 there and the other has a 0. If we partition all numbers into two groups based on whether that bit is set, the two unique numbers will land in different groups, and within each group, the paired numbers still cancel.

We use n & (-n) to isolate the lowest set bit of the combined XOR, giving us a convenient bit to split on.

Walking Through nums = [1, 2, 1, 3, 2, 5]

Step 1: XOR everything.

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5 = 0 ^ 0 ^ 3 ^ 5 = 6

In binary, 6 = 110.

Step 2: Isolate the lowest set bit.

6 & (-6) = 010 = 2

The bit at position 1 (value 2) is where 3 and 5 differ. In binary: 3 = 011 has this bit set, 5 = 101 does not.

Step 3: Split into two groups and XOR each.

Group A (bit 1 is set): 2 (010), 2 (010), 3 (011). XOR: 2 ^ 2 ^ 3 = 3.

Group B (bit 1 is not set): 1 (001), 1 (001), 5 (101). XOR: 1 ^ 1 ^ 5 = 5.

Each group contains exactly one unique number, and the paired numbers cancel within their group. The answer is [3, 5].

Code for Single Number III

def singleNumber(nums):
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Isolate the lowest set bit where the two unique numbers differ
    diff_bit = xor_all & (-xor_all)

    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]

Two passes through the array, each $O(n)$. No extra data structures. The total complexity is $O(n)$ time and $O(1)$ space.

Other Useful XOR Tricks

Swap Without a Temporary Variable

XOR can swap two variables without a third:

a ^= b
b ^= a
a ^= b

After these three operations, a and b have exchanged values. This works because: $a \oplus b \oplus b = a$ and $a \oplus b \oplus a = b$. In practice, using a temporary variable is usually clearer, but this trick occasionally appears in interview discussions.

Finding the Missing Number

Given an array of $n$ distinct numbers from the range $[0, n]$, one number is missing. XOR all elements with all indices from 0 to $n$:

def missingNumber(nums):
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

Every number that appears in both the array and the range cancels out, leaving only the missing one. This solves LeetCode 268. Missing Number in $O(n)$ time and $O(1)$ space.

Single Number II: Elements Appearing Three Times

LeetCode 137. Single Number II changes the constraint: every element appears exactly three times except for one that appears once. XOR alone will not cancel out triples since a ^ a ^ a = a, not zero.

Bit Counting Mod 3

The cleanest approach is to count, for each bit position, how many numbers have that bit set. If a bit position's total count is not divisible by 3, the single element must have that bit set.

def singleNumber(nums):
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1
        if bit_sum % 3:
            result |= 1 << i
    # handle negative numbers (Python)
    if result >= 2**31:
        result -= 2**32
    return result

State Machine Approach

A more elegant constant-space solution uses two variables, ones and twos, to track bit counts modulo 3. After processing each number: ones holds bits that have appeared 1 mod 3 times, and twos holds bits that have appeared 2 mod 3 times. When a bit reaches count 3, both variables reset it to 0.

def singleNumber(nums):
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

The two lines are order-dependent. After updating ones, the ~twos mask prevents bits that have appeared twice from staying in ones. After updating twos, the ~ones mask prevents bits that just moved to count 1 from also appearing in twos. When a bit's count reaches 3, it gets cleared from both. The final ones holds exactly the bits of the single element.

Bitwise AND of a Number Range

LeetCode 201. Bitwise AND of Numbers Range asks: given two integers left and right, return the bitwise AND of all integers in [left, right].

ANDing a large range naively is too slow. The key insight is that the result is the common prefix of left and right in binary, with the remaining lower bits all zeroed out. Any bit position where left and right differ will see both 0 and 1 somewhere in the range, so the AND at that position is 0.

def rangeBitwiseAnd(left, right):
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

Right-shift both numbers until they are equal: that equal value is the common prefix. Then left-shift back by the same amount to restore the original bit positions, with zeros filling the lower bits. The loop runs at most 31 times for 32-bit integers, so this is $O(\log n)$ time and $O(1)$ space.

When to Reach for Bit Manipulation

Bit manipulation is the right tool when:

• The problem involves finding elements that appear an unusual number of times (once when others appear twice, etc.).
• You need $O(1)$ space and the data involves integers.
• The problem explicitly asks you to avoid arithmetic operators.
• You are working with subsets or state compression (see bitmask DP).
• You need to efficiently iterate over or count set bits.

The patterns above, namely XOR for cancellation, n & (-n) for isolating the lowest set bit, and n & (n - 1) for removing it, form a small but powerful vocabulary that covers the vast majority of bit manipulation problems on LeetCode.

Complexity Analysis

Time: $O(n)$ for Single Number, Single Number III, and Missing Number: one or two linear passes through the array. Brian Kernighan's bit count runs in $O(k)$ where $k$ is the number of set bits, which is at most $O(\log n)$ for an integer $n$.

Space: $O(1)$ for all techniques above. No hash maps, no sorting, no auxiliary arrays. This is the defining advantage of bit manipulation approaches.

Recognizing this pattern

You're probably looking at bit manipulation / XOR tricks when:

• Every element appears twice (or k times) except one. XOR cancels the duplicates in O(n) / O(1) space.
• You need to enumerate all subsets of a small set (n \leq 20), so you iterate bitmasks 0..(1 << n) - 1.
• You need to count set bits, isolate the lowest set bit, or toggle a specific bit without auxiliary memory.
• The problem explicitly forbids extra space or asks for an O(1) space solution on an array problem.

Common templates:

• XOR cancellation for the lone element: XOR everything; pairs vanish. Example: Single Number.
• Split by a differing bit: XOR all, find any set bit of the result, partition the array. Example: Single Number III.
• Bitmask subset enumeration: loop mask over 0..(1 << n), optionally enumerate submasks via (s - 1) & mask. Example: Subsets.
• Brian Kernighan / lowest-bit tricks: n & (n - 1) to clear, n & -n to isolate. Example: Number of 1 Bits.