异或、异或和 的性质及应用总结
异或、异或和 的性质及应用总结
异或运算（XOR）是计算机科学中一个基础且重要的逻辑运算，广泛应用于数据处理和算法设计中。本文将从异或的基本概念出发，详细介绍其性质，并通过具体问题展示其应用场景。
一：异或的含义
在数学中，“或”运算表示一个元素在集合A中或在集合B中。而“异或”则表示两个集合中独有的元素，不允许共存。具体来说：
A 或 B 的维恩图如下：
A 异或 B 的维恩图如下：
A 异或 B 异或 C 的维恩图：
异或运算的真值表如下（F表示false，T代表true）：
A | B | A ⊕ B |
|---|---|---|
F | F | F |
F | T | T |
T | F | T |
T | T | F |
二、异或的性质：满足交换律和结合律
异或运算具有以下重要性质：
- 交换律：A ^ B = B ^ A
- 结合律：A ^ (B ^ C) = (A ^ B) ^ C
- 恒等律：X ^ 0 = X
- 归零律：X ^ X = 0
- 自反：A ^ B ^ B = A ^ 0 = A
- 取反：对于任意的 X： X ^ (-1) = ~X
- 可逆性：如果 A ^ B = C 成立，那么 A ^ B = C，B ^ C = A
三、异或的应用
1. 找出重复的数字
问题：1-1000放在含有1001个元素的数组中，只有唯一的一个元素重复，找出这个重复的数字。要求不能使用辅助存储空间并且数组的每个元素只能访问一次。
解法一：将这1001个元素加起来的和减去1+2+……+1000，所得的值就是重复的数字（数据过大容易溢出）。
解法二：异或
将1001个数全部异或得到的值再与1^2^……^1000的结果再次异或，这样就避免了数据过大溢出的情况。
首先，异或运算满足交换律和结合律，即a^b = b^a，(a^b)^c = a^(b^c)。令重复的数字为n：
所以1 ^ 2 ^ … ^ n ^ n ^ … ^ 1000 = 1 ^ 2 ^ … ^ 1000 ^ (n ^ n) = 1 ^ 2 ^ … ^ 1000 ^ 0 = 1 ^ 2 ^ … ^ 1000（即序列中除了重复数字 n 以外所有数的异或。
如果令1 ^ 2 ^ … ^ 1000(序列中不包含n）的结果为T，那么1 ^ 2 ^ … ^ 1000(序列中包含n）的结果就是 T^n，T ^ (T ^ n) = n。
2. 找出出现奇数次的数
问题：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数。
解法与上面的解法二相同。由于异或运算的性质，所有出现偶数次的数都会相互抵消，最终剩下的就是出现奇数次的数。