技术图文：位运算技术在求解算法题中的应用

背景

前段时间，在知识星球立了一个Flag，这是总结Leetcode刷题的第一篇图文。

在总结这篇图文的时候，顺便把遇到的坑写了两篇辅助的图文，大家可以参考一下：

• 有符号整型的数据范围为什么负数比正数多一个？
• Python 位运算防坑指南

理论部分

1. 原码、反码和补码

二进制有三种不同的表示形式：原码、反码和补码，计算机内部使用补码来表示。

原码：就是其二进制表示（注意，有一位符号位）。

00 00 00 11 -> 3
10 00 00 11 -> -3

反码：正数的反码就是原码，负数的反码是符号位不变，其余位取反（对应正数按位取反）。

00 00 00 11 -> 3
11 11 11 00 -> -3

补码：正数的补码就是原码，负数的补码是反码+1。

00 00 00 11 -> 3
11 11 11 01 -> -3

符号位：最高位为符号位，0表示正数，1表示负数。在位运算中符号位也参与运算。

2. 按位非操作 ~

~ 1 = 0
~ 0 = 1

~ 把num的补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）有符号整数的符号位在 ~ 运算中同样会取反。

00 00 01 01 -> 5
~
---
11 11 10 10 -> -611 11 10 11 -> -5
~
---
00 00 01 00 -> 4

3. 按位与操作 &

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

只有两个对应位都为 1 时才为 1

00 00 01 01 -> 5
&
00 00 01 10 -> 6
---
00 00 01 00 -> 4

4. 按位或操作 |

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

只要两个对应位中有一个 1 时就为 1

00 00 01 01 -> 5
|
00 00 01 10 -> 6
---
00 00 01 11 -> 7

5. 按位异或操作 ^

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

只有两个对应位不同时才为 1

00 00 01 01 -> 5
^
00 00 01 10 -> 6
---
00 00 00 11 -> 3

异或操作的性质：满足交换律和结合律

A: 00 00 11 00
B: 00 00 01 11A^B: 00 00 10 11
B^A: 00 00 10 11A^A: 00 00 00 00
A^0: 00 00 11 00A^B^A: = A^A^B = B = 00 00 01 11

6. 按位左移操作 <<

num << i 将num的二进制表示向左移动i位所得的值。

00 00 10 11 -> 11
11 << 3
---
01 01 10 00 -> 88 

7. 按位右移操作 >>

num >> i 将num的二进制表示向右移动i位所得的值。

00 00 10 11 -> 11
11 >> 2
---
00 00 00 10 -> 2 

8. 利用位运算实现快速计算

通过 <<，>> 快速计算2的倍数问题。

n << 1 -> 计算 n*2
n >> 1 -> 计算 n/2，负奇数的运算不可用
n << m -> 计算 n*(2^m)，即乘以 2 的 m 次方
n >> m -> 计算 n/(2^m)，即除以 2 的 m 次方
1 << n -> 2^n

通过 ^ 快速交换两个整数。

a ^= b
b ^= a
a ^= b

通过 a & (-a) 快速获取a的最后为 1 位置的整数。

00 00 01 01 -> 5
&
11 11 10 11 -> -5
---
00 00 00 01 -> 100 00 11 10 -> 14
&
11 11 00 10 -> -14
---
00 00 00 10 -> 2

9. 利用位运算实现整数集合

一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。

比如集合 {1, 3, 4, 8}，可以表示成 01 00 01 10 10 而对应的位运算也就可以看作是对集合进行的操作。

元素与集合的操作：

a | (1<<i)  -> 把 i 插入到集合中
a & ~(1<<i) -> 把 i 从集合中删除
a & (1<<i)  -> 判断 i 是否属于该集合（零不属于，非零属于）

集合之间的操作：

a 补   -> ~a
a 交 b -> a & b
a 并 b -> a | b
a 差 b -> a & (~b)

应用部分

题目1：只出现一次的数字

• 题号：136
• 难度：简单
• https://leetcode-cn.com/problems/single-number/

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

思路： 利用"异或"操作的性质。

A: 00 00 11 00
B: 00 00 01 11A^A: 00 00 00 00
A^0: 00 00 11 00A^B^A: = A^A^B = B = 00 00 01 11

C# 实现

• 状态：通过
• 16 / 16 个通过测试用例
• 执行用时: 144 ms, 在所有 C# 提交中击败了 91.76% 的用户
• 内存消耗: 25.4 MB, 在所有 C# 提交中击败了 11.39% 的用户

