异或运算的高级应用和Briankernighan算法

本篇文章主要回顾一下计算机的位运算，处理一些位运算的巧妙操作。

特别提醒：实现位运算要注意溢出和符号扩展等问题。

先看一个好玩的问题：

$Problem1 $ 黑白球概率问题

袋子里一共a个白球，b个黑球，每次从袋子里拿2个球，每个球每次被拿出的机会均等。如果拿出的是2个白球、或者2个黑球，那么就往袋子里重新放入1个白球，如果拿出的是1个白球和1个黑球，那么就往袋子里重新放入1个黑球，那么最终袋子里一定会只剩1个球，请问最终是黑球的概率是多少？用a与b来表示这个概率。

问题分析：

细心的同学会发现，袋子中的黑球每次要么取出2个，要么取出0个。所以如果袋子里的初始黑球个数是奇数的话，最后一个球一定是黑球，如果是偶数的话，最后一个球一定是白球。我们可以用异或运算来清晰地体现。

异或运算性质

[!NOTE]

1. 异或运算就是无进位相加。

2. 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终结果都是一个。

3. 0^n = n , n^n = 0

4. 整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和是x^y。【区间上异或和】

5. 通过异或运算来交换两个数（不用新开辟空间）

   a = a ^ b

   b = a ^ b

   a = a ^ b

   三行代码即可交换a 与 b

证明一下第4条性质：

​ 若 a^b=c ，则a = c^b， b = c^a。根据异或运算满足交换律与结合律，我们能得到：若一部分的异或和为y，另一部分的异或为x^y，则这两部分的整体异或和为x。

回到题目，我们把白球看成0，黑球看成1，根据题目条件，拿出1个白球和1个黑球则放入一个黑球，用数学数字表示就是 $0,1~ -> 1 $，那么全部条件如下：
$$\begin{gathered} 0,1->1 \\ 1,0->1 \\ 0,0->0 \\ 1,1->0 \end{gathered}$$
很显然，这就是个异或运算嘛。从袋子里拿出两个数进行异或运算，再把异或运算的结果放入袋子，所以这个题目我们可以抽象成如下情况：

数集中有a个0，b个1，每次从数集中拿出两个数进行异或，再将异或的结果放回到数集中【经过一次这种操作，数集中的数的个数会减1】，经过多次操作之后，最终得到一个数，请问这个数是1的概率？

一次这种操作是一次异或，多次异或放在一起就是异或和问题，异或和符合交换律与结合律，所以最终结果只和1的个数有关，若1的个数为偶

数，最终结果为0，若1的个数为奇数，最终结果为1。

$Problem2$ 不用任何判断语句和比较操作，返回两个数的最大值

问题分析：

这个题目有意思，既然不用判断和比较，那就只能利用计算操作了。但是涉及到比大小，那必然要作差，取两个int型数据$a,b$，作差得$c=a-b$，如果$c>0$，则$a$大，如果$c<0$，则$b$大。不用能判断，那我们考虑一下位运算：

如果$c<0$，则$c$的符号位为1，对其进行无符号位移（向右移动31位），最终得到结果1。

如果$c>0$，则$c$的符号位为0，对其进行无符号位移（向右移动31位），最终得到结果0。

我们记较大值为$max$，$c<0$时，$max=a\ast 0+b\ast 1$，$c>0$时，$max=a\ast 1+b\ast 0$。现在我们把无符号位移之后的$c$与$a,b$ 两个数的系数的关系表建立起来：

c	A	B
1	0	1
0	1	0

很容易看出，B = C，A = C ^1。【注意，这里的C是$c$向右无符号位移31位得到的结果】

详细代码：

//不用任何判断语句和比较操作，返回两个数的最大值
unsigned int sign(unsigned int C) {return C >> 31; //C最后只有0和1两个结果
}
//与1做异或
int flip(unsigned int C) {return C ^ 1;
}
int getMax(int a, int b) {int c = a - b;//强制转换为无符号整数再右移unsigned int C = static_cast<unsigned int>(c);int returnA = flip(sign(C));int returnB = sign(C);return a * returnA + b * returnB;
}

其实这个代码存在一定风险，因为int c = a - b可能会导致溢出情况，同学们可自行思考没有溢出问题的代码，实在暂时没想出来的的可以私信我【手动狗头】。

$Problem3$ 找到缺失的数字

现在存在一个长度为n的数组，也就是说这个数组里有n个数，但是小明只提取出了n-1个数，现在想知道缺失的那个数的大小是多少？

问题分析：

这个问题比较简单，很多同学会第一时间想到哈希表，先遍历这个长度为n的数组，建立数字本身：此数字出现的次数哈希表，之后再遍历一次数组，每遍历一个数字，都在哈希表中减少一次这个数字出现的次数，遍历结束之后，出现次数为-1的那个数字就是缺失的数。

但是这种方法比较复杂，需要遍历两遍数组，还要建立哈希表，查询哈希表，更改哈希表，不仅浪费时间，空间也消耗巨大【建哈希表需要空间】。所以我们想借助一下此篇文章强调的位运算的思想来找更简单的解法。

