异或（exclusive or）的定义

符号：

XOR 或 EOR 或 ⊕（编程语言中常用^）

定义：逻辑运算里，仅当两个运算元中恰有一个的值为真，而另外一个的值为非真时，其值为真

1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1

异或的特性

恒等律：X ⊕ 0 = X （X为任意整数）
归零律：X ⊕ X = 0 （X为任意整数）
交换律：A ⊕ B = B ⊕ A
结合律：(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

通过异或解决具体问题

判断两个数是否相等

技算机底层判断整数是否相等的方案：通过先将相应的位进行异或操作，然后将所有异或操作的结果进行或操作。因为执行异或操作没有进位，因此，这种方法比用ALU将两个数相减，然后再判断输出是否为0要快得多。

Linux中最初的ipv6_addr_equal()函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
{
    return (a1->s6_addr32[0] == a2->s6_addr32[0] &&
        a1->s6_addr32[1] == a2->s6_addr32[1] &&
        a1->s6_addr32[2] == a2->s6_addr32[2] &&
        a1->s6_addr32[3] == a2->s6_addr32[3]);
}

static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
{
    return (((a1->s6_addr32[0] ^ a2->s6_addr32[0]) |
        (a1->s6_addr32[1] ^ a2->s6_addr32[1]) |
        (a1->s6_addr32[2] ^ a2->s6_addr32[2]) |
        (a1->s6_addr32[3] ^ a2->s6_addr32[3])) == 0);
}

数据校验

利用异或的特性：IF a ^ b = c THEN a ^ c = b, b ^ c = a

RAID5，大概原理为：使用3块磁盘（A、B、C）组成RAID5阵列，当用户写数据时，将数据分成两部分，分别写到磁盘A和磁盘B，A ^ B的结果写到磁盘C；当读取A的数据时，通过B ^ C可以对A的数据做校验，当A盘出错时，通过B ^ C也可以恢复A盘的数据。

bit位的一些操作

判断一个二进制数中1的数量是奇数还是偶数

如100010111中1的数量是奇数还是偶数？

解答：1^0^0^0^1^0^1^1^1 = 1

特定位进行翻转

利用异或的特性：1^1=0，0^1=1。

如翻转100010111里的第5位？

解答：100010111 ^ 000010000 = 100000111

不使用其他空间，交换两个值

1
2
3
4

int a,b;
a = a ^ b;
b = a ^ b; // a^b^b=a
a = a ^ b; // a^b^a=b

一个整型数组里除了1个数字之外，其他的数字都出现两次，请查找出其中从一组数据中找出只出现一次的数字

比如，从[3, 2, 3, 2, 4, 5, 5, 6, 6]中找出只出现一次的数字：4

利用异或的三个定律：归零律，交换律，结合律。

1
2
3

3 ^ 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 5 ^ 6 ^ 6
= 3 ^ 3 ^ 2 ^ 2 ^ 5 ^ 5 ^ 6 ^ 6 ^ 4
= 4

一个整型数组里除了2个数字之外，其他的数字都出现两次，请查找出其中从一组数据中找出只出现一次的数字

比如，从[a, b, a, b, c, d, e, f, e, f]中找出只出现一次的数字：c, d

思路：

1. 整体异或的结果为c与d的异或值：cXORd，因c != d，则 cXORd != 0；
2. 利用cXORd的第一位值为1（比如从右向左第一位），来区分c与d，如下图所示：
   
3. 从数组里，找到所有第二位都为1的数字，假设有：[ a, a, c, e, f, e, f]，再对这些数进行异或：a ^ a ^ c ^ e ^ f ^ e ^ f = c
4. 再利用异或的特性：cXORd ^ c = d

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static int getFirstOneBit(int a){
    return a | (~a + 1); // 由a | -a即可以获取
}

public static void findTwo(int[] array){
    if(array == null || array.length == 0) {
        return ;
    }

    int cXORd = 0;
    for(int item : array){
        cXORd = cXORd ^ item;
    }

    int firstOneBit = getFirstOneBit(cXORd);
    int c = 0;
    for(int item : array){
        if(getFirstOneBit(item) == firstOneBit){
            c = c ^ item;
        }
    }

    int d = cXORd ^ c;

    System.out.printf("findTwo num is %d, %d\n", c, d);
}

时间复杂度为O(n)，空间复杂度O(1)

一个整型数组里除了3个数字之外，其他的数字都出现两次，请查找出其中从一组数据中找出只出现一次的数字

比如，从[a, b, a, b, c, d, e, f, f]中找出只出现一次的数字：c, d，e

思路：

1. 整体异或的结果为c,d,e的异或值：cXORdXORe。同时(cXORdXORe ^ c) ^ (cXORdXORe ^ d) ^ (cXORdXORe ^ e) = 0
2. IF A ^ B ^ C = 0, 则可以得出如下结论：
   
3. 把查找3个数字，转换为2个数字的问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static void findThree(int[] array){
    if(array == null || array.length == 0){
        return ;
    }

    int cXORdXORe = 0;
    for(int item : array){
        cXORdXORe = cXORdXORe ^ item;
    }

    int firstBit = 0;
    for(int item : array){
        firstBit = firstBit ^ getFirstOneBit(cXORdXORe ^ item);
    }

    int c = 0;
    for(int item : array){
        if(getFirstOneBit(cXORdXORe ^ item) == firstBit){
            c = c ^ item;
        }
    }

    System.out.printf("findThree num is %d ", c);

    int[] findtwoArray = new int[array.length + 1];
    for(int i=0; i<array.length; i++){
        findtwoArray[i] = array[i];
    }
    findtwoArray[findtwoArray.length - 1] = c;
    findTwo(findtwoArray);
}

时间复杂度O(n)，空间复杂度O(1)

参考

1. 感受异或的神奇