C++异或运算及其应用

什么是异或运算？

异或运算是一种二进制运算，用符号^表示。其规则是：两个二进制相同，结果为0；两个二进制不同，结果为1。比如：

1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1
0 ^ 0 = 0

此外，异或运算还有一个非常有用的性质，即相同的数异或结果为0，任何数异或0结果为该数本身。比如：

1 ^ 1 ^ 1 ^ 1 ^ 1 = 0
2 ^ 0 = 2

异或运算的应用

1. 交换两个变量的值

假设有两个整数a和b，我们要交换它们的值，可以使用如下代码：

a ^= b;
b ^= a;
a ^= b;

运用异或运算的上述代码实现了两个数的交换。

2. 判断奇偶性

对于任何一个整数，如果它的二进制表示的最后一位为1，那么它是奇数，否则它是偶数。因此，我们可以使用以下代码来判断一个数的奇偶性：

if (n & 1) {
    // n是奇数
} else {
    // n是偶数
}

3. 查找出现一次的数

在一个数组中，所有数都出现了两次，只有一个数出现了一次，要求找出这个数。我们可以使用异或运算，遍历数组中的每一个数，依次异或起来，最终的结果就是出现一次的那个数。因为出现两次的数异或起来的结果为0，不会影响最终结果。

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < nums.size(); i++) {
        ans ^= nums[i];
    }
    return ans;
}

4. 求解缺失的数

在一个从1到n的整数数组中，其中有一个数缺失，求出缺失的数。我们可以使用异或运算。

首先，我们可以将1到n的所有数异或起来，然后依次异或数组中的每一个数，最终得到的结果就是缺失的那个数。因为相同的数异或结果为0，所以剩余的就是缺失的数。

int missingNumber(vector<int>& nums) {
    int ans = 0;
    for (int i = 1; i <= nums.size(); i++) {
        ans ^= i;
    }
    for (int i = 0; i < nums.size(); i++) {
        ans ^= nums[i];
    }
    return ans;
}

总结

通过本文，我们了解了什么是异或运算，以及它的一些常用应用，包括交换两个变量的值、判断奇偶性、查找出现一次的数、求解缺失的数等。在实际编码中，掌握异或运算的应用能够提高代码的效率及可读性。