基本概念

异或：不同为1，相同为0

也可以理解为无进位相加。1+1=0，不进位，与相同为0同样的效果。

性质

1、0与任何数N异或都是N，任何一个数与自己异或都是0

1
2
0 ^ N = N 
N ^ N = 0

2、异或运算满足交换律或结合律

1
2
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

3、同样一批数，与异或的顺序无关，谁先异或不影响最终结果

应用

1、交换两个变量的值

根据上述性质可以使用异或方法，在不额外开辟空间的情况下，来交换两个变量的值：

1
2
3
4
5
6
7
// swap: 使用异或交换两个变量的值
func swap(a, b int) (int, int) {
	a = a ^ b // 将 a = a ^ b 带入下面的式子
	b = a ^ b // b = (a ^ b) ^ b = a
	a = a ^ b // a = (a ^ b) ^ a = b
	return a, b
}

当然，这样做也有一个前提，即a和b在内存里是两块独立的区域。什么意思呢？a可以等于b的值，但是a的地址和b的地址不同，如果内存是一块东西，a异或b等同于与自己异或，那么结果是0，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func swaps(k *int, b *int) (int, int) {
	*k ^= *b
	*b ^= *k
	*k ^= *b
	return *k, *b
}

func main() {
	a := 1
	b := 2
	fmt.Println(swaps(&a, &b))

	a, b = 3, 3
	fmt.Println(swaps(&a, &b))
	
	c := 4
	d := &c
	fmt.Println("c", &c)
	fmt.Println("d", d)
	fmt.Println(swaps(&c, d))
}

结果，当地址不同时，可正常交换变量的值，当地址相同时，异或结果为0：

1
2
3
4
5
2 1
3 3           
c 0xc0000180c0
d 0xc0000180c0
0 0

所以要用异或来交换两个值记得判断是否为同一块内存，例如在数组中就可以加上索引的判断。

1
2
3
4
5
6
7
8
9
func swapArr(arr *[3]int, a int, b int) (int, int) {
    if a == b {
        return arr[a], arr[b]
    }
    arr[a] ^= arr[b]
    arr[b] ^= arr[b]
    arr[a] ^= arr[b]
    return arr[a], arr[b]
}