位运算运用的技巧

Go 中的位运算符

• & 按位与
• ^ 一元操作为非，二元操作为异或
• | 按位或
• &^ 清零操作，为二元操作，a&^b 等同于 a&(^b)
• << 左移位操作
• >> 右移位操作

注意，go 中是没有 >>> 操作的，这个操作在 java 中为带符号移位操作。

移位操作的特点

• 速度快
• 安全，防溢出

安全的特点：比如在算 a = b * 2 时，若 b 很大，可能导致溢出报错，但用 a = b << 1 的方式的话，则不会报错。但你可能会发现这个计算结果不正确，并不是真正的 2 * b，这个点需要注意。

取反操作的妙用

计算类型中的最大最小值

    // 求无符号数的最大值
    max_uint := ^uint(0)     // 18446744073709551615
    max_uint8 := ^uint8(0)   // 255
    max_uint16 := ^uint16(0) // 65535
    max_uint32 := ^uint32(0) // 4294967295
    max_uint64 := ^uint64(0) // 18446744073709551615
    fmt.Println(max_uint, max_uint8, max_uint16, max_uint32, max_uint64)
    // 有符号数取反后被机器认为是补码，所以 ^0 皆为 -1
    f := ^int(0) // -1，int8, int16, int32, int64 皆一样
    fmt.Println(f)
    // 有符号数的最大值可以这样取（移位是带符号的）
    max_int := int(^uint(0) >> 1)       // 9223372036854775807
    max_int8 := int8(^uint8(0) >> 1)    // 127
    max_int16 := int16(^uint16(0) >> 1) // 32767
    max_int32 := int32(^uint32(0) >> 1) // 2147483647
    max_int64 := int64(^uint64(0) >> 1) // 9223372036854775807
    fmt.Println(max_int, max_int8, max_int16, max_int32, max_int64)
    // 有符号数的最小值可以这样算（利用溢出）
    min_int := max_int + 1     // -9223372036854775808
    min_int8 := max_int8 + 1   // -128
    min_int16 := max_int16 + 1 // -32768
    min_int32 := max_int32 + 1 // -2147483648
    min_int64 := max_int64 + 1 // -9223372036854775808
    fmt.Println(min_int, min_int8, min_int16, min_int32, min_int64)
    // 但注意，不可以这样算
    // wrong_example := int(^uint(0)>>1) + 1
    // 报错：constant 9223372036854775808 overflows int
    // 差别是没有用中间变量进行运算，而是直接使用的常数值进行的计算

    // 最小值也可以这样算，但注意这也是在常数上的操作，右移位数超出范围了也会报上方错误
    min_int_2 := int(-1) << 63 // -9223372036854775808
    fmt.Println(min_int_2)

求一个基本数值类型的最小值，也可以从二进制码入手，我们知道一个有符号数值的最小值为 “符号位为 1，其余位皆为 0”（补码形式），所以可以 用一个全 1 的数整体向右移一位，首位补 0，再整体取反，来得到这个二进制码。由于 Go 中移位是带符号的，所以前面需要是不带符号类型，后面需要是带符号的类型。如

    // 另一种方式算得有符号数的最小值
    a := ^(^uint(0) >> 1) // -9223372036854775808
    fmt.Println(int(a))

提取一个无符号数的二进制形式的最右侧的 1

比如，一个数的二进制数 a 为 11011000，即要得出 00001000 这个数。

这个算法题可以先将 a 取反，则为 00100111，然后加 1，得到 00101000，我们对比一下：

11011000 // a
00100111 // ^a
00101000 // ^a+1
00001000 // a & (^a+1)

此时可以明显得看到 a&(^a+1) 就是我们所要的结果。

异或的妙用

首先来说说异或运算的性质

• 0^N == N
• N^N == 0
• 异或满足交换律、结合律

由以上三个性质，我们来介绍下异或的几个算法题：

• 找到一组数据中唯一出现奇数次的数
• 不用额外的变量实现两数交换
• 找到一组数据中有且仅有的两个出现奇数次的数

找到一组数据中唯一出现奇数次的数

由于异或有上述三条性质，所以可以有这样的推导公式：

a^b^c^b^a == (a^a)^(b^b)^c == 0^0^c == c

显然，在一组数据中有且仅有一个奇数次数据时，可以用它进行运算找出。

不用额外的变量实现两数交换

另外，异或上述的三条性质可以实现 不需要额外的变量即可实现两数交换，以下是证明过程：

    a := 345
    b := 564
    a = a ^ b         // a' => a^b
    b = a ^ b         // b' => a'^b == (a^b)^b == a^(b^b) == a
    a = b ^ a         // a'' => b'^a' == a^a^b == b
    fmt.Println(a, b) // 564 345

找到一组数据中有且仅有的两个出现奇数次的数

上面可以完成找出一组数据中有且仅有一个奇数次的数，但如何找出两个呢？

我们上面介绍了，可以通过数据全部异或，得到一个结果 A，其中出现偶数次的数相互异或后结果为 0，所以可以得出结论，这个结果 A 的某一个 bit 位是 1 的原因肯定是两个奇数次数值的 bit 位不一致引起的。

因为所有数它们的某一个 bit 位非 1 即 0，所以找结果 A 的任意一个为 1 的 bit 位，可以将整组数据分为两组：一组数据此 bit 位值为 1；另一组数据此 bit 位为 0。还可以得到结论：此 bit 位为 1 的数中，有且仅有一个数出现了奇数次；此 bit 位为 0 的数中，有且仅有一个数出现了奇数次。

于是，这这问题就回到了 有且仅有一个元素出现了奇数次 的问题上了。

所以此答案是这样的：

// 找出一组数据中有且仅有两个出现奇数次的数
func getTwoOddValue(arr []uint64) (uint64, uint64) {
    // 1 得到全部异或的结果
    xor := uint64(0)
    for _, e := range arr {
        xor ^= e
    }
    // 2 按 xor 的某一个 bit 位的值为 1 的位找出此元素
    // 2.1 找出此 bit 位为 1 的一个值
    singleBitVal := xor & (^xor + 1)
    // 2.2 找出此 bit 位为 1 的那个奇数次元素
    elem_1 := uint64(0)
    for _, e := range arr {
        if singleBitVal&e > 0 {
            elem_1 ^= e
        }
    }
    // 3 找出另一个元素
    elem_2 := elem_1 ^ xor
    return elem_1, elem_2
}

---

总结，这里介绍了位操作的一些用法。位操作是性能相当快的操作，而且它还有一些其他的妙用，这些在算法题中常常遇到。本文还介绍了几个简单的算法题：

• 找类型（无/有符号）的最大/小值
• 提取一个无符号数二进制形式的最右侧的 1
• 不用额外的空间实现两数交换
• 找出一组数据中唯一出现奇数次的一个数
• 找出一组数据中有且仅有两个出现奇数次的两个数