理论基础
异或运算⊕有以下三个性质：
-
任何数和 0 做异或运算，结果仍然是原来的数，即 $a⊕0=a$
-
任何数和其自身做异或运算，结果是 0，即 $a⊕a=0$
-
异或运算满足交换律和结合律，即 $a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b$
& 表示按位与，∣ 表示按位或，⊕ ^表示按位异或，∼ 表示按位取反
移位运算：其中 << 表示左移，>> 表示右移
注：左移 𝑖 位相当于乘以 2𝑖，右移 𝑖 位相当于除以 2𝑖
只出现一次的数字
136. 只出现一次的数字 - 力扣（LeetCode）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间
思路：数组中的全部元素的异或运算结果即为数组中只出现一次的数字。两两相同异或为0，任何数异或0为自身
1
2
3
4
5
6
7
|
func singleNumber(nums []int) int {
res := nums[0]
for i := 1; i < len(nums); i++ {
res ^= nums[i]
}
return res
}
|
只出现一次的数字 II
137. 只出现一次的数字 II - 力扣（LeetCode）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间
思路：
设只出现一次的那个数为 x。用二进制思考：
这启发我们统计每个比特位上有多少个 1。下图比较了上题与本题的异同：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func singleNumber(nums []int) int {
// 结果集初始化为一个32位整数0
res := int32(0)
// 遍历结果集的32个位
for i := 0; i < 32; i++ {
// 记录各个位上1的个数
count := 0
// 遍历给定数组
for _, v := range nums {
// 右移后累加最低位的值
count += v >> i & 1
}
// 设置结果数的第i位
res |= int32(count) % 3 << i
}
return int(res)
}
|
只出现一次的数字 III
260. 只出现一次的数字 III - 力扣（LeetCode）
给定一个非空整数数组，其中恰好有两个元素只出现一次，其余每个元素均出现两次。找出只出现一次的那两个元素。必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间
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
|
func singleNumber(nums []int) []int {
// 保存两个结果数的异或值
xorAll := 0
// 遍历数组
for _, v := range nums {
xorAll ^= v
}
// 定位异或值最后一个1的索引
idx := 0
// 从右向左找1
for i := 0; i < 32; i++ {
if (xorAll >> i & 1) == 1 {
// 保存1的索引
idx = i
break
}
}
// 二进制 -> 十进制
idx = 1 << idx
res := make([]int, 2)
// 遍历数组
for _, v := range nums {
// 分组异或
if v&idx == 0 {
res[0] ^= v
} else {
res[1] ^= v
}
}
return res
}
|
位1的个数
191. 位1的个数 - 力扣（LeetCode）
给定一个十进制整数，返回其二进制形式中1的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func hammingWeight(n int) int {
res := 0
// n循环右移直到为0
for n != 0 {
// 判断最低位是否为1
if n&1 == 1 {
res++
}
// n右移一位
n >>= 1
}
return res
}
|
比特位计数
338. 比特位计数 - 力扣（LeetCode）
给定一个整数n，返回一个数组，每个元素表示0-n的每个数二进制形式中1的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func countBits(n int) []int {
res := make([]int, n+1)
// 遍历0-n
for i := 0; i <= n; i++ {
// 该数循环右移直至0
for cur := i; cur != 0; cur >>= 1 {
// 判断最低位是否为1
if cur&1 == 1 {
res[i]++
}
}
}
return res
}
|
颠倒二进制位
190. 颠倒二进制位 - 力扣（LeetCode）
颠倒给定的 32 位无符号整数的二进制位
1
2
3
4
5
6
7
8
9
10
11
12
|
func reverseBits(num uint32) uint32 {
newNum := uint32(0)
// 从右向左遍历num的32位
for i := 0; i < 32; i++ {
// num右移一位后判断最低位是否为1
if (num >> i & 1) == 1 {
// 置newNum对称位为1
newNum |= 1 << (31 - i)
}
}
return newNum
}
|
数字范围按位与
201. 数字范围按位与 - 力扣（LeetCode）
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）
思路一：暴力，一个for循环遍历区间，直接按位与（超时）
1
2
3
4
5
6
7
8
9
|
func rangeBitwiseAnd(left int, right int) int {
res := left
// 遍历区间所有数字
for i := left + 1; i <= right; i++ {
// 按位与
res &= i
}
return res
}
|
思路二：找公共前缀
观察按位与运算的性质，对于一列的位，只要有一个零值的位，那么这一列位的按位与运算结果都将为零。
在上图中发现，对所有数字执行按位与运算的结果是所有对应二进制的公共前缀再用零补上后面的剩余位，因此，最终可以将问题重新表述为：给定两个整数，找到它们对应的二进制字符串的公共前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func rangeBitwiseAnd(left int, right int) int {
// 记录右移的次数
count := 0
// 两个区间端点数字不断右移直到相等
for left != right {
// 右移一位
left >>= 1
right >>= 1
// 右移次数加一
count++
}
// 左移恢复高位
return left << count
}
|