public class Solution
{public int SingleNumber(int[] nums){int result = 0;for (int i = 0; i < nums.Length; i++){result ^= nums[i];}return result;}
}

Python 实现

• 执行结果：通过
• 执行用时：44 ms, 在所有 Python3 提交中击败了 84.17% 的用户
• 内存消耗：15.3 MB, 在所有 Python3 提交中击败了 5.26% 的用户

class Solution:def singleNumber(self, nums: List[int]) -> int:result = 0for item in nums:result ^= itemreturn result

题目2：2的幂

• 题号：231
• 难度：简单
• https://leetcode-cn.com/problems/power-of-two/

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 2^0 = 1

示例 2:

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

输入: 218
输出: false

思路： 利用"异或"操作的性质。

A: 00 00 11 00A^A: 00 00 00 00

C# 语言

• 状态：通过
• 1108 / 1108 个通过测试用例
• 执行用时: 36 ms, 在所有 C# 提交中击败了 100.00% 的用户
• 内存消耗: 14.7 MB, 在所有 C# 提交中击败了 100.00% 的用户

public class Solution
{public bool IsPowerOfTwo(int n){if (n < 0)return false;for (int i = 0; i < 32; i++){int mask = 1 << i;if ((n ^ mask) == 0)return true;}return false;}
}

Python 语言

• 执行结果：通过
• 执行用时：44 ms, 在所有 Python3 提交中击败了 51.91% 的用户
• 内存消耗：13.6 MB, 在所有 Python3 提交中击败了 6.25% 的用户

class Solution:def isPowerOfTwo(self, n: int) -> bool:for i in range(32):mask = 1 << iif n ^ mask == 0:return Truereturn False

题目3：只出现一次的数字 III

• 题号：260
• 难度：中等
• https://leetcode-cn.com/problems/single-number-iii/

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路： 利用"异或"操作的性质。

通过异或操作 ^ 去除掉恰好重复出现两次的元素，这时得到两个只出现一次整数的异或结果different。

A: 00 00 11 00
B: 00 00 01 11A^B: 00 00 10 11
B^A: 00 00 10 11A^A: 00 00 00 00
A^0: 00 00 11 00A^B^A: = A^A^B = B = 00 00 01 11

获取different二进制中最后一位1，通过该位，可以把这两个数分离出来，这两个数在该位是不同的。也即通过该位把 nums 分成了两组，该位是 1 的一组，该位是 0 的一组，然后求两组中只出现一次的整数。

通过 a & (-a) 快速获取a的最后为 1 位置的整数。

00 00 01 01 -> 5
&
11 11 10 11 -> -5
---
00 00 00 01 -> 100 00 11 10 -> 14
&
11 11 00 10 -> -14
---
00 00 00 10 -> 2

C# 语言

• 执行结果：通过
• 执行用时：280 ms, 在所有 C# 提交中击败了 83.33% 的用户
• 内存消耗：31.2 MB, 在所有 C# 提交中击败了 100.00% 的用户

public class Solution
{public int[] SingleNumber(int[] nums){if (nums.Length < 2)return new int[2];int different = 0;for (int i = 0; i < nums.Length; i++){different ^= nums[i];}different &= -1 * different;int num1 = 0, num2 = 0;for (int i = 0; i < nums.Length; i++){if ((different & nums[i]) == 0){num1 ^= nums[i];}else{num2 ^= nums[i];}}return new int[] { num1, num2 };}
}

Python 语言

• 执行结果：通过
• 执行用时：44 ms, 在所有 Python3 提交中击败了 83.70% 的用户
• 内存消耗：14.8 MB, 在所有 Python3 提交中击败了 33.33% 的用户

class Solution:def singleNumber(self, nums: List[int]) -> List[int]:if len(nums) < 2:return []different = 0for num in nums:different ^= numdifferent &= -1 * differentnum1, num2 = 0, 0for num in nums:if (num & different) == 0:num1 ^= numelse:num2 ^= numreturn [num1, num2]

题目4：子集

• 题号：78
• 难度：中等
• https://leetcode-cn.com/problems/subsets/

给定一组 不含重复元素 的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

思路： 利用整数集合的思路。

以{1,2,3}为例，三个数，共2^3个子集。

000 -> []
100 -> [1]
101 -> [1,3]
110 -> [1,2]
111 -> [1,2,3]
...

