可能出了大学后，就很少遇到异或运算吧，只是在刷力扣的时候经常会看到有些题解用到，今天就重新温习下。

你好，异或

异或运算,表达为^符号，规则为：相同为0，不同为1。 如

还有同或运算，这个用的较少，为了不混淆记忆，异或运算可以理解为 无进位相加，如上图就是忽略了进位信息，这样就好记很多。

各种举例

• 自己和自己异或，都是0
• 0和任何数异或，都是该数本身
• 交换律 a^b=b^a
• 结合律 a^b=c 那么 b=a^c或者 a=b^c

• 0和任何数异或，都等于这个数的本身。

  来几个异或的使用案例

• 如何不开辟一个临时变量c，来交换a和b的值，如果是回答 a,b=b,a那就拉出去砍了。

a = a^b
b = a^b
a = a^b

分析下： 第一行代码：a = a^b,b = b
第二行代码：b = a^b 此时a=a^b实际上就是： b = a^b^b ，由于自己异或自己都是0,0和任何数异或都是该数本身，所以b=a , a依旧是a^b
第三行代码: a=a^b,实际上就是a^b^a，同理，a = b。
不知道go语言底层是增加temp变量还是使用的异或，没找到源码，下次找到了再回来更新。
这样节省了空间复杂度

• 如何提取一个数的最右侧的1出来。
  如 一个数的二进制为： 10010100 需要把所有的1提取出来。

a:=148 // 10010100
for a!=0{
    rightOne := a & (-a) // 这里可以提取最右侧的1
    log.Println(rightOne)
    a ^=rightOne
}

输出 这个程序相当于把里面所有的1给剥离出来了。

4
12
128

• 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数。
  如数组：[11,22,5,3,11,4,5,3,22] 除了4之外，其余的数都出现了偶数次，只有4出现了基数次1次。

func OddOneKind(arr []int) {
    eor := 0
    for _, item := range arr {
        eor ^= item
    }
    fmt.Println(eor) // 4
}

简单吧，因为如下特性，
1：同一批数异或，不管何种顺序，最终结果都是一样。
2：自己和自己异或都是0，偶数次的都是0返回了。
3：自己和0异或，都是该数本身。

• 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，找到这两种数。
  如：[5,5,2,4,3,3],只有4,2出现一次。
  分析：如果按照我们上述的方式，最后肯定是4^2的结果，但如何得到4和2呢？
• 最后4^2=6，也就是4和2的二进制肯定有一位不一样，不然异或就是0了。
• 6的二进制为0 1 1 0
• 所有的数，在某一位上面可以分为两类，而2和4肯定是在这一位上面是不一样的，
  如6的第二位是1，那么所有的数，可以分为第二位是0和第二位是1的数，如下推断。

也就是说异或出来的倒数第一个1,2和4肯定是不一样，那么就有办法了。
这里需要先引进 & 的概念

代码如下：

func OddTimes2(arr []int) {
    eor := 0
    for _, item := range arr {
        eor ^= item
    }
    fmt.Println(eor) // 假设a和b为两个奇数，eor肯定是 a^b的值，因为偶数都是0

    rightOne := eor & (-eor) // 获取eor的最右侧的1，因为这个位数上面a和b肯定是不一样的
    onlyOne := 0             // 这个数，肯定是a或者是b，先定义好
    for _, item := range arr {
        if (item & rightOne) != 0 { // 这里就是区分a或b，只有最右侧为1的才可以进来，也就肯定a能进，b就不能进
            onlyOne ^= item // 同样，偶数的都为0，这个onlyOne肯定就只有a
        }
    }
    b := eor ^ onlyOne // 这样就获取到了另一个数 b
    fmt.Println(a,b)
}