异或运算¶

定义¶

异或运算（XOR，通常用符号 $ \oplus $ 或 ^ 表示）是一种二元运算，仅当两个操作数不同（一个为真，一个为假）时结果为真（\(1\)），否则结果为假（\(0\)）。在二进制中，异或运算通常是 指按位异或，即分别对两个二进制串每一位进行比较，如果两位相同则结果为\(0\)，不同则结果为\(1\)。

在这里，笔者给出一份异或运算的真值表，方便读者理解：

在计算机科学中，异或运算常用于加密、错误检测和纠正等领域。

在数学和工程学中，常常用其他的逻辑运算符来表示异或算符。异或算符可以使用逻辑算符逻辑与 \(\land\) ，逻辑或 \(\lor\) 和逻辑非 \(\neg\) 表示为:

或者使用逻辑算符逻辑与 \(\land\) ，逻辑或 \(\lor\) 和逻辑非 \(\neg\) 的另一种形式表示为:

这两种形式分别对应于异或的 析取范式 和 合取范式 。

在编程语言中，异或运算通常用符号 ^ 表示。例如，在 C++ 中，a ^ b 表示对整数 a 和 b 进行按位异或操作，不要与幂运算混淆。

基本性质¶

异或运算具有许多重要的性质，这些性质使得它在算法设计中非常有用。

交换律¶

异或运算满足交换律，即对于任意两个数 \(a\) 和 \(b\)，都有：

这意味着一个连续的异或操作的顺序不影响结果。

结合律¶

异或运算满足结合律，即对于任意三个数 \(a\)、\(b\) 和 \(c\)，都有：

这意味着在进行多个异或操作时，可以任意调整括号的位置，而不影响最终结果。

归零律 (自反性)¶

异或运算具有归零律，即对于任意数 \(a\)，都有：

这意味着一个数与自身进行异或操作的结果总是\(0\)。

恒等律¶

异或运算具有恒等律，即对于任意数 \(a\)，都有：

这意味着一个数与\(0\)进行异或操作的结果总是该数本身。

逆元¶

异或运算的逆元是自身，即对于任意数 \(a\)，都有：

这意味着一个数与自身进行异或操作的结果总是\(0\)，结合恒等律可以得到：

因此可以通过异或操作来“撤销”之前的操作。

引申¶

异或运算在许多算法中都有重要应用，以下是一些常见的应用场景：

交换两个数¶

可以利用异或运算在不使用临时变量的情况下交换两个数的值。

int a = 5;
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;

找出只出现一次的数¶

在一个数组中，其他数字都出现两次，只有一个数字出现一次，可以利用异或运算找出这个数字。

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

当然，这段代码也可以扩展到找出只出现奇数次的数。

计算两个数的汉明距离¶

汉明距离是指两个数的二进制表示中不同位的数量，可以通过异或运算得到，其中__builtin_popcount()作用是统计二进制中1的数量。

int hamming_distance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

区间异或¶

在处理区间异或查询时，可以使用前缀异或数组来快速计算某个区间内的异或值。前缀异或数组的定义是：prefix_xor[i] 表示从数组开头到第 \(i\) 个元素的异或值，可以通过以下公式计算区间 \([l, r]\) 的异或值：

可以使用前缀异或数组来快速计算区间内的异或值。

vector<int> prefix_xor(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i++) {
    prefix_xor[i] = prefix_xor[i - 1] ^ nums[i - 1];
}