异或的妙用（C语言）

按位异或 是在二进制位上的运算：

一句话概括，就是 同为0，异为1。
0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1

异或有何用？有妙用。有何妙用？有以下妙用。

首先来回顾一下异或的运算性质：

0 ^ n = n
n ^ n = 0
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)
其中 a, b, c, n 均为整数。

将上面转换为文字就是：

0 与任何整数异或，结果都是原来的整数
任何整数跟自身异或的结果都是 0
异或运算满足交换律
异或运算满足结合律

题目一

题目来源（力扣）：消失的数字

题目描述：
数组 nums 包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

示例 1：
输入：[3,0,1]
输出：2

示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8

int missingNumber(int* nums, int numsSize){
    
    int x = 0;
    for(int i = 0; i <= numsSize; i++)
    {
    
        x ^= i;
    }

    for(int i = 0; i < numsSize; i++)
    {
    
        x ^= nums[i];
    }

    return x;
}

代码说明：
第一个循环结束后，x = 0 ^ 1 ^ 2 ^ 3 ^ … ^ n .
第二个循环结束后，x 就是缺的那个数

比如示例 1：
第一个循环结束后，x = 0 ^ 1 ^ 2 ^ 3 .
第二个循环结束后，x = 0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 = 2 .

题目二

题目来源（力扣）：数组中数字出现的次数

题目描述：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    int ret = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        ret ^= nums[i]; 
    }
	 //上面的循环结束后，ret 的值是两个只出现一次的数字异或的结果
	 // ret 的二进制位上为 1 的位，就是两个数在这个位上是不同的
	 //比如 ret = 0101 ^ 1001 = 1100 ，也就是说两个数不同的位是从右向左数的第3、4位
	 
    int m = 1;    //用 m 来找出 ret 的二进制位中从右向左的第一个为 1 的位
    //不会是死循环，因为 ret 是两个不同的数字异或的结果，其二进制位中至少有一位是1. 
    while((ret & m) == 0)  
    {
     
        m <<= 1;
    }
    //此时的 m 只有一位是1，那一位所在的位置正是ret从右向左数的第一个为1的位
    //依靠 m 的这个为1的位分别把数组元素分为两组：一组是在这个位上为0的，另一组是在这个位上为1的.
    //出现两次的数字必然分到同一组
    //也就是说下面的几步能够分离出两个只出现一次的数
    int a = 0, b = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        if((nums[i] & m) == 0)
            a ^= nums[i];
        else
            b ^= nums[i];
    }
    
    int* retArr = (int*)malloc(sizeof(int)*2);
    retArr[0] = a;
    retArr[1] = b;
    *returnSize = 2;
    return retArr;
}

注：按位运算符（ & 、^ 、 | ）的优先级比 == 和 != 的优先级要低，因此想要先按位运算再判断等还是不等，要给按位运算套上一层括号才行。

如果不知道异或运算的性质，是很难想到题目的解决是与异或有关的，或者说根本想不到。就算知道异或运算的性质，也很难一下子想出来。只有做题做多了，才有如此思路。

更多文章
大数相加（C语言）
合并两个有序数组（C语言）
阶乘后的零（C语言）
调整数组顺序使奇数位于偶数前面（C语言）