Bitwise XOR Pattern — Single Number and Bit Manipulation Tricks

Q: Why does XOR find the number that appears once?

Because x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative. Order does not matter, so XOR-ing the whole array lets every pair cancel to zero, leaving only the unpaired value. It runs in O(n) time and O(1) space with no hash map.

Q: How do you find two numbers that each appear once?

XOR everything to get a ^ b. Any set bit in that result is a bit where the two answers differ, so isolate one with x & -x and partition the array on it. Each partition now contains exactly one unpaired number, so XOR each group separately.

XOR problems are pattern-matching on four algebraic facts. There is no algorithm to learn — either you know the identities and the solution is a line, or you do not and the problem looks impossible. That makes this the highest-leverage section on the sheet per minute spent.

The four properties

x ^ x = 0          a value cancels itself
x ^ 0 = x          zero is the identity
a ^ b = b ^ a      commutative
(a ^ b) ^ c = a ^ (b ^ c)    associative

Commutativity and associativity together mean order does not matter, so XOR-ing a whole array collapses every paired value to zero and leaves only what is unpaired.

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

int singleNumber(int[] nums) {
    int result = 0;
    for (int x : nums) result ^= x;   // pairs cancel; the loner survives
    return result;
}

int singleNumber(const vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;   // pairs cancel; the loner survives
    return result;
}

int singleNumber(int* nums, int n) {
    int result = 0;
    for (int i = 0; i < n; i++) result ^= nums[i];
    return result;
}

function singleNumber(nums) {
  let result = 0;
  for (const x of nums) result ^= x;   // pairs cancel; the loner survives
  return result;
}

O(n) time, O(1) space, works on unsorted input, and no hash map. The same reasoning solves

Missing Number: XOR every index together with every value, and everything pairs off

except the index that has no value.

def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result

int missingNumber(int[] nums) {
    int result = nums.length;         // seed with n, since i only reaches n-1
    for (int i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i];        // every index pairs with its value
    }
    return result;
}

int missingNumber(const vector<int>& nums) {
    int result = (int)nums.size();    // seed with n, since i only reaches n-1
    for (int i = 0; i < (int)nums.size(); i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

int missingNumber(int* nums, int n) {
    int result = n;                   /* seed with n */
    for (int i = 0; i < n; i++) result ^= i ^ nums[i];
    return result;
}

function missingNumber(nums) {
  let result = nums.length;        // seed with n, since i only reaches n-1
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

Two singles: split by a set bit

Single Number III — every value appears twice except two. XOR-ing everything gives

a ^ b, which is not either answer. But any bit set in a ^ b is a bit where a and b differ, so partitioning the array on that bit puts a in one group and b in the other, each of which is now a plain Single Number.

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

    lowest_bit = xor_all & -xor_all      # isolates the rightmost set bit

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

int[] singleNumberIII(int[] nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;

    int lowestBit = xorAll & -xorAll;   // isolates the rightmost set bit

    int a = 0, b = 0;
    for (int x : nums) {
        if ((x & lowestBit) != 0) a ^= x;   // the two answers differ here
        else b ^= x;
    }
    return new int[] { a, b };
}

vector<int> singleNumberIII(const vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;

    int lowestBit = xorAll & -xorAll;   // isolates the rightmost set bit

    int a = 0, b = 0;
    for (int x : nums) {
        if (x & lowestBit) a ^= x;      // the two answers differ here
        else b ^= x;
    }
    return {a, b};
}

void singleNumberIII(int* nums, int n, int out[2]) {
    int xorAll = 0;
    for (int i = 0; i < n; i++) xorAll ^= nums[i];

    int lowestBit = xorAll & -xorAll;   /* rightmost set bit */

    int a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] & lowestBit) a ^= nums[i];
        else b ^= nums[i];
    }
    out[0] = a; out[1] = b;
}

function singleNumberIII(nums) {
  let xorAll = 0;
  for (const x of nums) xorAll ^= x;

  const lowestBit = xorAll & -xorAll;   // isolates the rightmost set bit

  let a = 0, b = 0;
  for (const x of nums) {
    if (x & lowestBit) a ^= x;          // the two answers differ here
    else b ^= x;
  }
  return [a, b];
}

x & -x is the idiom to remember: two's complement makes -x the inverse of x plus one, so the AND leaves exactly the lowest set bit standing. It also powers Fenwick trees, which is where you meet it again.

Three of a kind: count bits mod 3

Single Number II — every value appears three times except one. XOR cannot help, because

x ^ x ^ x = x. Count set bits per position instead and take the count modulo 3; whatever remains is the answer's bit pattern.

