LeetCode 刷题必懂位运算
2023-02-02 算法
位运算
AND
表示将两个二进制数按位进行 与 运算，只有当两个对应的位都为 1 时，结果位才为 1，其他情况结果位为 0, Go 语言中使用运算符 &。
0000 0100 # 4 的二进制表示
0000 0111 # 7 的二进制表示
0000 0100 # 结果 = 4
// Go 语言表示
println(4 & 7)
OR
表示将两个二进制数按位进行 或 运算，只要两个对应的位任意一个为 1，结果位为 1，两个位都为 0 时，结果位才为 0, Go 语言中使用运算符 |。
0000 0100 # 4 的二进制表示
0000 0111 # 7 的二进制表示
0000 0111 # 结果 = 7
// Go 语言表示
println(4 | 7)
XOR
表示将两个二进制数按位进行 异或 运算，只有两个对应的位不相等时，结果位为 1，其他情况结果位为 0, Go 语言中使用运算符 ^。
0000 0100 # 4 的二进制表示
0000 0111 # 7 的二进制表示
0000 0011 # 结果 = 3
// Go 语言表示
println(4 ^ 7)
Complement
表示将二进制数按位进行 取反 运算，也就是每个位从 0 变成 1，1 变成 0, Go 语言中使用运算符 ^。
0111 1111 # 127 的二进制表示
1000 0000 # 取反之后 = -128
// Go 语言表示
println(^127)
对于有符号整型，最高位是是符号位，计算机用 补码 表示负数。
补码 = 原码取反 + 1
其中 原码 以负数的绝对值的二进制表示。
下面举两个例子来说明。
- 计算负数 -1 的二进制表示
# 计算 -1 的原码
# 原码以负数的绝对值 (1) 的二进制表示
# 所以 -1 的原码 = 00000001
# 将原码进行取反运算
00000001 # -1 原码
11111110 # 取反结果
# 在取反的结果上加 1
11111110 # 取反结果
11111111 # -1 的二进制表示
// Go 语言表示
println((^1) + 1)
- 计算 -128 的二进制表示
# 计算 -128 的原码
# 原码以负数的绝对值 (128) 的二进制表示
# 所以 -128 的原码 = 10000000
# 将原码进行取反运算
10000000 # -128 原码
01111111 # 取反结果
# 在取反的结果上加 1
01111111 # 取反结果
10000000 # -128 的二进制表示
// Go 语言表示
println((^128) + 1)
溢出
如果计算结果产生溢出，那么最高位溢出的部分会被省略掉。
11111111 # -1 的二进制表示
00000001 # 1 的二进制表示
00000000 # 0
10000000 # -128 的二进制表示
01111111 # 127 的二进制表示
11111111 # -1
位移
<< 表示左移，>> 表示右移。
数字 8 右移 2 位结果为 2。
0000 1000 # 8 的二进制表示
0000 0010 # 2
数字 8 左移 2 位结果为 32。
0000 1000 # 8 的二进制表示
0010 0000 # 32
将数字左移 1 位等于将该数字乘以 2, 因为在二进制中，左移 1 位就是将每个位向左移动 1 位，而每 1 位的位置都是 2 的幂，反过来说，将数字右移 1 位等于将该数字除以 2。
// Go 语言表示
println(8 >> 2) // 2
println(8 << 2) // 32
练习
1. 判断数字 K 第 n 位是否为 1
解题思路:
- 构造一个数字 X，该数字除了第 n 位为 1，其他位都为 0 (利用左移)
- 将数字 K 与数字 X 进行
&运算并判断结果是否大于 0, 如果大于 0, 表示数字 K 的第 n 位为 1, 否则表示数字 K 的第 n 位为 0
例如分别测试数字 7 的第 2 位和第 3 位是否为 1:
# 检测 7 的第 2 位是否为 1
0000 0111 # 7 的二进制表示
0000 0100 # 构造的数字，除了第 2 位，其他位全部为 0
0000 0100 # 结果为 4, 表示 7 的第 2 位等于 1
# 检测 7 的第 3 位是否为 1
0000 0111 # 7 的二进制表示
0000 1000 # 构造的数字，除了第 3 位，其他位全部为 0
0000 0000 # 结果为 0, 表示 7 的第 3 位不等于 1
// Go 语言表示
println(7 & (1 << 2))
println(7 & (1 << 3))
2. 判断数字 K 是否为 2 的整数次幂
解题思路:
首先看一下 2 的整数次幂都有什么特征？
0000 0010 # 2 的二进制表示
0000 0100 # 4 的二进制表示
0000 1000 # 8 的二进制表示
0001 0000 # 16 的二进制表示
特征就是二进制表示中只有 1 位为 1, 其他位全部为 0, 因此只需要构造一个数字 X, X 和 K 正好相反，只有 1 位为 0, 其他位全部为 1,
将数字 K 与数字 X 进行 & 运算并判断结果是否等于 0, 如果等于 0, 表示数字 K 等于 2 的整数次幂, 否则表示数字 K 不等于 2 的整数次幂。
0000 0010 # 2 的二进制表示
0000 0001 # 数字 X, 也就是 1 的二进制表示
0000 0100 # 4 的二进制表示
0000 0011 # 数字 X, 也就是 3 的二进制表示
0000 1000 # 8 的二进制表示
0000 0111 # 数字 X, 也就是 7 的二进制表示
0001 0000 # 16 的二进制表示
0000 1111 # 数字 X, 也就是 15 的二进制表示
从上面的代码中可以看到，X 其实就是 K-1, 在这个基础上再执行 & 运算即可。
0000 1000 # 8 的二进制表示
0000 0111 # 数字 X, 也就是 7 的二进制表示
# 执行 & 运算
0000 1000 # 8 的二进制表示
0000 0111 # 7 的二进制表示
0000 0000 # 0 结果等于 0, 表示 8 等于 2 的整数次幂
// Go 语言表示
println(8&(8-1) == 0) // true
println(7&(7-1) == 0) // false
通过上面的梳理过程，可以变化出另外一个小技巧: 将二进制表示中最右边为 1 的位置为 0:
0000 0111 # 7 的二进制表示
0000 0110 # 6 的二进制表示
# 执行 & 运算
0000 0111 # 7 的二进制表示
0000 0110 # 6 的二进制表示
0000 0110 # 6, 最右边为 1 的位已经被重置为 0
// Go 语言表示
println(7&(7-1))
3. 判断数字 k 的二进制需要改变多少位可以变为数字 n
解题思路:
- 计算出数字 k 和 n 有多少不同的位 (使用异或运算)
- 异或计算时，只有两个对应的位不相等时，结果位为 1，其他情况结果位为 0
- 计算结果中位等于 1 的个数，就是数字 k 需要改变的位数量
0000 0111 # 7 的二进制表示
0000 0110 # 6 的二进制表示
# 执行 ^ 异或运算
0000 0111 # 7 的二进制表示
0000 0110 # 6 的二进制表示
0000 0001 # 结果二进制中只有 1 位为 1
所以数字 7 需要改变 1 位可以变为数字 6, 反过来也一样。
// Go 语言表示
func countBits(n int) int {
count := 0
for n != 0 {
count += n & 1 // 如果最低位为1，则计数增加
n >>= 1 // 右移一位
}
return count
}
func main() {
println(countBits(7 ^ 6)) // 1
}
Go 标准库中的位运算
文章的最后介绍下 Go 语言中和位运算相关的方法。
打印二进制表示
fmt.Printf("%08b\n", 7) // 00000111
计算数字的二进制表示长度
fmt.Println(bits.Len(7)) // 3
fmt.Println(bits.Len(16)) // 5
计算数字的二进制表示中位为 1 的个数
// 7 的二进制表示: 0111, 有 3 位为 1
fmt.Println(bits.OnesCount(7)) // 3
计算数字的二进制表示中位为 0 的个数
// 7 的二进制表示: 1000, 有 3 位为 0
fmt.Println(bits.Len(8) - bits.OnesCount(8)) // 3
反转数字的二进制表示中的所有位
fmt.Printf("%08b\n", 7) // 00000111
fmt.Printf("%08b\n", bits.Reverse8(7)) // 11100000
检查数字的二进制表示中位为 0 的数量
var x uint8 = 16
fmt.Printf("%08b\n", x) // 00010000
// 返回从最高位开始到第一个位为 1 之间 0 的数量
fmt.Println("LeadingZeros:", bits.LeadingZeros8(x)) // 3
// 返回从最低位开始到第一个位为 1 之间 0 的数量
fmt.Println("TrailingZeros:", bits.TrailingZeros8(x)) // 4
扩展阅读
