黑马程序员技术交流社区

标题: 异或的小问题 [打印本页]

作者: Jam-l 时间: 2013-9-27 15:35
标题: 异或的小问题
本帖最后由 Jam-l 于 2013-9-27 20:05 编辑

为什么一个数两次异或同一个数会得到与原来相同的数，谁能举个例子并用算法解释一下吗？

作者: 肖亚光 时间: 2013-9-27 15:45
你自己可以试一下啊
1^1 = 0 0^1 = 1

1^0=1 1^0 = 1

0^1 = 1 1^1 = 0

0^0=0 0^0=0

作者: doitforyou 时间: 2013-9-27 15:54
1。你要知道异或的基本原则：相同为0不同为1，而且数据在计算机底层都是以二进制存在的。
2。同一个数与它本身相异或，他们的二进制是一样的，所以结果为0
3。一个数与0相异或，是什么结果呢？二进制中1与0异或为1,0与0异或为0，也就是说，一个数与0异或，他的所有位保持不变。
楼主的问题就是一个数与同一个数异或两次，可以拆开来看，同一个数自身相异或为0，然后与另一个数相异或，自然就是另一个数本身了。
以上三步大概可以解释清楚了楼主问题。

作者: 1098918523 时间: 2013-9-27 16:29
1.异或运算具有交换律、结合律。

2.一个数和自己做异或的结果是0。

xorl %eax, %eax比movl $0, %eax快

3.与0做异或，保持原值不变。

运用特性1，2，3，常在面试中遇到不用中间变量交换两个变量值。

int A=5, B=3;

. A          B

. 5          3

A=A^B 5^3          3

B=A^B 5^3    5^(3^3)=5^0=5

A=A^B  5^3^5=3 5

（这样运算只能帮助更好的理解异或的特性，但是针对效率而言，它不及采用中间变量的办法）。

还有一个应用如：现有1,1,2,2,3,3,....,n,n共2n个数，其中各个数字排列的顺序是任意的，是杂乱放的，即没有排序。现在删除了其中的一个数剩下了2n-1个数，求删除的那个数？

运用特性1，2，3就能很容易的解决，让所有的数异或，就能找到删除的数。

4.如果a1 ^ a2 ^ a3 ^ … ^ an的结果是1，则表示a1、a2、a3…an之中1的个数为奇数个，否则为偶数个。可用于奇偶校验(Parity Check).

作者: Jam-l 时间: 2013-9-27 16:53

肖亚光发表于 2013-9-27 15:45
你自己可以试一下啊
1^1 = 0 0^1 = 1

谢谢大家热心帮忙！你的最容易看懂。

作者: Mokill0911 时间: 2013-9-27 17:26

也可以写段代码看一下：

int a = 9,b;
b = a ^ 7;
System.out.println("1_b="+b);
b = b ^ 7;
System.out.println("2_b="+b);

复制代码

首先要知道，异或的原理就是两位相比相同为真（1），不同为假（0）；

另外，在内存里，数值的运算都是通过二进制来完成的。

所以当输入 9 ^ 7 的时候，内存中实际上是这样运算的：

9 转化为二进制： 1001
7 转化为二进制： 0111

两者每一位进行比较：
  1 0 0 1
^0 1 1 1
-------------
  1 1 1 0
所以这里二进制结果1110的十进制值为14 ，然后再将这个值第二次和7进行异或运算；
  1 1 1 0
^0 1 1 1
-------------
  1 0 0 1
得出的二进制结果为1001 再次转换为十进制的值就是 9 ；

作者: Mokill0911 时间: 2013-9-27 17:28
喵的辛苦编完已经有诸多大大帮忙解决了……

蹲角落画圈 - -|||

作者: Jam-l 时间: 2013-9-27 17:40

Mokill0911 发表于 2013-9-27 17:26
也可以写段代码看一下：首先要知道，异或的原理就是两位相比相同为真（1），不同为假（0）；

另外，在 ...

谢谢，你感觉你的算法更好理解

作者: 欲困 时间: 2013-9-27 19:08
异或都是用二进制运算的，相同为1 不同为0，以3为例
3的二进制是：0011
0011^0011 = 1111
1111^0011 = 0011
异或两次后还是3

作者: 坚持。 时间: 2013-9-27 20:39
你这样理解。你有一个饼，当你异或第一次的时候翻过来了，在异或一次，又将他反过来了，是不是还是原来的正面

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2