异或（^）的性质与应用

本文目录

1 基本概念

2 异或应用

3 相关文章

1 基本概念

1.1 符号

异或是一种二进制的位运算，符号以 XOR 或 ^ 表示。

1.2 运算规则

相同为0，不同为1，即

1 ^ 1 = 0

0 ^ 0 = 0

1 ^ 0 = 1

由运算规则可知，任何二进制数与零异或，都会等于其本身，即 A ^ 0 = A。

1.3 异或性质

（1）交换律： A ^ B = B ^ A

（2）结合律： ( A ^ B ) ^ C = A ^ ( B ^ C )

（3）自反性： A ^ B ^ B = A （由结合律可推： A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A）

2 异或应用

2.1 变量交换

示例：将 a 和 b 两个变量值交换，例如： a = 3，b = 7，交换后，a = 7，b = 3。

// 常规方法 int temp = a; // temp = 3 a = b; // a = 7 b = temp; // b = 3 // 异或方法 a = a ^ b; // a = 3 ^ 7 b = a ^ b; // b = (3 ^ 7) ^ 7 = 3 ^ (7 ^ 7) = 3 a = a ^ b; // a = (3 ^ 7) ^ (3 ^ 7 ^ 7) = (3 ^ 3) ^ (7 ^ 7) ^ 7 = 7

2.2 排除偶次重复

示例：在一个整数数组中，仅存在一个不重复的数字，其余数字均出现两次（或偶数次），找出不重复数字。

// 常规方法：通过二次循环找出不重复的数字 for (...) { for (...) { ... } } // 异或方法：将所有整数异或，出现偶数次的整数会被抵消，最终留下不重复整数。 int result = 0; for (int index = 0; index < numArray.length; index++) { result = result ^ numArray[index]; } return result;

2.3 排除偶次重复变种

示例：将数字1-999存放在一个大小为1000的数组中，其中只有一个数字重复出现两次，找出重复数字。

/* 异或方法：该问题为异或自反性的变种题，将数字以二进制形式展示，即可发现其中奥秘。 * 1: 0 0 0 0 0 0 0 0 0 1 * 2: 0 0 0 0 0 0 0 0 1 0 * 3: 0 0 0 0 0 0 0 0 1 1 * 4: 0 0 0 0 0 0 0 1 0 0 * 5: 0 0 0 0 0 0 0 1 0 1 * 6: 0 0 0 0 0 0 0 1 1 0 * 7: 0 0 0 0 0 0 0 1 1 1 * 8: 0 0 0 0 0 0 1 0 0 0 * 9: 0 0 0 0 0 0 1 0 0 1 * 10: 0 0 0 0 0 0 1 0 1 0 * 11: 0 0 0 0 0 0 1 0 1 1 * 12: 0 0 0 0 0 0 1 1 0 0 * 13: 0 0 0 0 0 0 1 1 0 1 * 14: 0 0 0 0 0 0 1 1 1 0 * 15: 0 0 0 0 0 0 1 1 1 1 * 16: 0 0 0 0 0 1 0 0 0 0 * .... * 999: 1 1 1 1 1 0 0 1 1 1 * PreCount: 511 255 127 63 31 15 7 3 1 0 * RepeatSpan: 1024 512 256 128 64 32 16 8 4 2 * MaxRepeat: 0 1 3 7 15 30 62 124 249 499 * Flag: A B C D E F G H I J * * 每一位（列）的前置0个数PreCount：2的n-1次方减1 * 每一位（列）的完整重复跨度为RepeatSpan：2的n次方 * 每一位（列）的完整重复次数为MaxRepeat：（999 - PreCount） / Repeat 向下取整 * 每一位（列）的非完整重复内的数字个数：999 - MaxRepeat * Repeat - PreCount * * 每一个完整重复内，前一半为1，后一半为0； * 末位（J位）完整重复内，异或结果为1； * 非末位（J位）完整重复内，均为偶数个1，异或结果为0； * * 由此可知：计算每一位（列）非完整重复部分的异或结果 与 完整重复部分的异或结果，即可得最终结果。 * J位：非完整重复数字个数 1，完整重复 499个1， 整体偶数个1，最终结果0； * I位：非完整重复数字个数 2，完整重复 249个0， 整体偶数个1，最终结果0； * H位：非完整重复数字个数 4，完整重复 124个0， 整体偶数个1，最终结果0； * G位：非完整重复数字个数 0，完整重复 62个0， 整体偶数个1，最终结果0； * F位：非完整重复数字个数 24，完整重复 30个0， 整体偶数个1，最终结果0； * E位：非完整重复数字个数 8，完整重复 15个0， 整体偶数个1，最终结果0； * D位：非完整重复数字个数 40，完整重复 7个0， 整体偶数个1，最终结果0； * C位：非完整重复数字个数 104，完整重复 3个0， 整体偶数个1，最终结果0； * B位：非完整重复数字个数 232，完整重复 1个0， 整体偶数个1，最终结果0； * A位：非完整重复数字个数 488，完整重复 0个0， 整体偶数个1，最终结果0； * * 即：1-999数字的异或结果为0 * * 因此，将1000个整数依次异或运算，最终结果就是重复的数字，相当于重复数字与0进行异或，得到其本身。 */ int result = 0; for (int index = 0; index < numArray.length; index++) { result = result ^ numArray[index]; } return result;

2.4 LeetCode 260：只出现一次的数字Ⅲ

题目：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

思路：

(1) 先通过一次异或操作，重复元素会被抵消，最终结果相当于两个单次出现的元素（分别记为one和two）的异或值；

(2) 由异或规则可知，若两个元素one和two的异或值的某二进制位为1，则表示两个元素在该二进制位上的值不同，即分别为1和0，找到其中一个满足条件（为1）的二进制位（记为bitValue）；

(3) 根据（2）找到的二进制位bitValue，可以将原数组分成两个部分，one 和 two 分别在两个部分，而相同的重复元素也会被分到同一个部分（因为其相应的二进制位的值是相同的）；

(4) 对于两个部分再次进行异或操作，即相当于 排除偶次重复 问题，最终可以得到两个题解。

class Solution { public int[] singleNumber(int[] nums) { // 通过异或操作，最终结果等于两个单次出现的元素的异或值。 int filterResult = 0; for (int num : nums) { filterResult ^= num; } // 计算首个为1（从右侧开始）的二进制位的值 int bitValue = filterResult & (filterResult - 1) ^ filterResult; // 以首个为1的二进制位将原数组分为两个部分并分别进行异或运算，最终结果为两个题解。 int oneResult = 0, twoResult = 0; for (int num : nums) { if ((num & bitValue) > 0) { oneResult ^= num; } else { twoResult ^= num; } } return new int[]{oneResult, twoResult}; } }

3 相关文章

《全排列（Java）》

《位运算：减法与补码》

《图解：常用排序算法（冒泡、选择、插入、希尔、快速、归并、堆）》

《回溯算法（试探算法）》

《动态规划：鸡蛋掉落》

《动态规划：单词拆分》

《状态机：只出现一次的数字II》

《最小堆：TopK问题》

《链表：快慢指针》