C# 语言

• 状态：通过
• 10 / 10 个通过测试用例
• 执行用时: 348 ms, 在所有 C# 提交中击败了 97.80% 的用户
• 内存消耗: 29.5 MB, 在所有 C# 提交中击败了 6.67% 的用户

public class Solution
{public IList<IList<int>> Subsets(int[] nums){IList<IList<int>> result = new List<IList<int>>();int count = nums.Length;for (int i = 0; i < 1 << count; i++){IList<int> item = new List<int>();for (int j = 0; j < count; j++){int mask = 1 << j;if ((mask & i) != 0)item.Add(nums[j]);}result.Add(item);}return result;}
}

Python 语言

• 执行结果：通过
• 执行用时：40 ms, 在所有 Python3 提交中击败了 63.08% 的用户
• 内存消耗：13.8 MB, 在所有 Python3 提交中击败了 5.72% 的用户

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:count = len(nums)result = []for i in range(1 << count):item = []for j in range(count):mask = 1 << jif (mask & i) != 0:item.append(nums[j])result.append(item)return result

题目5：Pow(x, n)

• 题号：50
• 难度：中等
• https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

示例 4:

输入: 1.00000, -2147483648
输出: 1.00000

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

思路：利用快速幂法。

假设我们要求a^b，那么b可以拆成二进制表示，例如当b = 5时，5的二进制是0101，5 = 2^3×0 + 2^2×1 + 2^1×0 + 2^0×1，因此，我们将a^5转化为算 a^(2^3×0 + 2^2×1 + 2^1×0 + 2^0×1)，即a^(2^0) × a^(2^2)。

我们先算出所有2的幂，然后在算出所有x的2的幂次方。再把n拆成二进制，把二进制当中对应位置是1的值乘起来，就得到了结果。这套方法称为 快速幂法。

C# 实现

• 执行结果：通过
• 执行用时：56 ms, 在所有 C# 提交中击败了 51.87% 的用户
• 内存消耗：15.1 MB, 在所有 C# 提交中击败了 50.00% 的用户

public class Solution
{public double MyPow(double x, int n){int neg = n < 0 ? -1 : 1;long g = Math.Abs((long)n);double[] d = new double[32];d[0] = x;for (int i = 1; i < 32; i++){d[i] = d[i - 1] * d[i - 1];}double result = 1.0d;for (int i = 0; i < 32; i++){int mask = 1 << i;if ((mask & g) != 0){result *= d[i];}}return neg != -1 ? result : 1.0 / result;}
}

注意：long g = Math.Abs((long)n);需要把n转换成long，因为Math.Abs(int.MinValue)会产生溢出错误。

Python 实现

• 执行结果：通过
• 执行用时：36 ms, 在所有 Python3 提交中击败了 75.02% 的用户
• 内存消耗：13.8 MB, 在所有 Python3 提交中击败了 8.33% 的用户

class Solution:def myPow(self, x: float, n: int) -> float:neg = -1 if n < 0 else 1n = abs(n)d = list()d.append(x)for i in range(1, 32):d.append(d[-1] * d[-1])result = 1.0for i in range(32):mask = 1 << iif (mask & n) != 0:result *= d[i]return result if neg != -1 else 1.0 / result

题目6：只出现一次的数字 II

• 题号：137
• 难度：中等
• https://leetcode-cn.com/problems/single-number-ii/

给定一个 非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

思路：

初始result = 0，将每个数想象成 32 位的二进制，对于每一位的二进制的1累加起来必然是3N或者3N + 1(出现3次和1次)；3N代表目标值在这一位没贡献，3N + 1代表目标值在这一位有贡献（=1），然后将所有有贡献的位记录到result中。这样做的好处是如果题目改成k个一样，只需要把代码改成count % k即可，很通用并列去找每一位。

C# 语言

• 执行结果：通过
• 执行用时：112 ms, 在所有 C# 提交中击败了 91.53% 的用户
• 内存消耗：25.2 MB, 在所有 C# 提交中击败了 100.00% 的用户

public class Solution
{public int SingleNumber(int[] nums){int result = 0;for (int i = 0; i < 32; i++){int mask = 1 << i;int count = 0;for (int j = 0; j < nums.Length; j++){if ((nums[j] & mask) != 0){count++; }}if (count % 3 != 0){result |= mask;}}return result;}
}

