XOR Tricks — Phép toán đối xứng và ứng dụng

Hãy tưởng tượng bạn đang vận hành một hệ thống phân tán gồm 500 node, mỗi ngày truyền hàng triệu gói tin. Làm thế nào để phát hiện một gói tin bị hỏng trong dòng dữ liệu khổng lồ đó mà không cần lưu trữ toàn bộ lịch sử? Câu trả lời nằm ở một phép toán tưởng chừng đơn giản nhất trong bộ công cụ bitwise: XOR.

Trong thực tế, XOR checksum được dùng rộng rãi — từ RAID 5 (khôi phục dữ liệu khi một ổ đĩa chết) đến TCP/IP (kiểm tra tính toàn vẹn gói tin), và cả trong các thuật toán mật mã dòng (stream cipher). Sức mạnh của XOR không đến từ độ phức tạp, mà đến từ tính chất đại số đặc biệt: bất kỳ giá trị nào XOR với chính nó đều trả về 0, và XOR với 0 trả về chính nó. Chỉ hai tính chất này thôi đã mở ra hàng loạt kỹ thuật giải bài toán trong O(n) thời gian và O(1) bộ nhớ.

Bài viết này sẽ đưa bạn từ nền tảng đại số XOR, qua các bài toán kinh điển trên LeetCode, đến XOR basis — công cụ đại số tuyến tính trên trường hữu hạn GF(2) dành cho competitive programming nâng cao.

Bức tranh tư duy

Hãy nghĩ về XOR như một công tắc đèn (light switch). Bật một lần → đèn sáng. Bật lần nữa → đèn tắt, về đúng trạng thái ban đầu. Đó chính là bản chất self-inverse — tính chất quan trọng nhất của XOR.

Bảng chân trị XOR (⊕):
┌───────┬───────┬─────────┐
│   A   │   B   │  A ⊕ B  │
├───────┼───────┼─────────┤
│   0   │   0   │    0    │  ← Giống nhau → 0
│   0   │   1   │    1    │  ← Khác nhau  → 1
│   1   │   0   │    1    │  ← Khác nhau  → 1
│   1   │   1   │    0    │  ← Giống nhau → 0
└───────┴───────┴─────────┘

Self-inverse (công tắc đèn):
  A ⊕ B ⊕ B = A ⊕ 0 = A
  ┌─────┐      ┌─────┐      ┌─────┐
  │  5  │ ⊕ 3 →│  6  │ ⊕ 3 →│  5  │  ← Trở về giá trị gốc!
  └─────┘      └─────┘      └─────┘

Tính giao hoán & kết hợp:
  a ⊕ b ⊕ c = c ⊕ a ⊕ b = b ⊕ c ⊕ a
  → Thứ tự không quan trọng, chỉ cần "ai XOR ai"

Một cách hình dung khác: XOR chính là phép cộng trong hệ nhị phân không nhớ (addition modulo 2). Mỗi bit hoạt động độc lập — bit thứ i của kết quả chỉ phụ thuộc vào bit thứ i của hai toán hạng. Tính chất này biến XOR thành phép toán song song hoàn hảo trên phần cứng: tất cả 64 bit được xử lý đồng thời trong một chu kỳ xung nhịp.

Cốt lõi kỹ thuật

Bốn tính chất đại số cơ bản

Mọi kỹ thuật XOR đều xây dựng trên bốn tính chất sau:

#	Tính chất	Công thức	Ý nghĩa thực tế
1	Self-inverse	`a ⊕ a = 0`	Phần tử trùng tự triệt tiêu
2	Identity	`a ⊕ 0 = a`	XOR với 0 giữ nguyên giá trị
3	Commutative	`a ⊕ b = b ⊕ a`	Thứ tự không ảnh hưởng
4	Associative	`(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)`	Nhóm tùy ý khi tính

C++PythonJavaGo

cpp

#include <iostream>
#include <cassert>

void demonstrateXorProperties() {
    int a = 42, b = 17, c = 99;

    // Self-inverse: a ^ a = 0
    assert((a ^ a) == 0);

    // Identity: a ^ 0 = a
    assert((a ^ 0) == a);

    // Commutative: a ^ b = b ^ a
    assert((a ^ b) == (b ^ a));

    // Associative: (a ^ b) ^ c = a ^ (b ^ c)
    assert(((a ^ b) ^ c) == (a ^ (b ^ c)));

    std::cout << "Tat ca tinh chat XOR da duoc xac minh.\n";
}

python

def demonstrate_xor_properties():
    a, b, c = 42, 17, 99

    # Self-inverse: a ^ a = 0
    assert (a ^ a) == 0

    # Identity: a ^ 0 = a
    assert (a ^ 0) == a

    # Commutative: a ^ b = b ^ a
    assert (a ^ b) == (b ^ a)

    # Associative: (a ^ b) ^ c = a ^ (b ^ c)
    assert ((a ^ b) ^ c) == (a ^ (b ^ c))

    print("Tất cả tính chất XOR đã được xác minh.")

java

