LeetCode 刷题

异或是一个数学运算符，英文为 exclusive OR，缩写成 XOR。异或的数学符号为 $\bigoplus$，计算机符号为「XOR」。如果二进制数 a 和 b 的同位置的值不相同，则该位置的结果为 1，反之为 0。

异或也叫半加运算

异或也叫半加运算，其运算法则相当于 不带进位的二进制加法，如 $0 \bigoplus 0=0, 1 \bigoplus 0=1, 0 \bigoplus 1=1, 1 \bigoplus 1=0$，这些法则与加法是相同的，如 $0+0=0, 1+0=1, 0+1=1, 1+1=(1)0$，只是不带进位，所以异或常被认作不进位加法。

异或运算性质

1. 归零律：任何数与自身异或都等于 0，即 $a \bigoplus a=0$
2. 恒等律：任何数与 0 异或都等于其本身，即 $a \bigoplus 0=a$
3. 交换律：即 $a \bigoplus b = b \bigoplus a$
4. 结合律：即 $a \bigoplus b \bigoplus c = a \bigoplus (b \bigoplus c) = (a \bigoplus b) \bigoplus c$
5. 自反性：对给定的数 b，用同样的运算因子 a 作两次异或运算后仍得到 b 本身，即 $a \bigoplus b \bigoplus a = b$

异或运算应用

交换两个数

若需要交换两个 整形变量 的值，除了借用中间变量进行交换外，还可以利用异或的自反性，仅使用两个变量进行交换，如：

1
2
3
4
5

void swap(int *a, int *b) {
    (*a) = (*a)^(*b);  // a1 = a^b
    (*b) = (*a)^(*b);  // b = (a^b)^b = a
    (*a) = (*a)^(*b);  // a = (a^b)^a = b
}

找出重复的数

假设一个集合中有 $n$ 个数，范围为 $[1, n-1]$，其中有 $n - 2$ 个互不相同的数，有一个数重复一次，设计一个 $O(n)$ 时间复杂度，$O(1)$ 空间复杂度的算法，找出这个数。

推导：

1. 假设不包含重复的第二个数的所有数的异或的结果为 $1 \bigoplus2 \bigoplus ... \bigoplus (n-1) = T$；
2. 那么，包含第二个重复的数的所有数的异或结果为 $1 \bigoplus2 \bigoplus ... \bigoplus (n-1) \bigoplus x = T \bigoplus x$。

通过自反性可以得出这个重复的数为 $T \bigoplus (T \bigoplus x) = x$。这里利用的异或的自反性，同时需要具备一个前置条件，就是：我们需要知道集合中都出现过哪些数，这样才能求出序号 1 的结果。

例如，下面的代码中，数组 nums[n] 存储着 $[1, n-1]$ 区间中的所有数，但只有一个数是重复的数。

1
2
3
4
5
6
7
8
9
10

int find_duplicate(int nums[], int n) {
    int res = 0;
    for (int i = 0; i < n; i++) {  // 所有数异或
        res ^= nums[i];  // T^x
    }
    for (int i = 1; i < n; i++) {  // 所有不重复的数异或
        res ^= i;  // res := (T^x)^T
    }
    return res;
}

找出不成对的一个数

LeetCode 习题：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数。

思路：使用异或运算的归零律、恒等律和交换律，将数组中的所有数异或求结果——所有出现偶数次的数的异或的结果是 0；再异或上那个出现奇数次的数，最终结果就是 0 异或 x，即那个不成对的数 x。

1
2
3
4
5
6
7

int singleNumber(int* nums, int numsSize){
    int res = 0;
    for (int i = 0; i < numsSize; i++) {
        res ^= nums[i];
    }
    return res;
}

找出不成对的两个数

LeetCode 习题：一个数组存放若干整数，两个不同的数出现了奇数次，其余数均出现偶数次，找出这两个出现奇数次的数。

假设这两个出现奇数次的数为 x 和 y：

1. 按照上述方法，将所有数做异或，计算出 x 和 y 或后的结果 z；
2. 在异或中，同位置的值不同则结果为 1。基于此，可以找到 z 的二进制中最右侧的那个 1（假设 x 的二进制在同位置为 1），然后丢弃左侧的二进制数；
3. 再次遍历数组，跳过那个同位置不为 1 的数（即 y），这就等价于数组是「成对的数中有且仅有一个不成对的数」，即找到了一个不成对的数（这里为 x）；
4. 另一个数 y 便是：x^(x^y)，即 x^z。

序号 2 中，当然也可能跳过成对的数，但没关系，因为这个数不会跳过一个、保留一个，就当少了一对成对的数，不会对找出那个不成对的数有影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int* singleNumber(int* nums, int numsSize, int* returnSize){
    int *ans = (int *)malloc(2 * sizeof(int));
    long xor = 0, lsb = 0;  // 防止溢出风险
    for (int i = 0; i < numsSize; ++i) {
        xor ^= 1LL * nums[i];
    }
    lsb = xor & (~xor + 1);
    ans[0] = 0, ans[1] = 0;
    for (int i =0; i < numsSize; ++i) {
        if ((nums[i] & lsb) != 0) {
            ans[0] ^= nums[i];
        }
    }
    ans[1] = xor ^ ans[0];
    (*returnSize) = 2;
    return ans;
}

是如何计算上述序号 2 中的那个二进制数的呢？

一个整数 x 与(~x+1)进行按位与运算的结果是将 x 的最右边的 1 保留下来，其他位都置为 0。这个操作通常用于获取 x 的最右边的 1 所代表的值，也可以称为获取 x 的最低有效位（LSB）。
举个例子，假设 x 的二进制表示为 10110100，那么 ~x 的二进制表示为 01001011，然后再加上 1，得到 (~x+1) 的二进制表示为 01001100。最后，将 x 与(~x+1)进行按位与运算，得到的结果就是 00000100，即 x 的最右边的 1 所代表的值为 4。

参考资料：

1. https://www.cnblogs.com/jasonkoo/articles/2760411.html