异或运算的骚操作
问题描述
先来个好玩的问题：
袋子里有 ( a ) 个白球、( b ) 个黑球。每次从袋子里拿出 2 个球，每个球被拿出的概率均等。如果拿出的是 2 个白球或 2 个黑球，那么就往袋子里重新放入 1 个白球；如果拿出的是 1 个白球和 1 个黑球，那么就往袋子里重新放入 1 个黑球。
那么最终袋子里一定会只剩 1 个球，请问最终的球是黑球的概率是多少？用 ( a ) 和 ( b ) 表达这个概率。
答案
黑球的数量如果是偶数，最终是黑球的概率是 ( 0\% )。
黑球的数量如果是奇数，最终是黑球的概率是 ( 100\% )。
完全和白球的数量无关。
异或运算性质
- 异或运算就是无进位相加；
- 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个
- 0⊕n=n，n⊕n=0
- 整体异或和如果是x，整体中某个部分的异或如果是y，那么剩下部分的异或和是x⊕y
这些结论最重要的就是 1)，所有其他结论都可以由这个结论推导得到。
其中第 4) 相关的题目最多，利用区间上异或和的性质。
Nim 博弈也是和异或运算相关的算法。
题目分析
由于
取出两个白球，则放入一个白球;
取出两个黑球，则放入一个白球;
取出一个白球和一个黑球，则放入一个黑球。
可以抽象为：
0⊕0=0;
1⊕1=0;
0⊕1=1。
由此可以得到答案：
最终的球是黑球的概率只与放入的黑球数量有关，黑球为偶数，则最终球是黑球的概率为 0%；黑球为奇数，则最终球是黑球的概率为 100%。
题目1 交换两个数
1
2
3
4
5
6
7
8
9
// 记初始a为a1, b为b1
a = a ^ b;
// a == a1 ^ b1
b = a ^ b;
// b == (a1 ^ b1) ^ b1 == a1
a = a ^ b;
// a == (a1 ^ b1) ^ ((a1 ^ b1) ^ b1) == b1
运行上段代码后，a，b的值互换了。
注意: a与b必须要在两个内存地址上，否则会将a，b刷为0。
1
2
3
4
5
6
7
8
9
int nums[2] = {1, 2};
int a = nums[0], b = nums[1];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
ERROR: nums[0] = 0, nums[1] = 0
因为当i == j时，nums[i]被刷为0了。
题目2 返回两个数的最大值
不使用if语句和>、<运算符，求两个数的最大值。
1
2
3
4
5
6
int sign(int x){
return ((x >> 31) & 1) ^ 1; // 符号位(0为负数,1为非负)
}
int getMax1(int a, int b){
return sign(a - b) == 1 ? a : b; // 返回符号位为1的数
}
缺点：当a = INT_MIN，b = INT_MAX等情况时，会溢出。
修正：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getMax2(int a, int b) {
int c = a - b;
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
// 判断AB符号是不是不一样
int diffAB = sa ^ sb; // 符号位不同（一样为0，不同为1）
int sameAB = diffAB ^ 1; // 符号位相同（一样为1，不同为0）
int returnA = diffAB * sa + diffAB * sc; // 符号位不同，返回A
int returnB = returnA ^ 1; // 符号位相同，返回B
return a * returnA + b * returnB; // 合并返回值
}
题目3 找到缺失的数字
查找数字范围为[0, n]的数组中缺失的数据，要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findMissing(vector<int>& nums){
int ans = 0;
int n = nums.size();
// 得到nums数组的异或和，nums数组中有n个数字（缺失了一个），范围在[0, n]
for(int i = 0; i < n; i++){
ans ^= nums[i];
}
// 得到0~n的异或和，共n + 1个数字
for(int i = 0; i <= n; i++){
ans ^= i;
}
// ans即为缺失的数字
return ans;
}
题目4 找唯一的出现奇数次的数
1
2
3
4
5
6
7
int singleNumber(vector<int> &nums) {
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
ans ^= nums[i];
}
return ans;
}
题目5 找唯二的出现奇数次的数
前提算法：
提取出二进制状态最右侧的1的状态
即从
0111100中得到
0000100
Brian Kernighan 算法：n & ((~n) + 1) 或 n & -n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> singleNumber(vector<int> &nums) {
long long eor1 = 0, eor2 = 0; // ll防溢出
for (auto num : nums) {
eor1 ^= num;
}
// eor1即为a^b
long long diff = eor1 & -eor1; // Brian Kernighan 算法
for (auto num : nums) {
if ((num & diff) == diff) {
eor2 ^= num;
}
}
// 此时eor2即为 a 或 b
int a = eor2;
int b = eor1 ^ eor2;
return {a, b};
}
⚠️注意：位运算的优先级比==低，因此必须在(num & diff)左右加上括号！
题目6 找唯一的出现次数少于m的数
数组中只有一种数出现了少于m次，其他数都出现了m次。 求这种数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int singleNumber(vector<int>& nums) {
int ans = 0;
int cnt1[32] = {0}; // ⚠️：记得初始化为0
for(auto num : nums){
for(int i = 0; i < 32; i++){
if(num & (1 << i)){
cnt1[i]++;
}
}
}
for (int i = 0; i < 32; i++){
if(cnt1[i] % m){
ans |= (1 << i);
}
}
return ans;
}