public class XorProperties {
    public static void demonstrate() {
        int a = 42, b = 17, c = 99;

        // Self-inverse: a ^ a = 0
        assert (a ^ a) == 0;

        // Identity: a ^ 0 = a
        assert (a ^ 0) == a;

        // Commutative: a ^ b = b ^ a
        assert (a ^ b) == (b ^ a);

        // Associative: (a ^ b) ^ c = a ^ (b ^ c)
        assert ((a ^ b) ^ c) == (a ^ (b ^ c));

        System.out.println("Tat ca tinh chat XOR da duoc xac minh.");
    }
}

package main

import "fmt"

func demonstrateXorProperties() {
	a, b, c := 42, 17, 99

	// Self-inverse: a ^ a = 0
	if (a ^ a) != 0 {
		panic("self-inverse failed")
	}
	// Identity: a ^ 0 = a
	if (a ^ 0) != a {
		panic("identity failed")
	}
	// Commutative: a ^ b = b ^ a
	if (a ^ b) != (b ^ a) {
		panic("commutative failed")
	}
	// Associative: (a ^ b) ^ c = a ^ (b ^ c)
	if ((a ^ b) ^ c) != (a ^ (b ^ c)) {
		panic("associative failed")
	}
	fmt.Println("Tat ca tinh chat XOR da duoc xac minh.")
}

Tìm phần tử xuất hiện 1 lần — Single Number (LeetCode 136)

Bài toán: Mảng gồm n phần tử, mỗi phần tử xuất hiện đúng 2 lần trừ một phần tử xuất hiện 1 lần. Tìm phần tử đó trong O(n) thời gian, O(1) bộ nhớ.

Nguyên lý: XOR toàn bộ mảng. Các cặp trùng tự triệt tiêu (a ⊕ a = 0), phần tử lẻ còn lại.

C++PythonJavaGo

cpp

#include <vector>

int singleNumber(const std::vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}
// singleNumber({4, 1, 2, 1, 2}) → 4

python

from functools import reduce
from operator import xor

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums)

# single_number([4, 1, 2, 1, 2]) → 4

java

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
    // singleNumber(new int[]{4, 1, 2, 1, 2}) → 4
}

func singleNumber(nums []int) int {
	result := 0
	for _, num := range nums {
		result ^= num
	}
	return result
}
// singleNumber([]int{4, 1, 2, 1, 2}) → 4

Tìm phần tử thiếu — Missing Number (LeetCode 268)

Bài toán: Mảng chứa n số phân biệt trong khoảng [0, n], thiếu đúng một số. Tìm số đó.

Nguyên lý: XOR tất cả chỉ số 0..n với tất cả phần tử. Các cặp (index, value) trùng nhau tự triệt tiêu, còn lại là số thiếu.

C++PythonJavaGo

cpp

#include <vector>

int missingNumber(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    int result = n; // khởi tạo bằng n vì index chỉ chạy 0..n-1
    for (int i = 0; i < n; ++i) {
        result ^= i ^ nums[i];
    }
    return result;
}
// missingNumber({3, 0, 1}) → 2

python

def missing_number(nums: list[int]) -> int:
    n = len(nums)
    result = n  # index chỉ chạy 0..n-1, cần XOR thêm n
    for i, val in enumerate(nums):
        result ^= i ^ val
    return result

# missing_number([3, 0, 1]) → 2

java

public class MissingNumber {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int result = n;
        for (int i = 0; i < n; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
    // missingNumber(new int[]{3, 0, 1}) → 2
}

func missingNumber(nums []int) int {
	n := len(nums)
	result := n
	for i, val := range nums {
		result ^= i ^ val
	}
	return result
}
// missingNumber([]int{3, 0, 1}) → 2

Tìm 2 phần tử xuất hiện 1 lần — Single Number III (LeetCode 260)

Bài toán: Mảng có đúng hai phần tử xuất hiện 1 lần, còn lại xuất hiện 2 lần. Tìm cả hai.

Nguyên lý:

XOR toàn bộ → được x = a ⊕ b
Lấy bit phân biệt: diff = x & (-x) — bit thấp nhất mà a và b khác nhau
Chia mảng thành 2 nhóm theo bit đó, XOR mỗi nhóm để tách a và b

C++PythonJavaGo

cpp

#include <vector>
#include <utility>

std::pair<int, int> singleNumberIII(const std::vector<int>& nums) {
    int xorAll = 0;
    for (int num : nums) xorAll ^= num;

    // Bit thấp nhất khác nhau giữa a và b
    int diffBit = xorAll & (-xorAll);

    int a = 0, b = 0;
    for (int num : nums) {
        if (num & diffBit) a ^= num;
        else               b ^= num;
    }
    return {a, b};
}
// singleNumberIII({1, 2, 1, 3, 2, 5}) → {3, 5}

python

def single_number_iii(nums: list[int]) -> tuple[int, int]:
    xor_all = 0
    for num in nums:
        xor_all ^= num

    diff_bit = xor_all & (-xor_all)

    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
    return a, b

# single_number_iii([1, 2, 1, 3, 2, 5]) → (3, 5)

java

public class SingleNumberIII {
    public static int[] singleNumberIII(int[] nums) {
        int xorAll = 0;
        for (int num : nums) xorAll ^= num;

        int diffBit = xorAll & (-xorAll);

        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & diffBit) != 0) a ^= num;
            else                      b ^= num;
        }
        return new int[]{a, b};
    }
    // singleNumberIII(new int[]{1, 2, 1, 3, 2, 5}) → [3, 5]
}

