算法题Python常用内置函数、方法、技巧汇总（其七：位运算）

位运算

整数类型的变量int在内存中是按照二进制的方式进行存储的，位运算指的就是直接对整数在内存中的二进制位进行操作。

我们可以把二进制中数字和布尔类型进行类比，把位运算符和布尔运算符进行类比。这样更容易理解。

假设要对两个数字a和b进行位运算，那么应该先将其转化为两个二进制数（仅包含0和1的两个二进制数），然后逐位地根据运算符进行运算，得到一个新的二进制数，再将其转换为十进制数即为结果。

与运算

与运算的符号是&。

参与运算的两个数，如果两个相对应的位的均为1，那么该位的运算结果为1，否则为0。即有如下表格

	0	1
0	0	0
1	0	1

即两个位置只要有一个不为1，结果就不为1。

举个例子，3 & 5 = 1，其计算过程如下。

或运算

或运算的符号是|。

参与运算的两个数，如果两个相对应的位的均为0，那么该位的运算结果为0，否则为1。即有如下表格

	0	1
0	0	1
1	1	1

即两个位置只要有一个不为0，结果就不为0。

举个例子，3 | 5 = 7，其计算过程如下。

异或运算

异或运算的符号是^。

参与运算的两个数，如果两个相对应的位相等，那么该位的运算结果为0，否则为1。即有如下表格

	0	1
0	0	1
1	1	0

即两个位置相等时，结果为0，不相等时，结果为1。

举个例子，3 ^ 5 = 6，其计算过程如下。

特别地，对于任意整数a，存在 a ^ a = 0 和 a ^ 0 = a 成立。

左移运算和右移运算

左移运算的符号是<<。

num << n表示是转换成二进制数的num整体向左移动n位，最右边空出来的位置用0补齐。

以5 << 2 = 20 为例，其计算过程如下。

右移运算的符号是>>。

num >> n表示是转换成二进制数的num整体向右移动n位，最右边的n位删除。

以23 >> 2 = 5 为例，其计算过程如下。

显然， num >> 1 等价于 num // 2。

位运算定律

任意位运算均满足交换律。即存在

a & b = b & a
a | b = b | a
a ^ b = b ^ a

任意位运算均满足结合律。即存在

(a & b) & c = a & (b & c)
(a | b) | c = a | (b | c)
(a ^ b) ^ c = a ^ (b ^ c)

判断n是否为2的幂

若数字n为2的幂，即存在$$n=2^k$$成立，那么其二进制的首位一定是1，后面包含了k个0。

如16 = 0b10000，其二进制的首位为1，后面包含了4个0。

如果考虑n-1的二进制，容易发现其位数应该比n少1，同时均为1构成。

如15 = 0b1111，其二进制为4个1

由于只有当n是2的幂，才会具备上述性质，我们可以使用与运算来判断n是否为2的幂。

当且仅当 n & (n-1) == 0 成立时，n为2的幂。题目 LeetCode231. 2 的幂 即使用到该技巧。

同理，如果要判断n的二进制是否均由1构成，也可以用类似的方法判断。

当且仅当n & (n+1) == 0 成立时，n的二进制均由1构成。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多