《异或运算的性质》由会员分享，可在线阅读，更多相关《异或运算的性质（4页珍藏版）》请在金锄头文库上搜索。
1、异或1的配对性定理:设a为任意非负偶数，b=a+1为比a大1的正奇数；则必有a1 = b,b1=a;用于处理两两配对问题（如正向、反向边）时很好用！ ！女廿 a = 2,b=3:2人1 = 3,3人1 = 2; 98人1=99;99人1=98;123人1 = 122; 9870人1=9871如 a = 0,b=1: 0人1 = 1,1人1 = 0;证明：由异或的自反性abb=a0=a，可知a11=a;又因为对于任意非负偶数有a1=a+1 ；所以有：a1=a+1 = b;a11 = （a+1）1 = b1=a;异或的性质及运用异或是一种基于二进制的位运算，用符号XOR或者人表示，其运算法则是对
2、运算符两侧数的每一个二进制位，同值取0,异值取1。它与布尔运算的区别在 于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。简单理解就是不进位加法，如1 + 1 = 0, ,0+0 = 0,1+0=10性质1、交换律2、结合律（即（ab）八c = A八（bc）3、对于任何数X,都有x八x=O, x八O=x4、自反性 A XOR B XOR B = A xor 0 = A异或运算最常见于多项式除法，不过它最重要的性质还是自反性:A XOR B XOR B = A，即对给定的数A，用同样的运算因子（B）作两次异或运算后仍得到A本身。这是一个神奇的性质，利用这个性质，可以获得许多有趣的
3、应用。例如， 所有的程序教科书都会向初学者指出，要交换两个变量的值，必须要引入一个中 间变量。但如果使用异或，就可以节约一个变量的存储空间：设有A,B两个变 量，存储的值分别为a，b，则以下三行表达式将互换他们的值 表达式(值)：A=A XOR B (a XOR b)B=B XOR A (b XOR a XOR b = a)A=A XOR B (a XOR b XOR a = b)类似地，该运算还可以应用在加密，数据传输，校验等等许多领域。运用距离：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均 只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用
4、辅助存储 空间，能否设计一个算法实现？解法一、显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去1+2+ 1000 的和。这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题 是，如果数列过大，则可能会导致溢出。解法二、异或就没有这个问题，并且性能更好。将所有的数全部异或，得到的结果与1人2人3人人1000的结果进行异或，得 到的结果就是重复数。但是这个算法虽然很简单，但证明起来并不是一件容易的事情。这与异或运算的 几个特性有关系。首先是异或运算满足交换律、结合律。所以，1人2人人n人人n人人1000，无论这两个n出现在什么位置，都可 以转换成为1人2人人1000人(
5、nn)的形式。其次，对于任何数x,都有x人x=0, x人0=x。所以1八2八八“八八“八八1000 = 1八2八八1000八（nn）=1八2八八1000八0 = 1八2八八100（即序列中除了 n的所有数的异或）。令，1人2人人1000 （序列中不包含n）的结果为T则1人2人人1000 （序列中包含n）的结果就是Tn。T人（T人 n） = n。所以，将所有的数全部异或，得到的结果与1人2人3人人1000的结果进行异 或，得到的结果就是重复数。当然有人会说，1+2+ 1000的结果有高斯定律可以快速计算，但实际上1人2人人1000的结果也是有规律的，算法比高斯定律还该简单的多。google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均 出现偶数次，找出这个出现奇数次的数？解法有很多，但是最好的和上面一样，就是把所有数异或，最后结构就是要找的， 原理同上！转载自 http:I 0Aa=a；异或有交换律
