本文目录
1 基本概念
2 异或应用
3 相关文章
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.1 变量交换
示例：将 a 和 b 两个变量值交换，例如： a = 3，b = 7，交换后，a = 7，b = 3。
2.2 排除偶次重复
示例：在一个整数数组中，仅存在一个不重复的数字，其余数字均出现两次（或偶数次），找出不重复数字。
2.3 排除偶次重复变种
示例：将数字1-999存放在一个大小为1000的数组中，其中只有一个数字重复出现两次，找出重复数字。
2.4 LeetCode 260：只出现一次的数字Ⅲ
题目：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
思路：
(1) 先通过一次异或操作，重复元素会被抵消，最终结果相当于两个单次出现的元素（分别记为one和two）的异或值；
(2) 由异或规则可知，若两个元素one和two的异或值的某二进制位为1，则表示两个元素在该二进制位上的值不同，即分别为1和0，找到其中一个满足条件（为1）的二进制位（记为bitValue）；
(3) 根据（2）找到的二进制位bitValue，可以将原数组分成两个部分，one 和 two 分别在两个部分，而相同的重复元素也会被分到同一个部分（因为其相应的二进制位的值是相同的）；
(4) 对于两个部分再次进行异或操作，即相当于 排除偶次重复 问题，最终可以得到两个题解。
《全排列（Java）》
《位运算：减法与补码》
《图解：常用排序算法（冒泡、选择、插入、希尔、快速、归并、堆）》
《回溯算法（试探算法）》
《动态规划：鸡蛋掉落》
《动态规划：单词拆分》
《状态机：只出现一次的数字II》
《最小堆：TopK问题》
《链表：快慢指针》
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/755.html