XOR Magic - The Swiss Army Knife of Bits

"XOR là ma thuật. Một operator đơn giản mà giải quyết được hàng trăm bài toán." - HPN

XOR Properties

Hiểu 4 properties này = Giải được 80% bài XOR:

# 1. Self-inverse: A ^ A = 0
5 ^ 5  # = 0

# 2. Identity: A ^ 0 = A
5 ^ 0  # = 5

# 3. Commutative: A ^ B = B ^ A
3 ^ 7 == 7 ^ 3  # True

# 4. Associative: (A ^ B) ^ C = A ^ (B ^ C)
(2 ^ 3) ^ 4 == 2 ^ (3 ^ 4)  # True

📘 Key Insight

XOR cùng một số 2 lần = Về lại giá trị ban đầu!

A ^ B ^ B = A ^ 0 = A

Đây là nền tảng của nhiều algorithms và encryption.

Classic Problems

1. Swap Variables Without Temp

def swap_xor(a: int, b: int) -> tuple:
    """
    Swap two integers without temporary variable.
    
    How it works:
    Step 1: a = a ^ b  → a holds XOR of both
    Step 2: b = a ^ b  → b = (a^b) ^ b = a
    Step 3: a = a ^ b  → a = (a^b) ^ a = b
    """
    a = a ^ b
    b = a ^ b  # Now b = original a
    a = a ^ b  # Now a = original b
    return a, b


# Demo
x, y = 5, 9
print(f"Before: x={x}, y={y}")
x, y = swap_xor(x, y)
print(f"After:  x={x}, y={y}")  # x=9, y=5

⚠️ Practical Note

Trong production, dùng a, b = b, a (Pythonic) hoặc temp variable. XOR swap chỉ nên dùng trong embedded systems hoặc interview flex 😎

2. Find Single Non-Duplicate Number

def single_number(nums: list) -> int:
    """
    Find the number that appears only once.
    All other numbers appear exactly twice.
    
    LeetCode 136: Single Number
    
    Time: O(N)
    Space: O(1)
    
    Why it works:
    - a ^ a = 0 (duplicates cancel out)
    - 0 ^ x = x (single number remains)
    
    Example: [4, 1, 2, 1, 2]
    4 ^ 1 ^ 2 ^ 1 ^ 2
    = 4 ^ (1 ^ 1) ^ (2 ^ 2)
    = 4 ^ 0 ^ 0
    = 4
    """
    result = 0
    for num in nums:
        result ^= num
    return result


# Demo
print(single_number([4, 1, 2, 1, 2]))  # 4
print(single_number([2, 2, 1]))        # 1

3. Find Missing Number

def missing_number(nums: list) -> int:
    """
    Array contains 0 to n, one number is missing. Find it.
    
    LeetCode 268: Missing Number
    
    Time: O(N)
    Space: O(1)
    
    Idea: XOR all numbers [0..n] with all array elements.
    Duplicates cancel, missing number remains.
    """
    n = len(nums)
    result = n  # Start with n (since indices are 0 to n-1)
    
    for i in range(n):
        result ^= i ^ nums[i]
    
    return result


# Demo
print(missing_number([3, 0, 1]))        # 2
print(missing_number([0, 1]))           # 2
print(missing_number([9,6,4,2,3,5,7,0,1]))  # 8

4. Find Two Non-Duplicate Numbers

def single_number_iii(nums: list) -> list:
    """
    Find two numbers that appear only once.
    All others appear exactly twice.
    
    LeetCode 260: Single Number III
    
    Time: O(N)
    Space: O(1)
    
    Idea:
    1. XOR all → xor = a ^ b (the two singles)
    2. Find rightmost set bit in xor
       (This bit is different between a and b)
    3. Partition numbers by this bit
    4. XOR each partition → Get a and b separately
    """
    # Step 1: XOR all numbers = a ^ b
    xor = 0
    for num in nums:
        xor ^= num
    
    # Step 2: Find rightmost set bit
    # This bit differs between a and b
    diff_bit = xor & (-xor)  # Isolate rightmost 1
    
    # Step 3 & 4: Partition and XOR
    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num  # Numbers with this bit set
        else:
            b ^= num  # Numbers without this bit
    
    return [a, b]


# Demo
print(single_number_iii([1, 2, 1, 3, 2, 5]))  # [3, 5]

Advanced XOR Tricks

Find Element Appearing Once (Others Appear 3 Times)

def single_number_ii(nums: list) -> int:
    """
    Find the number appearing once. Others appear 3 times.
    
    LeetCode 137: Single Number II
    
    Time: O(N)
    Space: O(1)
    
    Idea: Use two variables to count bits modulo 3.
    """
    ones, twos = 0, 0
    
    for num in nums:
        # ones holds bits that appeared 1 time (mod 3)
        # twos holds bits that appeared 2 times (mod 3)
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    
    return ones


