基本概念


异或:不同为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]
}