Datawhale Leecode基础算法篇 task05：位运算

官方学习文档：datawhalechina

往期task01：枚举算法链接：Datawhale Leecode基础算法篇 task01：枚举算法

往期task02：递归算法and分治算法：Datawhale Leecode基础算法篇 task02：递归算法and分治算法

往期task03：回溯算法：Datawhale Leecode基础算法篇 task03：回溯算法

往期task04:贪心算法：Datawhale Leecode基础算法篇 task04：贪心算法

位运算

位运算简介

位运算（Bit Operation）：在计算机内部，数是以「二进制（Binary）」的形式来进行存储。位运算就是直接对数的二进制进行计算操作，在程序中使用位运算进行操作，会大大提高程序的性能。

二进制数（Binary）：由 0 和 1 两个数码来表示的数。二进制数中每一个 0 或每一个 1 都称为一个「位（Bit）」。

在二进制数中，我们只有 0 和 1 两个数码，它的进位规则是「逢二进一」。

二进制转十进制数：

十进制转二进制数：

十进制数转二进制数的方法是：除二取余，逆序排列法。

具体可以参考这个视频：傻瓜式十进制转二进制，二进制转十进制

位运算基础操作

在二进制的基础上，我们可以对二进制数进行相应的位运算。基本的位运算共有 6 种，分别是：「按位与运算」、「按位或运算」、「按位异或运算」、「取反运算」、「左移运算」、「右移运算」。

这里的「按位与运算」、「按位或运算」、「按位异或运算」、「左移运算」、「右移运算」是双目运算。

「按位与运算」、「按位或运算」、「按位异或运算」是将两个整数作为二进制数，对二进制数表示中的每一位（即二进位）逐一进行相应运算，即双目运算。
「左移运算」、「右移运算」是将左侧整数作为二进制数，将右侧整数作为移动位数，然后对左侧二进制数的全部位进行移位运算，每次移动一位，总共移动右侧整数次位，也是双目运算。

而「取反运算」是单目运算，是对一个整数的二进制数进行的位运算。

我们先来看下这 6 种位运算的规则，再来进行详细讲解。

运算符	描述	规则
`\|`	按位或运算符	只要对应的两个二进位有一个为 1 时，结果位就为 1。
`&`	按位与运算符	只有对应的两个二进位都为 1 时，结果位才为 1。
`<<`	左移运算符	将二进制数的各个二进位全部左移若干位。`<<` 右侧数字指定了移动位数，高位丢弃，低位补 0。
`>>`	右移运算符	对二进制数的各个二进位全部右移若干位。`>>` 右侧数字指定了移动位数，低位丢弃，高位补 0。
`^`	按位异或运算符	对应的两个二进位相异时，结果位为 1，二进位相同时则结果位为 0。
`~`	取反运算符	对二进制数的每个二进位取反，使数字 1 变为 0，0 变为 1。

位运算的应用

判断整数奇偶

一个整数，只要是偶数，其对应二进制数的末尾一定为 0；只要是奇数，其对应二进制数的末尾一定为 1。所以，我们通过与 1 进行按位与运算，即可判断某个数是奇数还是偶数。

(x & 1) == 0 为偶数。
(x & 1) == 1 为奇数。

二进制数选取指定位

如果我们想要从一个二进制数 X 中取出某几位，使取出位置上的二进位保留原值，其余位置为 0。

则可以使用另一个二进制数 Y，使该二进制数上对应取出位置为 1，其余位置为 0。然后令两个数进行按位与运算（X & Y），即可得到想要的数。

我们要取二进制数 X=01101010(2) 的末尾 4 位，则只将 X=01101010(2) 与 Y=00001111(2) (末尾 4 位为 1，其余位为 0) 进行按位与运算，即 01101010 & 00001111 == 00001010。其结果 00001010 就是我们想要的数（即二进制数 01101010(2) 的末尾 4 位）。

将指定位设置为 1

如果我们想要把一个二进制数 X 中的某几位设置为 1，其余位置保留原值，则可以使用另一个二进制数 Y，使得该二进制上对应选取位置为 1，其余位置为 0。然后令两个数进行按位或运算（X | Y），即可得到想要的数。

举个例子，比如我们想要将二进制数 X=01101010(2) 的末尾 4 位设置为 1，其余位置保留原值，则只需将 X=01101010(2) 与 Y=00001111(2)（末尾 4 位为 1，其余位为 0）进行按位或运算，即 01101010 | 00001111 = 01101111。其结果 01101111 就是我们想要的数（即将二进制数 01101010(2) 的末尾 4 位设置为 1，其余位置保留原值）。

反转指定位

如果我们想要把一个二进制数 X 的某几位进行反转，则可以使用另一个二进制数 Y，使得该二进制上对应选取位置为 1，其余位置为 0。然后令两个数进行按位异或运算（X ^ Y），即可得到想要的数。

1对0得1,0对0得0，保持原值

1对1得0,0对1得1，数值反转

举个例子，比如想要将二进制数 X=01101010(2) 的末尾 4 位进行反转，则只需将 X=01101010(2) 与 Y=00001111(2)（末尾 4 位为 1，其余位为 0）进行按位异或运算，即 01101010 ^ 00001111 = 01100101。其结果 01100101 就是我们想要的数（即将二进制数 X=01101010(2) 的末尾 4 位进行反转）。

交换两个数

通过按位异或运算可以实现交换两个数的目的（只能用于交换两个整数）。

a, b = 10, 20
a ^= b
b ^= a
a ^= b
print(a, b)

将二进制最右侧为 1 的二进位改为 0（即从右向左数第一个1改为0）