Python 语言

class Solution:def singleNumber(self, nums: List[int]) -> int:result = 0for i in range(32):mask = 1 << icount = 0for num in nums:if num & mask != 0:count += 1if count % 3 != 0:result |= maskreturn result

以上 Python 代码与 C# 代码逻辑完全一致，但提交时报错，错误信息如下：

输入：[-2,-2,1,1,-3,1,-3,-3,-4,-2]
输出：4294967292
预期结果：-4

我们发现：

-4 补码为 1111 1111 1111 1111 1111 1111 1111 1100

如果不考虑符号位

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292 

是不是很坑，C++，C#，Java等语言的整型是限制长度的，如：byte 8位，int 32位，long 64位，但 Python 的整型是不限制长度的（即不存在高位溢出），所以，当输出是负数的时候，会导致认为是正数！因为它把32位有符号整型认为成了无符号整型，真是坑。

我们对以上的代码进行修改，加入判断条件 if result > 2 ** 31-1: 超过32位整型的范围就表示负数了result -= 2 ** 32，即可得到对应的负数。

• 执行结果：通过
• 执行用时：96 ms, 在所有 Python3 提交中击败了 19.00% 的用户
• 内存消耗：14.8 MB, 在所有 Python3 提交中击败了 25.00% 的用户

class Solution:def singleNumber(self, nums: List[int]) -> int:result = 0for i in range(32):mask = 1 << icount = 0for num in nums:if num & mask != 0:count += 1if count % 3 != 0:result |= maskif result > 2 ** 31-1:result -= 2 ** 32return result

题目7：格雷编码

• 题号：89
• 难度：中等
• https://leetcode-cn.com/problems/gray-code/

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。给定编码总位数为 n 的格雷编码序列，其长度为 2^n。当 n = 0 时，长度为 2^0 = 1。因此，当 n = 0 时，其格雷编码序列为 [0]。

思路：

由 n 位推导 n+1 位结果时，n+1 位结果包含 n 位结果，同时包含 n 位结果中在高位再增加一个位 1 所形成的令一半结果，但是这一半结果需要与前一半结果镜像排列。

C# 语言

• 状态：通过
• 12 / 12 个通过测试用例
• 执行用时: 296 ms, 在所有 C# 提交中击败了 95.83% 的用户
• 内存消耗: 24.8 MB, 在所有 C# 提交中击败了 16.67% 的用户

public class Solution
{public IList<int> GrayCode(int n){IList<int> lst = new List<int>();lst.Add(0);for (int i = 1; i <= n; i++){for (int j = lst.Count - 1; j >= 0; j--){int item = lst[j] + (1 << i - 1);lst.Add(item);}}return lst;}
}

Python 语言

• 执行结果：通过
• 执行用时：44 ms, 在所有 Python3 提交中击败了 45.92% 的用户
• 内存消耗：13.8 MB, 在所有 Python3 提交中击败了 20.00% 的用户

class Solution:def grayCode(self, n: int) -> List[int]:lst = [0]for i in range(1, n + 1):count = len(lst)for j in range(count - 1, -1, -1):lst.append(lst[j] + (1 << i - 1))return lst

注意：运算符的优先级

• 一元运算符优于二元运算符。如正负号。
• 先算术运算，后移位运算，最后位运算。例如 1 << 3 + 2 & 7等价于 (1 << (3 + 2)) & 7
• 逻辑运算最后结合

总结

这篇图文总结了位运算技术并通过7道 Leetcode 题目演示了这些理论的具体应用。目前该 Flag 计划已经完成20%，要努力，要努力，千万不要陷入“习得性无助”的陷阱中。今天就到这里吧！See You！

参考文献

• https://oi-wiki.org/math/bit/
• https://www.zhihu.com/question/314455297
• https://mp.weixin.qq.com/s/c5Lf4cNT3i8CHT_tEPfQUw
• https://mp.weixin.qq.com/s/8aG4XwSxjMLG0TIbX_hBBQ

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

• Python基础刻意练习活动即将开启，你参加吗？
• Task01：变量、运算符与数据类型
• Task02：条件与循环
• Task03：列表与元组
• Task04：字符串与序列
• Task05：函数与Lambda表达式
• Task06：字典与集合
• Task07：文件与文件系统
• Task08：异常处理
• Task09：else 与 with 语句
• Task10：类与对象
• Task11：魔法方法
• Task12：模块

我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：