异或运算的骚操作，由浅入深拿捏一类型的题

🚀前言

大家好啊！这里是阿辉又整的关于位运算的干货，不得不说异或运算真的6，话不多说来开始今天的学习吧！！！

🚀异或运算的基本用法

大家都知道异或运算是针对二进制位的运算，两个数异或运算是将两个数的对应二进制位进行比较，若这两个数的对应的二进制位相等则取0，不相等则取1（其实也是对应位相加的结果进位舍去，所以异或运算也叫做无进位相加）

相信各位都见过利用异或运算进行两个数的交换的骚操作，其实这个交换利用了三条异或运算的性质：

• a ^ a = 0相同的数字异或的结果是0
• 0 ^ a = a0和其他数字异或的结果仍为该数字
• 异或运算满足交换律和结合律

//无需临时变量交换两个变量
int a = 5, b = 6;
a = a ^ b;
b = a ^ b;//此时a的值为a ^ b ,所以b = a ^ b ^ b = a
a = a ^ b;//此时b的值为a,a的值还是a ^ b ,所以a = a ^ b ^ a = b,完成交换

下面介绍关于异或运算的相关题目，由浅入深，阿辉这波属实是干货满满❤️

🚀一组数中一种数出现了奇数次，其他种数出现了偶数次，找出这个数

阿辉直接上代码：

//一组数中一种数出现了奇数次，其他种数出现了偶数次，找出这个数
int oddnum(int a[], int len) {
  int ans = 0;
  for (int i = 0; i < len; i++) {
    ans ^= a[i];//偶数次的数异或结果为0，最后ans中留下的就是奇数次的数
  }
  return ans;
}

阿辉这里稍微解释一下，上面异或运算的基本使用不是介绍了异或运算的三个性质吗，利用这三个性质，我们将数组中所有的数全部异或，偶数次的数因为是偶数所以异或结果是0，而奇数次的数自然就留下来了

🚀一组数中有两种数出现了奇数次，其他种数出现了偶数次，求这两个数

这道题相当于上面一道题的变式，其实这道题阿辉当时并没有想出来，也是看了题解才会的

话不多说，这阿辉先上代码：

array<int, 2> townum(int a[], int len) {
  array<int, 2> ans = {};//作为返回值
  int one = 0;//记录其中一个数
  int another = 0;//记录另一个数
  int eor = 0;
  for (int i = 0; i < len; i++) {
    eor ^= a[i];//记录这两种数的异或结果
  }
  int endone = eor & (~eor + 1);//拿到了这俩个数异或结果最末尾的1
  for (int i = 0; i < len; i++) {//根据这个1，对原数组分组
    if ((a[i] & endone) != 0)
      one ^= a[i];//得到其中一个数
  }
  another = eor ^ one;//得到另一个数
  //下面这两步操作相当于把俩个数加进答案数组作为返回值返回
  ans.fill(one);
  ans.fill(another);
  return ans;
}

虽然这是cpp的代码但是C语言的铁子完全可以看得懂，对于array<int,2>你就把它当作一种类型就行了，相当于长度为2的int类型的数组，返回值也是这个

代码解读

比如对于这样一个数组：1 1 1 1 2 2 3 4 4 4 4 5 6 6 6 6

他们所有进行异或，最后的结果一定是3 ^ 5，因为只有3和5是出现奇数次

3异或5的值的二进制形式一定还有一个1，因为他俩不想等，所以异或结果一定有1（二进制形式下）这个1是怎么来的呢？这一位上有1只能说明3和5在这一位上不相等，一个是1一个是0，其实对于3异或5的结果的二进制形式下的任何一个1都能将3和5区分开（这里不懂为什么的接着看）这里我们为了方便就取最低位的1（也就是最右侧的1）

怎么取到最右侧的1呢？将这个数与上它的相反数即可（为什么讲完这题阿辉会详细解释）

然后根据这个1可以将原来的数组划分成两部分，一部分中只含有一个出现奇数次的数，然后对任意一部分的数全体异或即可得到其中一个出现奇数次的数，然后再将一开始原数组整体异或的结果和得到的一个数异或即可得到另一个数（并没有非常详细，但是各位阿辉基本上已经讲完了，一点细节各位可以自行揣摩，真不懂可以私信阿辉）

✈️得到一个数最右侧的1

对于一个数6，6的二进制是0110（这里阿辉用四位表示，各位应该看得懂），对~6就会得到1001如果这时我们给它加上1就会得到1010这时6 | (~6 + 1)就把最右侧的1取出来了（最右侧的1指的是0010这个数），为什么呢？

其实，我们要的是最右边的1，当你对原数字进行取反操作时，假如最右侧的1后面还有0，取反后加1就会让~a + 1在a的最右侧1对应的位置上有一个1，他俩与运算完就会得到最右侧的1

🚀究极进阶题

题目：一组数，一种数出现了k次，其他的数出现了m次，m > 1, m > k，求出现k次的这种数

思路：

利用一个长度为32的num数组，遍历原数组中每一个数将原数组的每一个数的二进制位的每一位累加到num上

然后num中每一个下标上对应的数字只要不是m的整数倍，就说明该二进制位上有1，遍历num数组即可得到出现k次的数

说实话这题真的骚

int onlyone(int a[], int len,int k, int m) {
  int ans = 0;
  int num[32] = { 0 };
  for (int j = 0; j < len; j++) {
    for (int i = 0; i < 32; i++) {
      num[i] += (a[i] >> i) & 1;//存数组中所有数字每一个二进制位的和
    }
  }
  for (int i = 0; i < len; i++) {//把模上m不等于0的位得到
    if (num[i] % m != 0)
      ans |= (1 << i);//将这每一位或到ans中，得到答案
  }
  return ans;
}