重新回顾一下这个题目，数组的数字情况有三种：完整的数组，缺失的一个数字，缺失一个数字之后的数组。由此可以联想到异或运算的第四条性质【区间上的异或和】，我们记数组中的数字如下：
$$a_1,a_2,a_3,a_4,...,a_n$$
记缺失的数字为$a_i$，则剩余的数字为
$$a_1,...,a_{i-1},a_{i+1},...,a_n$$
数组中所有数字的异或和为
$$A=a_1\wedge a_2\wedge ...\wedge a_n$$
缺失了一个数字之后的数组中所有数字异或和为
$$B=a_1\wedge ...\wedge a_{i-1}\wedge a_{i+1}\wedge ...\wedge a_n$$
异或运算满足结合律，所以我们很容易知道：
$$A=B\wedge a_i$$
所以
$$a_i=A\wedge B$$
以上过程就能直接利用异或运算的性质找出缺失的数字了。

我们直接给出代码：

int findMissingNumber(vector<int> Numbers,vector<int> missingNumbers) {int A = 0;  //存储所有数字异或和for (int i : Numbers) {A = A ^ i;}int B = 0;for (int i : missingNumbers) {B = B ^ i;}return A ^ B;
}

$Problem4$ 找到出现了奇数次的数

数组中有1种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数。

问题分析：

出现偶数次的数有什么特殊之处呢？我们知道$n\wedge n=0$，所以偶数次的数对最终异或和并没有贡献，只有奇数次的数会对异或和有影响，题目中说明了奇数次的数只有一种，所有最终异或和就是出现奇数次的数本身。

很简单的，以下是解题代码：

int findOddTimesNumber(vector<int> Numbers) {int A = 0;  //存储所有数字异或和for (int i : Numbers) {A = A ^ i;}return A;
}

$BrianKernighan$算法

$BrianKernighan$算法主要是用来获得二进制中最右侧的1，看下面这个例子你就明白了：

现在有一个二进制数（用8个位的数来作例子）$01101000$，我们想得到最右侧的1，也就是$00001000$，该进行哪些步骤呢？先简单思考下：

得到最右侧的1，也就是最右侧的1前面的数全部变为0(0->0,1->0)，该怎么变呢？现在我们来尝试一下：

• 与自身作任何操作（与（且），或，异或）都不能使得$01101000$变成$00001000$，即使与0作与运算能使$0110$变成$0000$，但是后面的$1000$也会被影响成$0000$。
• 先对数取反得到$10010111$，这时前面的$1001$和$0110$做与运算就可以得到$0000$，但是后面的$1000$和$0111$做与运算变成了$0000$，我们得想办法不让$1000$发生变化。
• 由于$1000$是最右侧的1，所以$1000$取反的结果$0111$只比$1000$小1，因此我们把$10010111$加上1再和原来的数$01101000$做与运算，最后会得到$00001000$。

总结一下：

1. 先对原来的数取反，以便最右侧1之前的数和取反之后的数做与运算能得到$\mathrm{0...0}$。
2. 对于最右侧1以及之后的二进制数 $\mathrm{100..0}$，取反之后的数比$\mathrm{100..0}$小1，我们对取反之后的数加上1就可以得到$\mathrm{100..0}$,相同两个数求与自然得到$\mathrm{100..0}$。

所以$Briankernighan$算法：对原来的数取反并加1，再和原来的数做与运算，最终得到最右侧的1。

int Briankernighan(int a) {return a & (~a + 1);
}

$Problem5$ 返回2种出现了奇数次的数

数组中有两种数出现了奇数次，其他的数都出现了偶数次，返回这2种出现了奇数次的数。

问题分析：

这道题算是$Problem4$的拓展，我们记数组中的所有数为：
$$a_1,a_2,...,a_n$$
重复出现的记为1个数。

记2种出现了奇数次的数为$a_i,a_j$，根据$Problem4$，我们知道，数组中所有数（算上重复的数）的异或和为$a_i\wedge a_j$，但是我们要的是$a_i$与$a_j$，该怎么找呢？

已知$a_i\wedge a_j$是求不出来$a_i$和$a_j$的，比如二进制数$01001100$可以由$11110000,10111100$异或出来，也可以由$00001100,01000000$异或出来，但是我们发现，其中的某个1要么在$a_i$中，要么在$a_j$中，不可能同时出现在$a_i,a_j$中。借助上面的$BrianKernighan$ 算法，我们拿最右侧的1作为标志来区分$a_i,a_j$。

还是拿异或和为二进制数$01001100$作为例子，它的最右侧的1为$00000100$，我们从右往左数，第三位为1，这个第三位为1就是标志！！！

正如刚刚讨论的，要么$a_i$的第三位为1，要么$a_j$的第三位为1，但是分析到现在还是求不出$a_i,a_j$，现在我们考虑一下将所有数进行划分，很显然，原来的所有数也可以被划分为两部分：

​ 第三位为1的部分与第三位为0的部分，并且，每一部分都对应一个$a_i$或$a_j$。

对含有$a_i$的部分求异或和不就是$a_i$么，$a_j$同理。

详细代码：

pair<int,int> findTwoOddTimesNumbers(vector<int> Numbers) {int eorAll = 0; //a_i ^ a_jfor (int i : Numbers) {eorAll = eorAll ^ i;}int rightOne = Briankernighan(eorAll); //得到最右侧的1int eor1 = 0; //对应位置是0的数的异或和int eor2 = 0; //对应位置是1的数的异或和for (int i : Numbers) {if (i & rightOne == 0) {eor1 = eor1 ^ i;}}eor2 = eorAll ^ eor1;return { eor1, eor2 };
}