func singleNumberIII(nums []int) (int, int) {
	xorAll := 0
	for _, num := range nums {
		xorAll ^= num
	}

	diffBit := xorAll & (-xorAll)

	a, b := 0, 0
	for _, num := range nums {
		if num&diffBit != 0 {
			a ^= num
		} else {
			b ^= num
		}
	}
	return a, b
}
// singleNumberIII([]int{1, 2, 1, 3, 2, 5}) → (3, 5)

XOR của dãy [0..n] trong O(1)

Quan sát chu kỳ 4 của 0 ⊕ 1 ⊕ ... ⊕ n:

n % 4 == 0  →  n
n % 4 == 1  →  1
n % 4 == 2  →  n + 1
n % 4 == 3  →  0

Để tính XOR đoạn [L..R]: xorRange(R) ⊕ xorRange(L - 1).

C++PythonJavaGo

cpp

int xorUpTo(int n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        default: return 0;
    }
}

int xorRange(int L, int R) {
    return xorUpTo(R) ^ (L > 0 ? xorUpTo(L - 1) : 0);
}
// xorRange(3, 7) = 3^4^5^6^7 = 7

python

def xor_up_to(n: int) -> int:
    remainder = n % 4
    if remainder == 0: return n
    if remainder == 1: return 1
    if remainder == 2: return n + 1
    return 0

def xor_range(L: int, R: int) -> int:
    return xor_up_to(R) ^ (xor_up_to(L - 1) if L > 0 else 0)

# xor_range(3, 7) → 7

java

public class XorRange {
    public static int xorUpTo(int n) {
        switch (n % 4) {
            case 0: return n;
            case 1: return 1;
            case 2: return n + 1;
            default: return 0;
        }
    }

    public static int xorRange(int L, int R) {
        return xorUpTo(R) ^ (L > 0 ? xorUpTo(L - 1) : 0);
    }
    // xorRange(3, 7) → 7
}

func xorUpTo(n int) int {
	switch n % 4 {
	case 0:
		return n
	case 1:
		return 1
	case 2:
		return n + 1
	default:
		return 0
	}
}

func xorRange(L, R int) int {
	r := xorUpTo(R)
	if L > 0 {
		r ^= xorUpTo(L - 1)
	}
	return r
}
// xorRange(3, 7) → 7

XOR Basis — Đại số tuyến tính trên GF(2)

Trường GF(2) (Galois Field of 2 elements) chỉ có hai phần tử {0, 1} với phép cộng là XOR và phép nhân là AND. Khi ta coi mỗi số nguyên là một vector trong không gian GF(2)^k (k = số bit), các khái niệm đại số tuyến tính — cơ sở (basis), hạng (rank), kết hợp tuyến tính — đều áp dụng được.

XOR Basis (hay Linear Basis) là tập vector nhỏ nhất sao cho mọi giá trị XOR có thể tạo từ tập gốc đều biểu diễn được qua basis. Kích thước tối đa của basis là k (số bit).

Thuật toán Gaussian Elimination trên GF(2) — xây dựng basis:

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>

struct XorBasis {
    static constexpr int MAXBIT = 62; // cho số 64-bit
    long long basis[63] = {};

    // Chèn val vào basis. Trả về true nếu val độc lập tuyến tính.
    bool insert(long long val) {
        for (int i = MAXBIT; i >= 0; --i) {
            if (!((val >> i) & 1)) continue;
            if (!basis[i]) {
                basis[i] = val;
                return true; // val mở rộng không gian
            }
            val ^= basis[i]; // khử bit cao nhất
        }
        return false; // val đã biểu diễn được từ basis hiện tại
    }

    // Truy vấn XOR lớn nhất có thể tạo từ basis
    long long queryMax() const {
        long long result = 0;
        for (int i = MAXBIT; i >= 0; --i) {
            result = std::max(result, result ^ basis[i]);
        }
        return result;
    }

    // Truy vấn XOR lớn nhất khi kết hợp với giá trị khởi tạo
    long long queryMaxWith(long long initVal) const {
        long long result = initVal;
        for (int i = MAXBIT; i >= 0; --i) {
            result = std::max(result, result ^ basis[i]);
        }
        return result;
    }
};

python

class XorBasis:
    MAXBIT = 62  # cho số 64-bit

    def __init__(self):
        self.basis = [0] * (self.MAXBIT + 1)

    def insert(self, val: int) -> bool:
        """Chèn val vào basis. Trả về True nếu val độc lập tuyến tính."""
        for i in range(self.MAXBIT, -1, -1):
            if not ((val >> i) & 1):
                continue
            if not self.basis[i]:
                self.basis[i] = val
                return True  # val mở rộng không gian
            val ^= self.basis[i]  # khử bit cao nhất
        return False  # val đã biểu diễn được từ basis hiện tại

    def query_max(self) -> int:
        """XOR lớn nhất có thể tạo từ basis."""
        result = 0
        for i in range(self.MAXBIT, -1, -1):
            result = max(result, result ^ self.basis[i])
        return result

    def query_max_with(self, init_val: int) -> int:
        """XOR lớn nhất khi kết hợp với giá trị khởi tạo."""
        result = init_val
        for i in range(self.MAXBIT, -1, -1):
            result = max(result, result ^ self.basis[i])
        return result

