Dar*_*der 55 language-agnostic math bit-manipulation operators xor
我试图理解C#中的二元运算符,或者一般,尤其是^ - exclusive或.
例如:
给出一组正整数.除了一个出现奇数次数的数字之外,所有数字都出现偶数次.在O(n)时间和恒定空间中找到数字.
这可以通过^完成,如下所示:对所有元素进行按位异或.最后我们得到奇数出现的数字.
它是如何工作的？
当我做:
int res = 2 ^ 3;
res = 1;
int res = 2 ^ 5;
res = 7;
int res = 2 ^ 10;
res = 8;
实际发生了什么？还有什么其他的魔法？我可以查阅任何参考资料并了解更多信息吗？
fyr*_*rye 99
我知道这是一个相当古老的帖子,但我想简化答案,因为我在寻找其他东西时偶然发现了它.
XOR(eXclusive OR /或者),可以简单地翻译为打开/关闭.
哪个将排除或包含指定的位.
使用4位(1111),我们从0-15得到16个可能的结果:
decimal | binary | expanded
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 | (1+2)
4 | 0100 |
5 | 0101 | (1+4)
6 | 0110 | (2+4)
7 | 0111 | (1+2+4)
8 | 1000 |
9 | 1001 | (1+8)
10 | 1010 | (2+8)
11 | 1011 | (1+2+8)
12 | 1100 | (4+8)
13 | 1101 | (1+4+8)
14 | 1110 | (2+4+8)
15 | 1111 | (1+2+4+8)
二进制值左侧的十进制值是XOR和其他按位运算中使用的数值.
例如:0011位1和2为on,第4位和第8位为off.其表示为3表示打开的位的十进制值,并以扩展形式显示为1+2.
至于XOR背后的逻辑是什么,这里有一些例子
来自原始帖子
2 ^ 3 = 1
- 2是1 + 2 (3)删除2 = 1的成员
2 ^ 5 = 7
- 2不是1 + 4 (5)加2 = 1 + 2 + 4(7)的成员
2 ^ 10 = 8
- 2是2 + 8 (10)的成员删除2 = 8
更多例子
1 ^ 3 = 2
- 1是1 + 2 (3)删除1 = 2的成员
4 ^ 5 = 1
- 4是1 + 4 (5)的成员删除4 = 1
4 ^ 4 = 0
- 4是自身成员删除4 = 0
1 ^ 2 ^ 3 = 0
逻辑:((1 ^ 2)^(1 + 2))
- (1 ^ 2)1不是2的成员加2 = 1 + 2 (3)
- (3 ^ 3)1和2是1 + 2 (3)的成员删除1 + 2 (3) = 0
1 ^ 1 ^ 0 ^ 1 = 1
逻辑:(((1 ^ 1)^ 0)^ 1)
- (1 ^ 1)1是1的成员删除1 = 0
- (0 ^ 0)0是0的成员删除0 = 0
- (0 ^ 1)0不是1 add 1 = 1的成员
1 ^ 8 ^ 4 = 13
逻辑:((1 ^ 8)^ 4)
- (1 ^ 8)1不是8的成员1 = 1 + 8 (9)
- (9 ^ 4)1和8不是4的成员加1 + 8 = 1 + 4 + 8 (13)
4 ^ 13 ^ 10 = 3
逻辑:((4 ^(1 + 4 + 8))^(2 + 8))
- (4 ^ 13)4是1 + 4 + 8 (13)删除4 = 1 + 8 (9)的成员
- (9 ^ 10)8是2 + 8 (10)的成员,删除8 = 2
- 1不是2
+8(10)加1 = 1 + 2 (3)的成员4 ^ 10 ^ 13 = 3
逻辑:((4 ^(2 + 8))^(1 + 4 + 8))
- (4 ^ 10)4不是2 + 8 (10)的成员加4 = 2 + 4 + 8 (14)
- (14 ^ 13)4和8是1 + 4 + 8 (13)的成员,去除4 + 8 = 1
- 2不是1
+ 4 + 8(13)加2 = 1 + 2 (3)的成员
Ben*_*igt 55
要了解它是如何工作的,首先需要以二进制形式编写两个操作数,因为按位运算适用于各个位.
然后,您可以为您的特定运营商应用真值表.它作用于两个操作数中具有相同位置的每对位(相同的位置值).因此最左边的位(MSB)A与MSB组合B以产生结果的MSB.
示例2^10::
0010 2
XOR 1010 8 + 2
----
1 xor(0, 1)
0 xor(0, 0)
0 xor(1, 1)
0 xor(0, 0)
----
= 1000 8
结果是8.
Nem*_*emo 31
另一种表明这种情况的方法是使用XOR的代数; 你不需要知道任何有关个别位的信息.
对于任何数字x,y,z:
异或是可交换的: x ^ y == y ^ x
XOR是关联的: x ^ (y ^ z) == (x ^ y) ^ z
标识为0: x ^ 0 == x
每个元素都是它自己的逆: x ^ x == 0
鉴于此,很容易证明结果.考虑一个序列:
a ^ b ^ c ^ d ...
由于XOR是可交换和关联的,因此顺序无关紧要.所以对元素进行排序.
现在任何相邻的相同元素x ^ x都可以替换为0(自反特性).任何0都可以删除(因为它是身份).
尽可能重复.出现偶数次的任何数字都有一对整数,所以它们都变为0并消失.
最后,你只剩下一个元素,即出现奇数次的元素.每当它出现两次,那两个就会消失.最终你只剩下一次.
[更新]
请注意,此证明仅需要对操作进行某些假设.具体来说,假设具有运算符的集合S具有.以下属性:
Assocativity:x . (y . z) = (x . y) . z任何x,y和z在S.
身份:存在一个单一的元素e,使得e . x = x . e = x所有x的S.
关闭:对于任何x和y在S中,x . y也在S中
自逆:对于xS中的任何一个,x . x = e
事实证明,我们不需要承担交换性; 我们可以证明:
(x . y) . (x . y) = e (by self-inverse)
x . (y . x) . y = e (by associativity)
x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right)
y . x = x . y (because x . x = y . y = e and the e's go away)
现在,我说"你不需要知道任何关于个别位的信息".我认为任何满足这些属性的组都足够了,并且这样的组不一定与XOR下的整数同构.
但@Steve Jessup在评论中证明我错了.如果您将标量乘法定义为{0,1},则:
0 * x = 0
1 * x = x
...然后这个结构满足整数mod 2 上的向量空间的所有公理.
因此,任何这样的结构在分量XOR下与一组位向量同构.
小智 13
这是基于一个简单的事实，即数字与自身的异或结果为零。
和一个数字与 0 的异或结果是数字本身。
所以，如果我们有一个数组 = {5,8,12,5,12}。
5 发生了 2 次。8 发生了 1 次。12 发生了 2 次。
我们必须找到出现奇数次的数字。显然，8 是数字。
我们从 res=0 和 XOR 开始，对数组的所有元素进行异或。
int res=0;
for(int i:array)
res = res ^ i;
1st Iteration: res = 0^5 = 5
2nd Iteration: res = 5^8
3rd Iteration: res = 5^8^12
4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12
5th Iteration: res = 8^12^12 = 8^0 = 8
按位运算符将整数值内的位视为微小的位数组.每个位都像一个微小的bool值.当您使用按位异或运算符时,对运算符执行的操作的一种解释是:
净效应是单个位开始false,如果"切换"的总数是偶数,它仍将false在结束时.如果"切换"的总数是奇数,则它将true在最后.
只要想想"微小的布尔值数组",它就会开始变得有意义.