异或的妙用

大家好，欢迎来到IT知识分享网。

一、什么是异或

异或 (xor) 是一种常用的逻辑运算，在数学中用 “ ⊕ ” 符号表示，在编程代码中用符号 “ ^ ” 表示。其真值表如图所示：

刚接触逻辑运算的小伙伴可能总是记不住什么情况为1，什么情况为0。这里给一个记忆小提示：

• 计算机中经常用 1 代表 true ，用 0 代表 false ；
• 异或异或，关键在于“异”字，也就是“不同”，异了才为1。

因此，就有了“相同为0，不同为1”的口诀。理解了“异”字的含义之后，再看上面的真值表是不是就很容易记忆啦！
举一反三，“同或”真值表也就很容易推出来了（关键在“同”）：

二、异或的性质

1. 0 ^ N = N
2. N ^ N = 0
3. 异或运算满足 结合律 和 交换律
4. 按位异或，可以看作是二进制的 “ 无符号相加 ”

三、巧用异或运算

下面举几个巧妙使用“异或”运算的例子：

题目一：交换两个数字的值

• 描述：交换数组 arr 的 i ，j 位置上的数值

方法一：

 // 交换arr的i和j位置上的值 public static void swap(int[] arr, int i, int j) { 
    int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } 

方法二：

 // 交换arr的i和j位置上的值 public static void swap(int[] arr, int i, int j) { 
    arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; } 

方法三：

 // 交换arr的i和j位置上的值 public static void swap(int[] arr, int i, int j) { 
    arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } 

这三种方法均实现了交换数组中两个位置上的值的目的。

方法一是最常规的方法；

方法二虽然使用 + – 运算实现了交换，但在代码的第三行出现了两个数相加的操作，在数组中数据未知其范围的情况下，容易出现溢出的问题，造成不必要的麻烦（这在二分查找中 mid = L + (( R – L ) >> 2); 也遇到过）；

方法三使用异或运算，主要使用了 性质2 两个相同的数字异或为0的特点实现交换。但该方法也存在一定问题，当 arr[i] 和 arr[j] 指向同一片内存地址时，由 性质2 知，其结果为 0，达不到交换的效果。

因此，交换两数值时，还是老老实实的使用最简单的方法一吧！

题目二：一个整形数中1的个数

• 描述：一个整形数对应的二进制中有多少个1。

 public static int bit1counts(int N) { 
    int count = 0; while(N != 0) { 
    int rightOne = N & ((~N) + 1);// 提取出最右侧的 1  N ^= rightOne; // 剔除掉最右侧的 1  count++; } return count; } 

N的值更新为剔除最右侧的1后的新值，此时计数器+1。以此循环，当N的值变为0时，就统计出了N中所有1的个数。

题目三：数组中出现奇数次的数

• 描述：在一个数组中有一种数出现了奇数次，其他数都出现了偶数次。找到出现奇数次个数的数是几。

 public static void OddNum(int[] arr) { 
    int num = 0; for (int i = 0; i < arr.length; i++) { 
    num ^= arr[i]; } System.out.println(num); } 

该题思想其实很简单，运用 性质2 和 性质3交换律、结合律，将出现偶数次的数两两结合，变为0，最后只剩下一个奇数次的数字与0异或，仍为该数本身。

题目四：数组中出现两个奇数次的数

• 描述：在一个数组中有两种数出现了奇数次，其他数都出现了偶数次。找到这两个出现奇数次个数的数分别是几。

 public static void OddNum2(int[] arr) { 
    int num = 0; for (int i = 0; i < arr.length; i++) { 
    num ^= arr[i]; } int rightOne = num & ((~num) + 1); // 提取出最右侧的 1  int one = 0; // 以rightOne为界将数组分为两部分，此时两个奇数次数就分开了 for (int i = 0 ; i < arr.length;i++) { 
    if ((arr[i] & rightOne) != 1) { 
    one ^= arr[i]; } } System.out.println(one + " " + (num ^ one)); } 

理解了前面的二、三两道题，再来看本题的代码思路就能轻松不少。

num 的值表示了两个出现奇数次的数异或后的结果，且 num 不为0。找到最右侧的1，以此作为分界，就可以将整个数组中的值分为两部分：一部分为rightOne 为1那一位上值为0的所有数，另一部分为 rightOne 为1那一位上值为1的所有数。至此，该题就转化为了题目三，再次异或后就能得到两个出现奇数次的数。

题目五：数组中出现k次的数

• 描述：数组中仅有一个数出现了k次，其他的数均出现了m次。找出出现k次的数是几(k<m)。

public static int KNum(int[] arr, int k, int m) { 
    int[] t = new int[32]; for (int i = 0; i < arr.length; i++) { 
    for (int j = 0; j < 32; j++) { 
    t[j] += (arr[i] >> j) & 1; } } int ans = 0; for (int i = 0; i < 32; i++) { 
    if (t[i] % m == k) { 
    ans |= (1 << i); } } return ans; } 

遍历数组，用数组 t 记录数组 arr 中所有数字的每个二进制位上1的出现次数。遍历数组 t ，如果当前位置上的数字1的个数模m后为 k ，说明出现 k 次的数字在该位上为 1。用或运算进行记录，将ans对应位设置为1。遍历结束后，ans就获取到了出现 k 次数的二进制位上所有的1，即为所求。