java

public class XorBasis {
    private static final int MAXBIT = 62;
    private long[] basis = new long[MAXBIT + 1];

    /** Chèn val vào basis. Trả về true nếu val độc lập tuyến tính. */
    public boolean insert(long val) {
        for (int i = MAXBIT; i >= 0; i--) {
            if (((val >> i) & 1) == 0) continue;
            if (basis[i] == 0) {
                basis[i] = val;
                return true;
            }
            val ^= basis[i];
        }
        return false;
    }

    /** XOR lớn nhất có thể tạo từ basis. */
    public long queryMax() {
        long result = 0;
        for (int i = MAXBIT; i >= 0; i--) {
            result = Math.max(result, result ^ basis[i]);
        }
        return result;
    }

    /** XOR lớn nhất khi kết hợp với giá trị khởi tạo. */
    public long queryMaxWith(long initVal) {
        long result = initVal;
        for (int i = MAXBIT; i >= 0; i--) {
            result = Math.max(result, result ^ basis[i]);
        }
        return result;
    }
}

package main

const MaxBit = 62

type XorBasis struct {
	basis [MaxBit + 1]int64
}

// Insert chèn val vào basis. Trả về true nếu val độc lập tuyến tính.
func (xb *XorBasis) Insert(val int64) bool {
	for i := MaxBit; i >= 0; i-- {
		if (val>>i)&1 == 0 {
			continue
		}
		if xb.basis[i] == 0 {
			xb.basis[i] = val
			return true
		}
		val ^= xb.basis[i]
	}
	return false
}

// QueryMax trả về XOR lớn nhất có thể tạo từ basis.
func (xb *XorBasis) QueryMax() int64 {
	var result int64
	for i := MaxBit; i >= 0; i-- {
		if result^xb.basis[i] > result {
			result ^= xb.basis[i]
		}
	}
	return result
}

// QueryMaxWith trả về XOR lớn nhất khi kết hợp với initVal.
func (xb *XorBasis) QueryMaxWith(initVal int64) int64 {
	result := initVal
	for i := MaxBit; i >= 0; i-- {
		if result^xb.basis[i] > result {
			result ^= xb.basis[i]
		}
	}
	return result
}

Phân tích thuật toán: Với mỗi số val, ta duyệt từ bit cao nhất xuống. Nếu gặp bit i bật mà basis[i] chưa có giá trị, ta gán basis[i] = val — tức val độc lập tuyến tính với các vector đã có. Nếu basis[i] đã có, ta khử bit i bằng cách XOR val với basis[i], rồi tiếp tục xuống bit thấp hơn. Nếu val bị khử về 0, nó phụ thuộc tuyến tính — không bổ sung thêm chiều nào cho không gian.

Thực chiến

Kịch bản 1: Phát hiện lỗi dữ liệu trong hệ thống phân tán

Trong kiến trúc RAID 5, dữ liệu được chia thành các strip trên nhiều ổ đĩa, kèm một strip parity bằng XOR toàn bộ strip dữ liệu. Khi một ổ đĩa hỏng, dữ liệu được khôi phục bằng cách XOR các strip còn lại với parity.

Nguyên lý tương tự áp dụng cho XOR checksum khi truyền gói tin:

C++PythonJavaGo

cpp

#include <vector>
#include <cstdint>
#include <stdexcept>

uint32_t computeXorChecksum(const std::vector<uint32_t>& blocks) {
    uint32_t checksum = 0;
    for (uint32_t block : blocks) {
        checksum ^= block;
    }
    return checksum;
}

// Mô phỏng mất 1 block và khôi phục
uint32_t recoverBlock(const std::vector<uint32_t>& surviving,
                      uint32_t parity) {
    uint32_t xorSurvivors = 0;
    for (uint32_t block : surviving) {
        xorSurvivors ^= block;
    }
    return xorSurvivors ^ parity; // block bị mất
}

// Ví dụ:
// blocks = {0xABCD, 0x1234, 0x5678}
// parity = 0xABCD ^ 0x1234 ^ 0x5678 = 0xF9A1
// Nếu mất block 0x1234:
// recover({0xABCD, 0x5678}, 0xF9A1)
//   = (0xABCD ^ 0x5678) ^ 0xF9A1 = 0x1234 ✓

python

def compute_xor_checksum(blocks: list[int]) -> int:
    checksum = 0
    for block in blocks:
        checksum ^= block
    return checksum

def recover_block(surviving: list[int], parity: int) -> int:
    """Khôi phục block bị mất từ các block còn lại + parity."""
    xor_survivors = 0
    for block in surviving:
        xor_survivors ^= block
    return xor_survivors ^ parity

# Ví dụ:
blocks = [0xABCD, 0x1234, 0x5678]
parity = compute_xor_checksum(blocks)  # 0xF9A1
lost = recover_block([0xABCD, 0x5678], parity)
assert lost == 0x1234  # Khôi phục thành công