如果我们想要将一个二进制数 X 最右侧为 1 的二进制位改为 0，则只需通过 X & (X - 1) 的操作即可完成。

比如 X=01101100(2)，(X-1)=01101011，则 X & (X - 1) == 01101100 & 01101011 == 01101000，结果为 01101000(2)（即将 X 最右侧为 1 的二进制为改为 0）。

计算二进制中二进位为 1 的个数

如上通过 X & (X - 1) 我们可以将二进制 X 最右侧为 1 的二进制位改为 0，那么如果我们不断通过 X & (X - 1) 操作，最终将二进制 X 变为 0，并统计执行次数，则可以得到二进制中二进位为 1 的个数。

具体代码如下：

class Solution:def hammingWeight(self, n: int) -> int:cnt = 0while n:n = n & (n - 1)cnt += 1return cnt

判断某数是否为 2 的幂次方

通过判断 X & (X - 1) == 0 是否成立，即可判断 X 是否为 2 的幂次方。

这是因为：

凡是 2 的幂次方，其二进制数的某一高位为 1，并且仅此高位为 1，其余位都为 0。比如： $4_{(10)} = 00000100_{(2)}$ 、 $8_{(10)} = 00001000_{(2)}$ 。
不是 2 的幂次方，其二进制数存在多个值为 1 的位。比如： $5_{10} = 00000101_{(2)}$ 、 $6_{10} = 00000110_{(2)}$ 。

我们使用 X & (X - 1) 操作，将原数对应二进制数最右侧为 1 的二进位改为 0 之后，得到新值，若原数是 2 的幂次方，则通过 X & (X - 1) 操作之后，新值所有位都为 0，值为 0；反之值不为0则不是 2 的幂次方。

位运算的常用操作总结

功能	位运算	示例
从右边开始，把最后一个 1 改写成 0	`x & (x - 1)`	`100101000 -> 100100000`
去掉右边起第一个 1 的左边	`x & (x ^ (x - 1))` 或 `x & (-x)`	`100101000 -> 1000`
去掉最后一位	`x >> 1`	`101101 -> 10110`
取右数第 k 位	`x >> (k - 1) & 1`	`1101101 -> 1, k = 4`
取末尾 3 位	`x & 7`	`1101101 -> 101`
取末尾 k 位	`x & 15`	`1101101 -> 1101, k = 4`
只保留右边连续的 1	`(x ^ (x + 1)) >> 1`	`100101111 -> 1111`
右数第 k 位取反	`x ^ (1 << (k - 1))`	`101001 -> 101101, k = 3`
在最后加一个 0	`x << 1`	`101101 -> 1011010`
在最后加一个 1	`(x << 1) + 1`	`101101 -> 1011011`
把右数第 k 位变成 0	`x & ~(1 << (k - 1))`	`101101 -> 101001, k = 3`
把右数第 k 位变成 1	`x \| (1 << (k - 1))`	`101001 -> 101101, k = 3`
把右边起第一个 0 变成 1	`x \| (x + 1)`	`100101111 -> 100111111`
把右边连续的 0 变成 1	`x \| (x - 1)`	`11011000 -> 11011111`
把右边连续的 1 变成 0	`x & (x + 1)`	`100101111 -> 100100000`
把最后一位变成 0	`x \| 1 - 1`	`101101 -> 101100`
把最后一位变成 1	`x \| 1`	`101100 -> 101101`
把末尾 k 位变成 1	`x \| (1 << k - 1)`	`101001 -> 101111, k = 4`
最后一位取反	`x ^ 1`	`101101 -> 101100`
末尾 k 位取反	`x ^ (1 << k - 1)`	`101001 -> 100110, k = 4`

二进制枚举子集

除了上面的这些常见操作，我们经常常使用二进制数第 1∼n 位上 0 或 1 的状态来表示一个由 1∼n 组成的集合。也就是说通过二进制来枚举子集。

枚举子集的方法有很多，这里介绍一种简单有效的枚举方法：「二进制枚举子集算法」。

对于一个元素个数为 n 的集合 S 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 1 来表示选取该元素，用数字 0 来表示不选取该元素。

对应代码：

class Solution:def subsets(self, S):                   # 返回集合 S 的所有子集n = len(S)                          # n 为集合 S 的元素个数sub_sets = []                       # sub_sets 用于保存所有子集for i in range(1 << n):             # 枚举 0 ~ 2^n - 1sub_set = []                    # sub_set 用于保存当前子集for j in range(n):              # 枚举第 i 位元素if i >> j & 1:              # 如果第 i 为元素对应二进位删改为 1，则表示选取该元素sub_set.append(S[j])    # 将选取的元素加入到子集 sub_set 中sub_sets.append(sub_set)        # 将子集 sub_set 加入到所有子集数组 sub_sets 中return sub_sets                     # 返回所有子集

for i in range(1 << n):：这里使用了位移运算符<<，1 << n相当于2的n次幂，即从0开始枚举到2^n - 1。因为对于一个长度为n的集合，其子集的数量为2^n，所以我们可以通过遍历0到2^n - 1之间的整数来得到所有子集。

if i >> j & 1:：检查当前枚举的整数i的第j位是否为1。i >> j表示将i向右移动j位，& 1则是与1做位与操作，如果结果为1，则表示原数i的第j位为1，也就是说我们选择了集合S的第j个元素。

sub_set.append(S[j])：如果第j位为1，那么将集合S的第j个元素添加到当前子集sub_set中。

那我们本期的学习在这里就短暂结束了，天涯何处不相逢，我们下次再见！