首页 > 代码库 > 关于异或（Xor）的一点笔记
关于异或（Xor）的一点笔记
因为博弈论里，尤其实在求sg函数时，经常会用到异或运算，所以我就把网上搜到的一些相关知识和自己的一些理解记下来。
如果出现差错，还请指出，谢谢！
异或：可以简称Xor，可以用数学符号⊕表示，计算机就一般可以用^表示了。
异或运算主要指二进制中。
0⊕0=0,0⊕1=1
1⊕0=1,1⊕1=0
可以看成是两个值相同得0,不同得1。
另一种求值方法就是两数相加，但是不进位，如1⊕1=0，可以看作1+1=10,但是不进位，所以1⊕1=0。
关于一些运算法则
1. a ⊕ a = 0
2. a ⊕ b = b ⊕ a
3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
5. a ⊕ b ⊕ a = b.
我举例说明一下法则5的运用。
例题：已知一串只含大于0的int型整数的数字，其中大部分数都出现了两次，但只有一个数只出现了一次，求这个数的值。
如5 5 3 2 2 1 3，数字5，3，2都出现了两次，而只有1只出现了一次，所以这串数字的答案为1。又如3,4,5,5,4,2,3 的答案为2。
对于这题，可以使用hash数组，但可能会使用过大的空间。如果用异或就简单许多了。因为a⊕a=0; 0⊕b=b;a⊕b⊕a=b;
如5 5 3 2 2 1 3求异或 5 ⊕ 5 ⊕ 3 ⊕ 2 ⊕ 2 ⊕ 1 ⊕ 3 = 5 ⊕ 5 ⊕ 3 ⊕ 3 ⊕ 2 ⊕ 2 ⊕ 1 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1;数列中出现两次的数5,3,2在异或都将得出0，因此得出只出现一次的数字1。
这题只要将所有数字异或即可得只出现一次的数字。而且这方法极大的节约了空间和时间。关于异或（Xor）的一点笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。