java

public class XorChecksum {
    public static int computeXorChecksum(int[] blocks) {
        int checksum = 0;
        for (int block : blocks) {
            checksum ^= block;
        }
        return checksum;
    }

    public static int recoverBlock(int[] surviving, int parity) {
        int xorSurvivors = 0;
        for (int block : surviving) {
            xorSurvivors ^= block;
        }
        return xorSurvivors ^ parity;
    }

    // blocks = {0xABCD, 0x1234, 0x5678}
    // parity = 0xF9A1
    // recoverBlock({0xABCD, 0x5678}, 0xF9A1) → 0x1234
}

func computeXorChecksum(blocks []uint32) uint32 {
	var checksum uint32
	for _, block := range blocks {
		checksum ^= block
	}
	return checksum
}

func recoverBlock(surviving []uint32, parity uint32) uint32 {
	var xorSurvivors uint32
	for _, block := range surviving {
		xorSurvivors ^= block
	}
	return xorSurvivors ^ parity
}

// blocks := []uint32{0xABCD, 0x1234, 0x5678}
// parity := computeXorChecksum(blocks) // 0xF9A1
// lost := recoverBlock([]uint32{0xABCD, 0x5678}, parity)
// lost == 0x1234 ✓

Kịch bản 2: Maximum XOR Subarray — dùng XOR basis

Bài toán: Cho mảng a[0..n-1], tìm đoạn con liên tục a[l..r] sao cho a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r] đạt giá trị lớn nhất.

Nhận xét: Gọi prefix[i] = a[0] ⊕ a[1] ⊕ ... ⊕ a[i-1]. Khi đó a[l] ⊕ ... ⊕ a[r] = prefix[r+1] ⊕ prefix[l]. Bài toán trở thành: tìm hai giá trị prefix[i] và prefix[j] sao cho XOR của chúng lớn nhất. Dùng XOR basis giải trong O(n × k).

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>

long long maxXorSubarray(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return 0;

    // Xây prefix XOR
    std::vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] ^ a[i];
    }

    // Chèn tất cả prefix vào XOR basis
    // Với mỗi prefix[i], truy vấn max XOR với basis hiện tại,
    // rồi chèn prefix[i] vào basis.
    constexpr int MAXBIT = 30;
    long long basis[31] = {};
    long long ans = 0;

    for (int i = 1; i <= n; ++i) {
        // Truy vấn max XOR với prefix[i]
        long long cur = prefix[i];
        for (int b = MAXBIT; b >= 0; --b) {
            cur = std::max(cur, cur ^ basis[b]);
        }
        ans = std::max(ans, cur);

        // Chèn prefix[i] vào basis
        long long val = prefix[i];
        for (int b = MAXBIT; b >= 0; --b) {
            if (!((val >> b) & 1)) continue;
            if (!basis[b]) { basis[b] = val; break; }
            val ^= basis[b];
        }
    }
    return ans;
}
// maxXorSubarray({1, 2, 3, 4}) → 7  (đoạn [1,2,3] → 1^2^3 = 0, 
//   nhưng prefix trick cho kết quả 7 = prefix[4]^prefix[1] = 4^3 = 7)

python

def max_xor_subarray(a: list[int]) -> int:
    n = len(a)
    if n == 0:
        return 0

    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] ^ a[i]

    MAXBIT = 30
    basis = [0] * (MAXBIT + 1)
    ans = 0

    for i in range(1, n + 1):
        # Truy vấn max XOR với prefix[i]
        cur = prefix[i]
        for b in range(MAXBIT, -1, -1):
            cur = max(cur, cur ^ basis[b])
        ans = max(ans, cur)

        # Chèn prefix[i] vào basis
        val = prefix[i]
        for b in range(MAXBIT, -1, -1):
            if not ((val >> b) & 1):
                continue
            if not basis[b]:
                basis[b] = val
                break
            val ^= basis[b]

    return ans

# max_xor_subarray([1, 2, 3, 4]) → 7

java

public class MaxXorSubarray {
    public static long maxXorSubarray(int[] a) {
        int n = a.length;
        if (n == 0) return 0;

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ a[i];
        }

        int MAXBIT = 30;
        long[] basis = new long[MAXBIT + 1];
        long ans = 0;

        for (int i = 1; i <= n; i++) {
            long cur = prefix[i];
            for (int b = MAXBIT; b >= 0; b--) {
                cur = Math.max(cur, cur ^ basis[b]);
            }
            ans = Math.max(ans, cur);

            long val = prefix[i];
            for (int b = MAXBIT; b >= 0; b--) {
                if (((val >> b) & 1) == 0) continue;
                if (basis[b] == 0) { basis[b] = val; break; }
                val ^= basis[b];
            }
        }
        return ans;
    }
    // maxXorSubarray(new int[]{1, 2, 3, 4}) → 7
}

