Bitwise XOR: Mathematical Invariants & Interview Patterns

The Bitwise XOR (Exclusive OR, denoted by ^ in most C-family languages) evaluates to 1 if and only if the two compared bits differ. In algorithm design, bitwise XOR is effectively addition modulo 2 without carries.

Because XOR possesses unique algebraic properties—primarily that any number XORed with itself cancels out to zero—it enables brilliant O(N) time and strict O(1) memory solutions for array cancellation, missing numbers, and duplicate isolation.

The 4 Core Mathematical Invariants

Pattern 1: The Single Number Problem

Given an array where every integer appears exactly twice except for one unique integer, locate the unique number in O(N) time and O(1) space.

Accumulating XOR across all numbers cancels out every paired duplicate: (A ^ A) ^ (B ^ B) ^ C = 0 ^ 0 ^ C = C.

Java Implementation

public class SingleNumberFinder {
    public static int findSingleNumber(int[] nums) {
        int accumulator = 0;
        for (int num : nums) {
            accumulator ^= num;
        }
        return accumulator;
    }
}

Pattern 2: Finding the Missing Number in Range [0...N]

Given an array of size N containing distinct numbers from 0 to N with exactly one missing, you could compute the arithmetic sum using Gauss's formula N(N+1)/2 - sum(arr). However, on huge integers, calculating the sum risks integer overflow.

XOR solves this without any overflow risk by XORing all array elements alongside all expected indices from 0 to N:

Python Implementation

def find_missing_number(nums: list[int]) -> int:
    """Finds the missing number in [0...N] without integer overflow risk."""
    n = len(nums)
    xor_acc = 0

    # XOR all expected numbers from 0 to N
    for i in range(n + 1):
        xor_acc ^= i

    # XOR all actual numbers present in array
    for num in nums:
        xor_acc ^= num

    return xor_acc

# Example
arr = [3, 0, 1]
print(find_missing_number(arr)) # Output: 2

Pattern 3: Two Single Numbers (Bit Partitioning)

What if an array contains two unique numbers (say x and y) while all other numbers appear twice? XORing the whole array yields combined = x ^ y. Because x ≠ y, combined must have at least one bit set to 1.

That set bit represents a position where x and y have different bits. We can use this bit as a discriminator to partition the array into two separate groups, solving both independently:

flowchart TD
    Start["XOR All Elements:\ncombined = x ^ y"] --> Extract["Isolate Rightmost Set Bit:\ndiffBit = combined & (-combined)"]
    Extract --> Partition["Partition Elements into 2 Buckets:"]
    Partition --> Bucket0["Bucket A:\n(num & diffBit) == 0"]
    Partition --> Bucket1["Bucket B:\n(num & diffBit) != 0"]
    Bucket0 --> Res0["XOR Bucket A → Yields x"]
    Bucket1 --> Res1["XOR Bucket B → Yields y"]

TypeScript Implementation

export function findTwoSingleNumbers(nums: number[]): [number, number] {
  // Step 1: XOR entire array to get (x ^ y)
  let diff = 0;
  for (const num of nums) {
    diff ^= num;
  }

  // Step 2: Extract the rightmost set bit (Two's complement trick: diff & -diff)
  const rightmostSetBit = diff & -diff;

  // Step 3: Divide into two groups and XOR each group
  let num1 = 0;
  let num2 = 0;

  for (const num of nums) {
    if ((num & rightmostSetBit) === 0) {
      num1 ^= num; // Group with bit unset
    } else {
      num2 ^= num; // Group with bit set
    }
  }

  return [num1, num2];
}

Pattern 4: In-Place Swapping & The Pointer Aliasing Trap

You can swap two integer variables without a third variable using bitwise XOR:

a ^= b; // a now holds a ^ b
b ^= a; // b now holds (b ^ a ^ b) = a
a ^= b; // a now holds (a ^ b ^ a) = b

The Critical Bug (Memory Aliasing): If you attempt this trick on array elements where pointers point to the same memory address (e.g. swap(arr, i, i)), the first step executes arr[i] ^= arr[i] which wipes the value to 0 irreversibly! In production systems, always use standard temporary variables or destructuring assignment.

Complexity Analysis