# Demo
print(single_number_ii([2, 2, 3, 2]))        # 3
print(single_number_ii([0, 1, 0, 1, 0, 1, 99]))  # 99

XOR of Range [0..n]

def xor_range(n: int) -> int:
    """
    Calculate 0 ^ 1 ^ 2 ^ ... ^ n in O(1).
    
    Pattern:
    n % 4 == 0 → n
    n % 4 == 1 → 1
    n % 4 == 2 → n + 1
    n % 4 == 3 → 0
    """
    remainder = n % 4
    if remainder == 0:
        return n
    elif remainder == 1:
        return 1
    elif remainder == 2:
        return n + 1
    else:
        return 0


def xor_range_l_r(L: int, R: int) -> int:
    """XOR of [L..R] = xor_range(R) ^ xor_range(L-1)"""
    return xor_range(R) ^ (xor_range(L-1) if L > 0 else 0)


# Demo
print(xor_range(5))        # 0^1^2^3^4^5 = 1
print(xor_range_l_r(3, 5)) # 3^4^5 = 2

Production Code

# HPN Engineering Standard
# Implementation: XOR Utilities

from typing import List, Tuple, Optional
from functools import reduce


class XORUtils:
    """Production-ready XOR utilities."""
    
    @staticmethod
    def find_single(nums: List[int]) -> int:
        """Find element appearing once (others twice)."""
        return reduce(lambda x, y: x ^ y, nums)
    
    @staticmethod
    def find_missing(nums: List[int], n: int) -> int:
        """Find missing number in [0..n]."""
        result = n
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result
    
    @staticmethod
    def find_two_singles(nums: List[int]) -> Tuple[int, int]:
        """Find two elements appearing once."""
        xor = reduce(lambda x, y: x ^ y, nums)
        diff_bit = xor & (-xor)
        a = b = 0
        for num in nums:
            if num & diff_bit:
                a ^= num
            else:
                b ^= num
        return (a, b)
    
    @staticmethod
    def xor_range(L: int, R: int) -> int:
        """XOR of [L..R] in O(1)."""
        def f(n):
            rem = n % 4
            if rem == 0: return n
            if rem == 1: return 1
            if rem == 2: return n + 1
            return 0
        return f(R) ^ (f(L-1) if L > 0 else 0)
    
    @staticmethod
    def count_bits_diff(a: int, b: int) -> int:
        """Count different bits between a and b (Hamming distance)."""
        xor = a ^ b
        count = 0
        while xor:
            count += 1
            xor &= (xor - 1)  # Clear lowest set bit
        return count


# ============================================
# ENCRYPTION: SIMPLE XOR CIPHER
# ============================================

def xor_encrypt(plaintext: bytes, key: bytes) -> bytes:
    """
    Simple XOR cipher (repeating key).
    
    ⚠️ NOT SECURE for production! Educational only.
    Real encryption uses AES, ChaCha20, etc.
    """
    key_len = len(key)
    return bytes([p ^ key[i % key_len] for i, p in enumerate(plaintext)])


def xor_decrypt(ciphertext: bytes, key: bytes) -> bytes:
    """XOR cipher is symmetric: encrypt = decrypt."""
    return xor_encrypt(ciphertext, key)


# Demo
if __name__ == "__main__":
    print("=== XOR Utilities ===")
    
    # Single number
    nums = [4, 1, 2, 1, 2]
    print(f"Single in {nums}: {XORUtils.find_single(nums)}")
    
    # Missing number
    nums = [0, 1, 3, 4, 5]
    print(f"Missing in [0..5] - {nums}: {XORUtils.find_missing(nums, 5)}")
    
    # Hamming distance
    print(f"Hamming(1, 4): {XORUtils.count_bits_diff(1, 4)}")  # 2
    
    # Encryption demo
    print("\n=== XOR Cipher Demo ===")
    message = b"Hello, HPN!"
    key = b"secret"
    encrypted = xor_encrypt(message, key)
    decrypted = xor_decrypt(encrypted, key)
    print(f"Original:  {message}")
    print(f"Encrypted: {encrypted.hex()}")
    print(f"Decrypted: {decrypted}")

XOR Cheat Sheet

Problem	Pattern	Complexity
Single number (others ×2)	reduce(^, nums)	O(N)
Single number (others ×3)	Bit counting mod 3	O(N)
Two singles	Partition by differing bit	O(N)
Missing in [0..n]	n ^ 0 ^ 1 ^ ... ^ all elements	O(N)
XOR of [L..R]	f(R) ^ f(L-1)	O(1)
Hamming distance	popcount(a ^ b)	O(log max)

💡 HPN's Rule

"Thấy 'appears once/twice', 'missing number', 'no extra space' → XOR ngay. Self-inverse là key."