func maxXorSubarray(a []int) int64 {
	n := len(a)
	if n == 0 {
		return 0
	}

	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] ^ int64(a[i])
	}

	const MAXBIT = 30
	var basis [MAXBIT + 1]int64
	var ans int64

	for i := 1; i <= n; i++ {
		cur := prefix[i]
		for b := MAXBIT; b >= 0; b-- {
			if cur^basis[b] > cur {
				cur ^= basis[b]
			}
		}
		if cur > ans {
			ans = cur
		}

		val := prefix[i]
		for b := MAXBIT; b >= 0; b-- {
			if (val>>b)&1 == 0 {
				continue
			}
			if basis[b] == 0 {
				basis[b] = val
				break
			}
			val ^= basis[b]
		}
	}
	return ans
}
// maxXorSubarray([]int{1, 2, 3, 4}) → 7

Sai lầm điển hình

❌ Sai lầm 1: Nhầm XOR với OR hoặc AND

SAI:  Nghĩ rằng 1 ⊕ 1 = 1 (đây là OR, không phải XOR)
ĐÚNG: 1 ⊕ 1 = 0 — XOR trả 1 khi hai bit KHÁC nhau

SAI:  Dùng & thay ^ khi muốn phát hiện bit khác nhau
ĐÚNG: a ^ b cho ra bitmask với bit 1 tại mọi vị trí a và b khác nhau

❌ Sai lầm 2: XOR swap khi hai biến cùng địa chỉ bộ nhớ

SAI:
  a ^= b;  // Nếu a và b cùng trỏ đến 1 ô nhớ (alias)
  b ^= a;  // → a ^= a → a = 0 → MẤT DỮ LIỆU
  a ^= b;

ĐÚNG: Luôn kiểm tra a ≠ b trước khi swap, hoặc dùng biến tạm:
  if (&a != &b) { a ^= b; b ^= a; a ^= b; }
  // Tốt hơn: dùng std::swap(a, b) hoặc temp variable

❌ Sai lầm 3: Quên xử lý edge case mảng rỗng

SAI:
  def single_number(nums):
      return reduce(xor, nums)  # TypeError nếu nums rỗng!

ĐÚNG:
  def single_number(nums):
      if not nums:
          raise ValueError("Mảng không được rỗng")
      return reduce(xor, nums)

❌ Sai lầm 4: Sai thứ tự bit khi xây dựng XOR basis

SAI:  Duyệt từ bit 0 lên bit cao → basis không ở dạng echelon
      → queryMax() cho kết quả sai

ĐÚNG: LUÔN duyệt từ bit cao nhất xuống bit 0.
      Gaussian elimination trên GF(2) yêu cầu pivot từ hàng/bit cao nhất.

Under the Hood

XOR trong phần cứng

Ở mức cổng logic, XOR được thực thi bằng tổ hợp NAND/NOR gates hoặc trực tiếp bằng XOR gate (thường 6-8 transistor). Trên CPU hiện đại:

Lệnh XOR thực thi trong 1 chu kỳ xung nhịp (latency = 1, throughput = 1)
CPU 64-bit xử lý 64 bit song song trong một lệnh — không có carry propagation như phép cộng
XOR là một trong những lệnh rẻ nhất trên mọi kiến trúc (x86, ARM, RISC-V)
Compiler thường dùng xor eax, eax để gán 0 cho thanh ghi — nhanh hơn mov eax, 0

Bảng độ phức tạp

Kỹ thuật	Thời gian	Bộ nhớ	Ghi chú
Single Number (1 lẻ)	O(n)	O(1)	Tất cả khác xuất hiện 2 lần
Missing Number	O(n)	O(1)	Dãy [0..n] thiếu 1 phần tử
Single Number III (2 lẻ)	O(n)	O(1)	Chia nhóm bằng differing bit
XOR Range [L..R]	O(1)	O(1)	Chu kỳ 4
Xây XOR Basis	O(n × k)	O(k)	k = số bit (thường 30 hoặc 62)
Query Max từ Basis	O(k)	O(1)	Greedy từ bit cao
Max XOR Subarray	O(n × k)	O(n + k)	Prefix XOR + Basis
Hamming Distance	O(k)	O(1)	`popcount(a ^ b)`

Khi nào XOR tricks KHÔNG hiệu quả

Phần tử xuất hiện 3 lần: Self-inverse không triệt tiêu → cần đếm bit modulo 3 (LeetCode 137)
Cần biết giá trị cụ thể, không chỉ XOR: XOR chỉ cho thông tin bit-level, không khôi phục được từng phần tử riêng lẻ
Số âm với biểu diễn khác nhau: Cần cẩn thận với sign-extension trên các ngôn ngữ có kiểu dữ liệu signed/unsigned khác nhau
Bài toán cần thứ tự: XOR mất thông tin thứ tự (commutative) — không thể khôi phục dãy ban đầu

✅ Checklist triển khai

Checklist ghi nhớ

