The Matrix of Bitwise: One XOR Trick to Rule Them All

The Quest Begins (The "Why")

I still remember the first time I stared at a competitive‑programming problem that asked me to find the lone number in an array where every other value showed up twice. My brute‑force instinct screamed “sort it, then scan for the lonely one!” – O(n log n) felt like dragging a sack of bricks up a hill. I tried a hash map, which worked but burned extra memory and made my solution feel… clunky. After a few failed submissions, I was frustrated enough to mutter, “There has to be a cleaner way.”

That moment was my mini‑dragon: a seemingly simple task that kept tripping me up because I was over‑complicating it. I wanted a solution that felt like a sleek katana swipe – fast, constant‑space, and utterly elegant. Little did I know the answer was hiding in a bitwise operation I’d used only for swapping variables without a temp.

The Revelation (The Insight)

The treasure I uncovered was the XOR operation and its two super‑powers:

1. Self‑cancellation – a ^ a = 0.
2. Identity – a ^ 0 = a.

Because XOR is associative and commutative, the order of operations doesn’t matter. If you XOR a bunch of numbers together, every pair that appears twice annihilates itself to zero, and the lone survivor remains untouched.

Why does this work? Think of each bit as a tiny light switch. Flipping a switch twice (XOR with 1 twice) leaves it exactly as it started. Flipping it once (XOR with 1) toggles it. When you XOR all numbers, each bit gets flipped as many times as there are 1s in that column across the array. An even number of flips lands the switch back at 0; an odd number leaves it at 1 – precisely the bit pattern of the element that appears an odd number of times (once, in our case).

It’s not magic; it’s parity. And the best part? It runs in a single pass, uses O(1) extra space, and needs no fancy data structures.

Wielding the Power (Code & Examples)

The “Before” – a naïve approach

def single_number_naive(nums):
    # O(n log n) time, O(1) extra space (if we sort in‑place)
    nums.sort()
    for i in range(0, len(nums)-1, 2):
        if nums[i] != nums[i+1]:
            return nums[i]
    return nums[-1]   # handles the case where the lone is at the end

Sorting feels heavyweight for such a simple task, and it mutates the input – a no‑no in many interview settings.

The “After” – XOR in action

def single_number(nums):
    """
    Returns the element that appears exactly once while every other
    element appears twice.
    Time  : O(n)
    Space : O(1)
    """
    result = 0
    for num in nums:
        result ^= num          # flip bits according to num
    return result

Why this is beautiful:

• One line inside the loop does the whole job.
• No extra containers, no sorting, no edge‑case gymnastics.
• Works for negative numbers as well because Python’s integers are of unlimited width and XOR works on their two’s‑complement representation.

Common trap #1 – forgetting to initialise result to 0

If you start with result = nums[0] and then loop from nums[1:], you’ll still get the right answer, but you’ll have to handle the empty‑array case separately. Starting at 0 is the cleanest, universally safe pattern.

Common trap #2 – mixing up ^ with **

In Python, ^ is bitwise XOR, not exponentiation. It’s an easy slip if you come from a language where ^ means power. A quick sanity check: 5 ^ 3 equals 6 (101 xor 011 = 110), not 125.

A second interview twist – two lonely numbers

Sometimes the prompt upgrades: every element appears twice except for two distinct numbers that appear once each. The same XOR idea works, we just need to split the array into two groups based on a distinguishing bit.

def single_two(nums):
    # Step 1: XOR of all numbers gives x ^ y where x and y are the two uniques
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Step 2: Find a set bit (rightmost) that differs between x and y
    # xor_all is non‑zero because x != y
    set_bit = xor_all & -xor_all   # isolates the lowest 1‑bit

    # Step 3: Partition numbers into two buckets and XOR each bucket
    x = y = 0
    for num in nums:
        if num & set_bit:
            x ^= num
        else:
            y ^= num
    return x, y

Explanation:

• xor_all holds the bits where the two uniques differ.
• Picking any set bit (we use the lowest for simplicity) guarantees that the two uniques fall into different buckets.
• XOR-ing each bucket cancels out the paired numbers, leaving the unique in each.

Both functions run in O(n) time and O(1) extra space – the same complexity as the original trick, just with a tiny bit more bookkeeping.

Why This New Power Matters

Mastering XOR isn’t just about solving “single number” puzzles; it’s a mindset shift. You start seeing problems through the lens of parity and bit‑wise invariants, which opens doors to:

• Finding a missing number in a range [0, n] (XOR the range with the array).
• Detecting duplicates without extra memory (XOR plus sum tricks).
• Crafting fast checksums, parity checks, or even simple cryptographic toys.

In an interview, dropping a one‑liner like return reduce(xor, nums) signals that you think at the bit level – a signal that interviewers love because it shows depth beyond textbook loops.

And honestly, there’s a rush when you watch the algorithm collapse a messy array into a clean answer with a single pass. It felt like when the Avengers finally assemble after a long battle — each piece clicking into place, the hero’s theme swelling, and the villain (inefficient code) dissolving into nothing.

Your Turn

Grab a piece of paper (or your IDE) and try this:

Given an array of integers where every element appears three times except for one that appears once, find that single element using only O(n) time and O(1) space.

Hint: think about counting bits modulo 3.

Drop your solution in the comments, share a “aha!” moment, or ask a question if the bit‑parity concept still feels fuzzy. Let’s keep the quest going – the next bit‑wise boss is waiting!