def single_number_ii(nums):
    result = 0
    for bit in range(32):
        count = sum((x >> bit) & 1 for x in nums)
        if count % 3:
            result |= 1 << bit
    if result >= 2 ** 31:                # Python has unbounded ints
        result -= 2 ** 32                # reinterpret as a signed 32-bit value
    return result

int singleNumberII(int[] nums) {
    int result = 0;
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        for (int x : nums) count += (x >>> bit) & 1;   // >>> , not >>
        if (count % 3 != 0) result |= 1 << bit;
    }
    return result;   // int is already 32-bit signed, so no fixup needed
}

int singleNumberII(const vector<int>& nums) {
    int result = 0;
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        for (int x : nums) count += (static_cast<unsigned>(x) >> bit) & 1;
        if (count % 3) result |= (1 << bit);
    }
    return result;   // int is already 32-bit signed
}

int singleNumberII(int* nums, int n) {
    int result = 0;
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        for (int i = 0; i < n; i++) count += ((unsigned)nums[i] >> bit) & 1;
        if (count % 3) result |= (1 << bit);
    }
    return result;
}

function singleNumberII(nums) {
  let result = 0;
  for (let bit = 0; bit < 32; bit++) {
    let count = 0;
    for (const x of nums) count += (x >>> bit) & 1;   // >>> , not >>
    if (count % 3) result |= 1 << bit;
  }
  return result | 0;   // bitwise ops already coerce to signed 32-bit
}

The generalisation: values appearing k times cancel under "count mod k", and XOR is just the k = 2 case done in parallel across all bits at once.

The idioms worth memorising

Idiom	Meaning
`x & (x - 1)`	clears the lowest set bit — loop it to count bits in O(set bits)
`x & -x`	isolates the lowest set bit
`x & 1`	is odd
`x >> 1`	divide by two
`x ^ (1 << i)`	flip bit `i`
`x & (1 << i)`	test bit `i`

Number of 1 Bits is x & (x - 1) in a loop: each iteration removes one set bit, so it

runs once per set bit rather than 32 times.

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;    // clears the lowest set bit
        count++;
    }
    return count;      // runs once per set bit, not 32 times
}

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= n - 1;    // clears the lowest set bit
        count++;
    }
    return count;      // runs once per set bit, not 32 times
}

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= n - 1;    /* clears the lowest set bit */
        count++;
    }
    return count;
}

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;      // clears the lowest set bit
    count++;
  }
  return count;      // runs once per set bit, not 32 times
}

Maximum XOR of Two Numbers

The one that is not an identity trick. Insert every number into a binary trie, most significant bit first, then for each number walk the trie preferring the opposite bit at every level — the opposite bit is what makes the XOR's high bits 1, and a high bit is worth more than every lower bit combined. O(n × 32) instead of O(n²).

Complexity

O(n) time and O(1) space for the XOR-based ones — that combination is precisely why these get asked when a hash map would be the obvious answer. The bit-counting variants are O(32n), and the trie is O(32n) time with O(32n) space.

Mistakes that cost the round

Trying to XOR the k = 3 problem. x ^ x ^ x = x — odd multiplicities do not cancel.
Signed-integer handling. In Python, integers are unbounded, so the bit-count solution

needs the explicit two's-complement fixup above. In Java, use >>> rather than >>.

Assuming XOR gives you the values. a ^ b is neither a nor b; you need the

splitting bit to recover them.

Confusing `x & -x` with `x & (x - 1)`. One isolates the lowest set bit, the other

clears it.

What to drill

Single Number — the cancellation identity.
Number of 1 Bits — x & (x - 1).
Single Number III — split by the differing bit.
Single Number II — count bits mod 3.
Maximum XOR of Two Numbers in an Array — the binary trie.

All on the 22 DSA Patterns sheet.

Frequently asked

Why does XOR find the number that appears once?

Because x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative. Order does not matter, so XOR-ing the whole array lets every pair cancel to zero, leaving only the unpaired value. It runs in O(n) time and O(1) space with no hash map.

How do you find two numbers that each appear once?

XOR everything to get a ^ b. Any set bit in that result is a bit where the two answers differ, so isolate one with x & -x and partition the array on it. Each partition now contains exactly one unpaired number, so XOR each group separately.

What does `x & (x - 1)` do?

It clears the lowest set bit of x. Looping it until x is zero counts the set bits in as many iterations as there are 1s, rather than always looping 32 times. The related idiom x & -x does the opposite — it isolates that lowest set bit rather than clearing it.

Bitwise XOR