[ ] Self-inverse là nền tảng: a ⊕ a = 0 — mọi kỹ thuật XOR đều dựa trên tính chất này
[ ] XOR toàn mảng triệt tiêu phần tử trùng cặp, còn lại phần tử lẻ
[ ] Missing number: XOR indices [0..n] với elements → số thiếu còn lại
[ ] Tách 2 phần tử lẻ: tìm differing bit bằng xor & (-xor), chia nhóm
[ ] XOR range [0..n] có chu kỳ 4 → O(1) bằng n % 4
[ ] XOR basis xây bằng Gaussian elimination từ bit cao xuống bit thấp
[ ] insert() trả false = phần tử phụ thuộc tuyến tính với basis hiện tại
[ ] queryMax() greedy chọn bit cao nhất — giống tham lam trên hệ nhị phân
[ ] Max XOR Subarray = prefix XOR + basis, truy vấn online khi chèn prefix
[ ] XOR swap nguy hiểm khi hai biến cùng alias → luôn dùng std::swap hoặc temp
[ ] XOR không hoạt động cho phần tử lặp 3 lần → dùng bit counting mod 3
[ ] Compiler tối ưu xor reg, reg cho zero-init — hiểu hardware giúp viết code hiệu quả
[ ] Kiểm tra mảng rỗng trước khi reduce XOR — tránh runtime error
[ ] Hamming distance = popcount(a ⊕ b) — đếm bit 1 trong kết quả XOR

Bài tập luyện tập

Bài 1 — Foundation: Single Number

Đề bài: Cho mảng nums với mỗi phần tử xuất hiện 2 lần trừ một phần tử xuất hiện 1 lần. Tìm phần tử đó.

Ràng buộc: 1 ≤ nums.length ≤ 3 × 10⁴, -3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴

🧠 Quiz

Câu hỏi: Phương pháp nào tối ưu nhất (cả thời gian lẫn bộ nhớ) cho bài Single Number?

[ ] A. Sắp xếp mảng, duyệt cặp liền kề → O(n log n), O(1)
[x] B. XOR toàn bộ mảng → O(n), O(1)
[ ] C. Dùng HashMap đếm tần suất → O(n), O(n)
[ ] D. Dùng tập hợp (set), thêm/xóa → O(n), O(n)

Giải thích: Cả 4 phương pháp đều đúng, nhưng XOR cho O(n) thời gian và O(1) bộ nhớ — tối ưu nhất.

Lời giải tham khảo

C++PythonJavaGo

cpp

#include <vector>

int singleNumber(std::vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

python

from functools import reduce
from operator import xor

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums)

java

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) result ^= num;
        return result;
    }
}

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

Bài 2 — Intermediate: Tổng Hamming Distance (LeetCode 477)

Đề bài: Cho mảng nums, tính tổng Hamming distance giữa tất cả các cặp (nums[i], nums[j]) với i < j.

Ràng buộc: 1 ≤ nums.length ≤ 10⁴, 0 ≤ nums[i] ≤ 10⁹

Gợi ý: Thay vì duyệt O(n²) cặp, xét từng bit riêng. Tại bit thứ k, nếu có c số bật bit đó và n - c số tắt, thì đóng góp vào tổng là c × (n - c).

🧠 Quiz

Câu hỏi: Độ phức tạp tối ưu cho bài Tổng Hamming Distance?

[ ] A. O(n²) — duyệt mọi cặp
[ ] B. O(n² × 32) — duyệt mọi cặp, đếm bit
[x] C. O(n × 32) = O(n) — đếm bit 1 tại mỗi vị trí
[ ] D. O(n log n) — sắp xếp trước

Giải thích: Tại mỗi bit (32 bit), duyệt n số đếm bao nhiêu số có bit đó bật. Đóng góp = count × (n - count).

Lời giải tham khảo

C++PythonJavaGo

cpp

#include <vector>

int totalHammingDistance(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    int total = 0;
    for (int bit = 0; bit < 30; ++bit) {
        int count = 0; // số phần tử có bit này bật
        for (int num : nums) {
            count += (num >> bit) & 1;
        }
        total += count * (n - count);
    }
    return total;
}

python

def total_hamming_distance(nums: list[int]) -> int:
    n = len(nums)
    total = 0
    for bit in range(30):
        count = sum((num >> bit) & 1 for num in nums)
        total += count * (n - count)
    return total

java

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int total = 0;
        for (int bit = 0; bit < 30; bit++) {
            int count = 0;
            for (int num : nums) {
                count += (num >> bit) & 1;
            }
            total += count * (n - count);
        }
        return total;
    }
}

func totalHammingDistance(nums []int) int {
	n := len(nums)
	total := 0
	for bit := 0; bit < 30; bit++ {
		count := 0
		for _, num := range nums {
			count += (num >> bit) & 1
		}
		total += count * (n - count)
	}
	return total
}

Bài 3 — Advanced: Maximum XOR of Two Numbers (LeetCode 421)

Đề bài: Cho mảng nums, tìm giá trị lớn nhất của nums[i] XOR nums[j] với 0 ≤ i < j < n.

Ràng buộc: 1 ≤ nums.length ≤ 2 × 10⁵, 0 ≤ nums[i] ≤ 2³¹ - 1

Gợi ý: Chèn toàn bộ phần tử vào XOR basis, rồi queryMax(). Hoặc dùng Trie trên biểu diễn nhị phân.

Lời giải tham khảo (XOR Basis)

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>

int findMaximumXOR(const std::vector<int>& nums) {
    constexpr int MAXBIT = 30;
    long long basis[31] = {};

    for (int num : nums) {
        long long val = num;
        for (int b = MAXBIT; b >= 0; --b) {
            if (!((val >> b) & 1)) continue;
            if (!basis[b]) { basis[b] = val; break; }
            val ^= basis[b];
        }
    }

    long long ans = 0;
    for (int b = MAXBIT; b >= 0; --b) {
        ans = std::max(ans, ans ^ basis[b]);
    }
    return static_cast<int>(ans);
}

