位运算算法篇：异或运算
位运算算法篇：异或运算
那么在介绍我们的异或运算之前，那么我们首先引入一个问题，我们现在从一个盒子里面取球，这个盒子只有黑和白两种颜色的球，那么每次只能从盒子里取出两个球，那么如果取出的两个球颜色相同的话，那么会往盒子里放一个黑球，如果颜色相反的话，会往盒子里放入一个白球，那么问我们这个盒子里最终剩余的一个球的颜色是什么？
那么我先不会给出该问题的一个答案，那么读者可以自行思考一下这个题的答案是什么，当然这个题和我们今天所讲的内容：异或运算有关，这题是一个陷阱题，答案以及解析会在文末结语位置处公布，那么我们废话不多说，就让我们进入正文，来领略一下异或运算的骚操作！
1.原理
(1).无进位相加
那么我们在上一篇位运算文章中介绍了我们的异或运算，我们知道异或运算的规则就是相同为0，相异为1，那么很多人会经常搞忘这个异或运算的规则，那么这里我们有一个更容易理解异或运算的方式，那就是无进位相加。
那么所谓的无进位相加这里我们该怎么理解呢，那么我们知道对于二进制的加法运算来说，我们对应的二进制位相加，采取的是逢二进一的原则，那么如果对应的二进制位是两个1相加，那么会产生一个一的进位到下一位上去，那么这里的无进位相加就指的是两个1相加不会产生进位，那么就是无进位相加。
所以当两个二进制序列做异或运算的时候，我们可以将这两个二进制序列理解为做一个无进位相加的加法运算，那么计算得到的结果和和按照我们异或运算的相同为0，相异为一的结果是一样，比如我们以8个二进制位的异或运算来举例：
10011001 ^ 11110101
10011001
+11110101
——————
01101100
(2).异或运算的性质
那么有了我们这里无进位相加的一个理解，那么我们就能理解异或运算的性质了，异或运算满足交换律以及结合律，
那么a^ b ^ c ^ d= a^ c ^ b ^ d =(a ^ c) ^ d ^ b= (a^ (c ^ b) ^d)
那么对于我们这里a，b，c，d四个数做异或运算，无论你怎么使用交换律或者结合律改变我们的运算次序，那么结果都是一样的，那么这里我们可以用无进位相加来理解，我们这里a,b,c,d四个数做异或运算，就可以转换为它们四个数做一个无进位相加的加法运算，那么无进位相加的加法运算，我们知道每一个二进制位的状态，只和当前这4个数中对应的二进制位为1的数量有关，如果该二进制位1的数量为偶数，那么根据无进位相加，我们知道，最终异或运算的结果中该二进制位为0，反之如果该二进制位为奇数，那么异或运算的结果中该二进制位一定为0，与顺序是没有任何关系的
a ^ b ^ c ^ d (以4为二进制位为例，每一例是一个数对应的二进制序列，每一行是对应二进制位进行无进位相加）
0 0 1 1 = 0
1 0 1 0 = 0
1 1 1 1 = 0
0 0 0 0 = 0
那么我们异或运算的性质除了交换律以及结合律，那么还有一个技巧，那么我们知道我们异或运算的本质其实就是无进位相加，那么我们两个相同的数异或的结果一定是0，因为我们该数的对应二进制位1相加后会得到0，所以异或后的结果一定是0，那么同理我们0与任何数异或的结果也一定是任何数本身：
a^a=0
0^a=a
那么这个技巧可以推广到如果偶数个相同的数进行异或，那么异或和为0，那么0与偶数个相同的数的异或和为0，奇数个数相同的数异或和为该数，证明就是我们的无进位相加。
那么我们有了这个技巧以及异或运算的交换律和结合律之后，我们可以应用到一个题目上：现在有一个序列整体的一个异或和，假设该异或和为c，那么我们其中该序列一部分的异或和b，那么我们要求另一部分的异或和a，那么我们这里怎么得到呢？
那么方法也很简单，利用刚才的技巧，那么我们有整体序列的异或和，整体的异或和可以由这两部分的异或和再进行异或得到：
c=a^b
然后利用刚才的技巧，再来异或已知的异或和b：
c ^ b=a ^ b ^ b=a ^ (b ^ b) =a ^ 0 =a
2.应用
那么我们的应用部分我们分几道题来解析
(1).交换两个数
题目：假设我们现在有两个已知的数a和b，那么我们要交换a和b的值。
我们这个题目想必你一定不陌生，那么我们这个题目交换两个数的技巧有很多，第一个是最为常见的技巧，也就是c语言时期所教的临时变量法，那么我们可以定义一个临时变量，将一个数的值赋给临时变量，然后通过临时变量来转换。
那么这里我们还可以用异或运算来解决，核心就是我们原理部分所讲述的技巧，自己与自己的异或为0,0与任何数异或的结果为任何数
代码部分实现：
#include<iostream>
using namespace std;
int main()
{
int a=10,b=20;
cout<<"before: "<<a<<" "<<b<<endl;
a=a^b;
b=a^b;
a=a^b;
cout<<"After: "<<a<<" "<<b<<endl;
return 0;
}
(2).找到缺失的数
题目：题目会给出一个连续的区间，但是我们这个连续的区间缺失了1个数，我们要找到这个数(例如题目给出的区间是[0,10]，其中缺了9，那么我们要写出一份代码找到该数)
那么这个题的常规思路估计就是用哈希表的方式然后遍历一遍该数组找到缺失的数字，但是我们这里可以用更为高效的异或运算来实现，
那么思路就是核心还是利用我们异或的技巧，我们首先先将我们的连续区间的所有数给异或得到一个异或和然后定义一个变量来保存，然后再定义另一个变量遍历我们的数组中的每个元素得到一个该数组所有元素的异或和，然后两个异或和在异或，那么相同的数会被消去，只留下缺失的数。
代码部分实现：
#include<iostream>
using namespace std;
int main()
{
int arr[]={1,2,3,4,5,6,7,8,10};
int ret=0;
for(int i=1;i<=10;i++)
{
ret^=i;
}
int ret2=0;
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
{
ret2^=arr[i];
}
ret=ret^ret2;
cout<<ret<<endl;
return 0;
}
(3).比较两个数的大小
那么我们比较两个数的大小我们知道我们通常可以用if else的条件判断语句来比较大小，那么这里我们比较大小我们可以用我们的位运算来实现，其中不调用任何条件判断语句。
那么我们怎么只通过位运算来实现并且不调用我们的条件判断语句呢？
那么原理如下：
我们知道我们比较两个数的大小，我们可以采取我们的作差法，那么假设我们要比较我们两个数a和b的大小，那么我们首先可以作差a-b，然后判断差值，如果该差值为非负数，那么意味着a大，如果为负数，那么意味着b大，那么我们知道我们一个有符号整形的数的最高位表示符号位，其中0代表正数，1代表负数，那么我们可以利用右移运算符将我们的符号位移动到最低位然后来与1进行一个与运算来判断符号位从而确定正负，然后我们接着我们定义一个变量returnA来接收，那么returnB就是returnA的互斥取反，如果a-b为负数，那么returnA为1，returnB为0，正数则相反，然后我们知道我们非负数返回a，负数返回b。
那么我们可以通过表达式a* returnA+b* returnB来实现
代码部分实现：
#include<iostream>
using namespace std;
void getmax(int a,int b)
{
int c=a-b;
int returnB=(c>>31)&1;
int returnA=1-returnB;
int res=a*returnA+b*returnB;
cout<<"the max is:"<<res<<endl;
return;
}
int main()
{
int a=20,b=10;
getmax(a,b);
a=10,b=30;
getmax(a,b);
return 0;
}
但是我们上面那个思路有一个明显的缺陷，那么就是我们如果是一个正数减去负数的话，那么会有溢出的风险，那么我们就得改善，那么我们得添加一个逻辑，那么我们首先先判断我们两个数是否同号以及异号，那么我们可以用我们的位运算来实现，那么我们将两个数我们的最高位的符号位右移到最低位然后分别用sa以及sb保存a和b的符号位然后来进行异或运算，结果用一个diff变量来保存，然后same则是它的互斥条件，也就是说diff是1，same则是0，那么两数异号，反之同理，那么我们接下来还是用上面的方式假设他们是同号的话，用上面的方式得到差值的正负，那么returnA就是返回a的条件，那么返回a的话就是a，b异号，a是非负数，以及a，b同号差值是非负数，用sc来保存差值的符号位。
那么returnA=diff * sa+same *sc
returnB=~ returnA
代码部分实现：
#include<iostream>
using namespace std;
void getmax(int a,int b)
{
int sa=(a>>31)&1;
int sb=(a>>31)&1;
int c=a-b;
int sc=(c>>31)&1;
int diff=sa^sb;
int same=1-diff;
int returnA=diff*(1-sa)+same*(1-sc);
int returnB=1-returnA;
int res=a*returnA+b*returnB;
cout<<"the max is:"<<res<<endl;
return;
}
int main()
{
int a=20,b=10;
getmax(a,b);
a=10,b=-30;
getmax(a,b);
return 0;
}
(4).找到出现为奇数次的数
题目：题目会给我们一个序列，那么这个序列中有一个数的出现的次数是奇数次，其余都是偶数次，那么找到该出现奇数次的数
那么这道题的思路的话，我们还是利用异或运算的性质，将得到我们整体序列的异或和，然后该异或和就是奇数次的数的值
代码部分：
#include<iostream>
using namespace std;
int main()
{
int arr[]={1,1,1,2,2,3,3,4,4,5,5};
int ret=0;
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
{
ret^=arr[i];
}
cout<<ret<<endl;
return 0;
}
(5）找到两个不同出现奇数次的数
题目：先有一个序列，那么该序列中有两个数出现了奇数次，其余数都是出现偶数次，那么找出现奇数次的这两个数
此题的思路我们还是首先可以得到该序列的异或和，但是至于我们这里偶数部分的数全部被消去，那么假设出现奇数次的这两个数为a和b，那么整体序列异或和的结果就是a^b
那么这里这题思路的核心就是我们得知道我们这里我们a和b是两个不同的数，如果是两个相同的数，那么奇数与奇数相加就是偶数了，那么a与b是两个值不同的数，那么既然值不同，我们知道他们所对应的二进制序列一定不完全相同，那么他们的异或运算的结果一定不为0，因为两个数不相同，那么我们异或运算得到的结果必然有一个二进制位有1，那么异或运算的本质是无进位相加，那么必然是结果的1对应的两个相加的二进制位分别是0和1，那么我们a和b必然可以以该二进制位是否为1来分为两类。
那么我们可以用布莱德算法提取结果最右侧的1，然后将我们这个序列分为两类，一类是二进制为1，一类是该二进制位不为1，那么我们a和b必然在这其中一类中，我们在将该二进制为1的得到一个异或和，那么偶数的消去，该异或和的结果要么就是a或者b，那么剩下的思路就很清晰了
代码部分：
#include<iostream>
using namespace std;
int main()
{
int arr[]={1,1,1,2,2,3,3,4,4,5,5,7,7,7};
int ret=0;
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
{
ret^=arr[i];
}
int check=ret&(-ret);
int ret2=0;
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
{
if((check&arr[i])!=0)
{
ret2^=arr[i];
}
}
ret=ret^ret2;
cout<<ret<<" "<<ret2<<endl;
return 0;
}
(6).找到出现次数小于m次的数
题目：先有一个序列，该序列中有一个数出现的次数小于m次，其余的数都出现了m次，我们要得到该数。
那么这里我们知道其他数出现了m次，那么我们假设该数是int类型，那么有32为，我们统计每一个二进制位为1的数量，那么每一个二进制位为1的位上，那么该二进制位为1的数量一定是m的倍数，因为二进制位为0，一定是m的倍数，然后再原来的基础上加了m个1，那么该二进制位的1的个数也一定满足是m的倍数，那么如果我们现在有了出现次数少于m的数，那么该数对应二进制位为1的话，那么我们加上该数对应二进制位为1的数量，那么它一定不能不是m的倍数，那么我们就可以根据这个情况，来得到我们出现次数少于m次的数二进制位为1的位置从而确地其二进制序列。
#include <iostream>
#include <vector>
using namespace std;
int findNumberAppearingLessThanMTimes(const vector<int>& nums, int m) {
int result = 0;
int bitCount[32] = {0}; // 用于统计每一位上1的个数
// 遍历每一位
for (int i = 0; i < 32; ++i) {
for (int num : nums) {
// 检查num的第i位是否为1
if (num & (1 << i)) {
bitCount[i]++;
}
}
// 如果第i位上1的个数不是m的倍数，则结果的第i位为1
if (bitCount[i] % m != 0) {
result |= (1 << i);
}
}
return result;
}
int main() {
vector<int> nums = {2, 2, 3, 3, 3, 4, 4, 4, 4}; // 示例序列
int m = 3; // 其他数出现的次数
int result = findNumberAppearingLessThanMTimes(nums, m);
cout << "The number appearing less than " << m << " times is: " << result << endl;
return 0;
}
3.结语
那么回答之前开篇的问题，我们发现我们取球的规则和异或运算的规则是一致的，那么我们可以把黑球看成1，白球看成0，那么我们取球的所有过程就可以看成将这个盒子里的所有球进行一个异或运算，那么最终剩的球的颜色就只与黑球的个数也就是奇数个还是偶数个有关，那么这就是本篇文章的全部内容，那么希望你能有所收获，我会持续更新，希望你能多多关注与支持！
