Use XOR, AND, OR, shifts to solve problems in O(1) extra memory, often exploiting parity.

Data Flow (Single Number)

nums = [4, 1, 2, 1, 2]
xor all: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4
because x ^ x = 0 and 0 ^ x = x

When to use

• “Find the unique element where every other appears twice”.
• “Swap two numbers without temp”.
• Check power of two: n & (n-1) == 0 for n > 0.
• Count set bits (n & -n strips lowest bit).

Code

def single_number(nums):
    x = 0
    for n in nums: x ^= n
    return x
 
def hamming_weight(n):
    cnt = 0
    while n:
        n &= n - 1
        cnt += 1
    return cnt

Pitfalls

• swap trick fails when a and b are the same reference — it zeroes the value.
• Operator precedence: n & 1 == 0 parses as n & (1 == 0). Use parentheses.

Analogy

Modulo-2 lights: pair them up and they cancel. Leftover bits are anomalies.

Interview tip: Whenever “all duplicates except one” or “parity” appears, XOR is the answer.