python

def find_maximum_xor(nums: list[int]) -> int:
    MAXBIT = 30
    basis = [0] * (MAXBIT + 1)

    for num in nums:
        val = num
        for b in range(MAXBIT, -1, -1):
            if not ((val >> b) & 1):
                continue
            if not basis[b]:
                basis[b] = val
                break
            val ^= basis[b]

    ans = 0
    for b in range(MAXBIT, -1, -1):
        ans = max(ans, ans ^ basis[b])
    return ans

java

class Solution {
    public int findMaximumXOR(int[] nums) {
        int MAXBIT = 30;
        long[] basis = new long[MAXBIT + 1];

        for (int num : nums) {
            long val = num;
            for (int b = MAXBIT; b >= 0; b--) {
                if (((val >> b) & 1) == 0) continue;
                if (basis[b] == 0) { basis[b] = val; break; }
                val ^= basis[b];
            }
        }

        long ans = 0;
        for (int b = MAXBIT; b >= 0; b--) {
            ans = Math.max(ans, ans ^ basis[b]);
        }
        return (int) ans;
    }
}

func findMaximumXOR(nums []int) int {
	const MAXBIT = 30
	var basis [MAXBIT + 1]int64

	for _, num := range nums {
		val := int64(num)
		for b := MAXBIT; b >= 0; b-- {
			if (val>>b)&1 == 0 {
				continue
			}
			if basis[b] == 0 {
				basis[b] = val
				break
			}
			val ^= basis[b]
		}
	}

	var ans int64
	for b := MAXBIT; b >= 0; b-- {
		if ans^basis[b] > ans {
			ans ^= basis[b]
		}
	}
	return int(ans)
}

XOR Tricks — Phép toán đối xứng và ứng dụng ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Bốn tính chất đại số cơ bản ​

Tìm phần tử xuất hiện 1 lần — Single Number (LeetCode 136) ​

Tìm phần tử thiếu — Missing Number (LeetCode 268) ​

Tìm 2 phần tử xuất hiện 1 lần — Single Number III (LeetCode 260) ​

XOR của dãy [0..n] trong O(1) ​

XOR Basis — Đại số tuyến tính trên GF(2) ​

Thực chiến ​

Kịch bản 1: Phát hiện lỗi dữ liệu trong hệ thống phân tán ​

Kịch bản 2: Maximum XOR Subarray — dùng XOR basis ​

Sai lầm điển hình ​

❌ Sai lầm 1: Nhầm XOR với OR hoặc AND ​

❌ Sai lầm 2: XOR swap khi hai biến cùng địa chỉ bộ nhớ ​

❌ Sai lầm 3: Quên xử lý edge case mảng rỗng ​

❌ Sai lầm 4: Sai thứ tự bit khi xây dựng XOR basis ​

Under the Hood ​

XOR trong phần cứng ​

Bảng độ phức tạp ​

Khi nào XOR tricks KHÔNG hiệu quả ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1 — Foundation: Single Number ​

Bài 2 — Intermediate: Tổng Hamming Distance (LeetCode 477) ​

Bài 3 — Advanced: Maximum XOR of Two Numbers (LeetCode 421) ​

Liên kết học tiếp ​

Nội bộ PENALGO ​

Thuật ngữ chính (Glossary) ​

Bài tập mở rộng trên LeetCode ​

XOR Tricks — Phép toán đối xứng và ứng dụng

Bức tranh tư duy

Cốt lõi kỹ thuật

Bốn tính chất đại số cơ bản

Tìm phần tử xuất hiện 1 lần — Single Number (LeetCode 136)

Tìm phần tử thiếu — Missing Number (LeetCode 268)

Tìm 2 phần tử xuất hiện 1 lần — Single Number III (LeetCode 260)

XOR của dãy [0..n] trong O(1)

XOR Basis — Đại số tuyến tính trên GF(2)

Thực chiến

Kịch bản 1: Phát hiện lỗi dữ liệu trong hệ thống phân tán

Kịch bản 2: Maximum XOR Subarray — dùng XOR basis

Sai lầm điển hình

❌ Sai lầm 1: Nhầm XOR với OR hoặc AND

❌ Sai lầm 2: XOR swap khi hai biến cùng địa chỉ bộ nhớ

❌ Sai lầm 3: Quên xử lý edge case mảng rỗng

❌ Sai lầm 4: Sai thứ tự bit khi xây dựng XOR basis

Under the Hood

XOR trong phần cứng

Bảng độ phức tạp

Khi nào XOR tricks KHÔNG hiệu quả

Checklist ghi nhớ

Bài tập luyện tập

Bài 1 — Foundation: Single Number

Bài 2 — Intermediate: Tổng Hamming Distance (LeetCode 477)

Bài 3 — Advanced: Maximum XOR of Two Numbers (LeetCode 421)

Liên kết học tiếp

Nội bộ PENALGO

Thuật ngữ chính (Glossary)

Bài tập mở rộng trên LeetCode