Timevolt

Posted on Jun 26

The Bitwise Jedi: Mastering the XOR Trick Like a Lightsaber

#algorithms #datastructures #programming #coding

The Quest Begins (The "Why")

I still remember the first time I faced a coding interview where the interviewer slid a simple array across the whiteboard: [2, 3, 5, 4, 5, 3, 2]. “Find the element that appears only once,” they said, smiling like a game master about to reveal a hidden level. My gut screamed “hash map!” – O(n) time, O(n) extra space. I coded it, felt the familiar buzz of a working solution, and waited for the nod. Instead, the interviewer leaned back and asked, “Can you do it without extra space?”

That moment felt like staring down a boss in Dark Souls with only a rusty sword. I knew there had to be a trick, something elegant that didn’t require a sack of extra memory. The curiosity turned into a mini‑obsession, and after a few frustrated attempts (and a lot of coffee), the XOR operation whispered its secret to me.

The Revelation (The Insight)

Why XOR?

XOR (^) has two magical properties that make it perfect for “cancelling out” pairs:

Self‑annihilation – a ^ a = 0.
Identity – a ^ 0 = a.

Because XOR is also commutative and associative, the order of operations doesn’t matter. If you XOR every number in an array where all but one appear twice, each pair collapses to zero, and the lone survivor remains unchanged:

a ^ b ^ b ^ c ^ c ^ d   = a ^ (b^b) ^ (c^c) ^ d
                         = a ^ 0   ^ 0   ^ d
                         = a ^ d

When d is the unique element and all others are paired, the result is exactly that unique value. No extra storage, no nested loops – just a single pass through the data.

It’s the algorithmic equivalent of finding the One Ring’s power: a simple, unassuming operation that, when applied correctly, reveals the hidden truth.

Wielding the Power (Code & Examples)

The Struggle – Naïve Approaches

# O(n^2) brute force – painfully slow
def single_brute(nums):
    for i in range(len(nums)):
        if nums.count(nums[i]) == 1:
            return nums[i]
    return None

# O(n) time, O(n) space – hash map (better, but still extra memory)
def single_hash(nums):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    for x, cnt in freq.items():
        if cnt == 1:
            return x
    return None

Both work, but they either waste time or memory – not ideal when the interviewer hints at “constant space.”

The Victory – XOR in Action

def single_number(nums):
    """Return the element that appears once while all others appear twice."""
    result = 0
    for num in nums:
        result ^= num          # the magic line
    return result

Why it works: Each paired number contributes num ^ num = 0. Zero XOR‑ed with anything leaves it unchanged, so after the loop result holds the solitary value.

Common Trap #1 – Forgetting to start at zero

If you initialize result = nums[0] and then XOR the rest, you’ll accidentally cancel the first element incorrectly when it appears twice later. Always begin with a neutral element for XOR – 0.

Common Trap #2 – Mixing up operators

Using | (OR) or & (AND) instead of ^ destroys the cancellation property. OR accumulates bits, AND erodes them; neither yields the clean “pair‑eliminate” effect. Stick to ^.

A Sibling Problem – Two Unique Numbers

LeetCode 260 asks: Given an array where every element appears twice except for two distinct elements, find those two. The same XOR core helps, with a tiny extra step.

def single_number_iii(nums):
    # 1️⃣ XOR of all numbers gives x ^ y (the two uniques combined)
    xy = 0
    for num in nums:
        xy ^= num

    # 2️⃣ Find a set bit that differs between x and y
    #    xy & -xy isolates the rightmost 1‑bit
    diff_bit = xy & -xy

    # 3️⃣ Partition numbers by that bit and XOR each group
    x = y = 0
    for num in nums:
        if num & diff_bit:
            x ^= num
        else:
            y ^= num
    return [x, y]

Why it works:

Step 1 produces x ^ y. Since x != y, at least one bit is set in this result.
Step 2 picks any differing bit (the rightmost set bit is easiest).
Step 3 splits the original array into two buckets: numbers with that bit set and numbers without it. Each bucket now contains one unique number plus pairs that cancel out, leaving the two answers after a final XOR pass.

Both solutions run in O(n) time and O(1) extra space – the hallmark of a true bit‑wise Jedi.

Why This New Power Matters

Armed with the XOR trick, you can:

Slash memory usage in interview coding challenges from linear to constant.
Spot opportunities where a problem looks like it needs a hash table but actually reduces to a simple parity check.
Impress interviewers by showing you understand the why, not just the how – a sign of deeper algorithmic thinking.

Beyond interviews, this mindset trains you to hunt for invariants and algebraic properties in everyday code. It’s the same feeling you get when you finally unlock a secret shortcut in a speedrun: the solution was there all along, you just needed the right lens.

Your Turn – A Mini‑Quest

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

Variation: Find the element that appears once while every other appears three times. (Hint: think about counting bits modulo 3.)
Real‑world: Imagine a log file where each user ID appears twice except for a single anomalous login. How would you detect it in a streaming fashion with O(1) memory?

Drop your solutions or questions in the comments – I love seeing how fellow developers wield their bit‑wise lightsabers. May the XOR be with you! 🚀

DEV Community