Skip to content

Latest commit

 

History

History
318 lines (198 loc) · 19.8 KB

File metadata and controls

318 lines (198 loc) · 19.8 KB

1. 位运算简介

1.1 位运算与二进制简介

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

在学习二进制数的位运算之前,我们先来了解一下什么叫做「二进制数」。

二进制数(Binary):由 $0$$1$ 两个数码来表示的数。二进制数中每一个 $0$ 或每一个 $1$ 都称为一个「位(Bit)」。

我们通常使用的十进制数有 $0 \sim 9$$10$ 个数字,进位规则是「满十进一」。例如:

  1. $7_{(10)} + 2_{(10)} = 9_{(10)}$:$7_{(10)}$ 加上 $2_{(10)}$ 等于 $9_{(10)}$
  2. $9_{(10)} + 2_{(10)} = 11_{(10)}$:$9_{(10)}$ 加上 $2_{(10)}$ 之后个位大于等于 $10$,符合「满十进一」,结果等于 $11_{(10)}$

而在二进制数中,我们只有 $0$$1$ 两个数码,它的进位规则是「逢二进一」。例如:

  1. $1_{(2)} + 0_{(2)} = 1_{(2)}$:$1_{(2)}$ 加上 $0_{(2)}$ 等于 $1_{(2)}$
  2. $1_{(2)} + 1_{(2)} = 10_{(2)}$:$1_{(2)}$ 加上 $1_{(2)}$,大于等于 $2$,符合「逢二进一」,结果等于 $10_{(2)}$
  3. $10_{(2)} + 1_{(2)} = 11_{(2)}$

1.2 二进制数的转换

1.2.1 二进制转十进制数

在十进制数中,数字 $2749_{(10)}$ 可以理解为 $2 \times 1000 + 7 \times 100 + 4 \times 10 + 9 * 1$,相当于 $2 \times 10^3 + 7 \times 10^2 + 4 \times 10^1 + 9 \times 10^0$,即 $2000 + 700 + 40 + 9 = 2749_{(10)}$

同理,在二进制数中,$01101010_{(2)}$ 可以看作为 $(0 \times 2^7) + (1 \times 2^6) + (1 \times 2^5) + (0 \times 2^4) + (1 \times 2^3) + (0 \times 2^2) + (1 \times 2^1) + (0 \times 2^0)$,即 $0 + 64 + 32 + 0 + 8 + 0 + 2 + 0 = 106_{(10)}$

我们可以通过这样的方式,将一个二进制数转为十进制数。

1.2.2 十进制转二进制数

十进制数转二进制数的方法是:除二取余,逆序排列法

我们以十进制数中的 $106_{(10)}$ 为例。

$\begin{aligned} 106 \div 2 = 53 & \text{(余 0)} \cr 53 \div 2 = 26 & \text{(余 1)} \cr 26 \div 2 = 13 & \text{(余 0)} \cr 13 \div 2 = 6 & \text{(余 1)} \cr 6 \div 2 = 3 & \text{(余 0)} \cr 3 \div 2 = 1 & \text{(余 1)} \cr 1 \div 2 = 0 & \text{(余 1)} \cr 0 \div 2 = 0 & \text{(余 0)} \end{aligned}$

我们反向遍历每次计算的余数,依次是 $0$,$1$,$1$,$0$,$1$,$0$,$1$,$0$,即 $01101010_{(2)}$

2. 位运算基础操作

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

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

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

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

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

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

2.1 按位与运算

按位与运算(AND):按位与运算符为 &。其功能是对两个二进制数的每一个二进位进行与运算。

  • 按位与运算规则:只有对应的两个二进位都为 $1$ 时,结果位才为 $1$

    • 1 & 1 = 1

    • 1 & 0 = 0

    • 0 & 1 = 0

    • 0 & 0 = 0

举个例子,对二进制数 $01111100_{(2)}$$00111110_{(2)}$ 进行按位与运算,结果为 $00111100_{(2)}$,如图所示:

2.2 按位或运算

按位或运算(OR):按位或运算符为 |。其功能对两个二进制数的每一个二进位进行或运算。

  • 按位或运算规则:只要对应的两个二进位有一个为 $1$ 时,结果位就为 $1$
    • 1 | 1 = 1
    • 1 | 0 = 1
    • 0 | 1 = 1
    • 0 | 0 = 0

举个例子,对二进制数 $01001010_{(2)}$$01011011_{(2)}$ 进行按位或运算,结果为 $01011011_{(2)}$,如图所示:

2.3 按位异或运算

按位异或运算(XOR):按位异或运算符为 ^。其功能是对两个二进制数的每一个二进位进行异或运算。

  • 按位异或运算规则:对应的两个二进位相异时,结果位为 $1$,二进位相同时则结果位为 $0$

  • 0 ^ 0 = 0

  • 1 ^ 0 = 1

  • 0 ^ 1 = 1

  • 1 ^ 1 = 0

举个例子,对二进制数 $01001010_{(2)}$$01000101_{(2)}$ 进行按位异或运算,结果为 $00001111_{(2)}$,如图所示:

2.4 取反运算

取反运算(NOT):取反运算符为 ~。其功能是对一个二进制数的每一个二进位进行取反运算。

  • 取反运算规则:使数字 $1$ 变为 $0$,$0$ 变为 $1$
    • ~0 = 1
    • ~1 = 0

举个例子,对二进制数 $01101010_{(2)}$ 进行取反运算,结果如图所示:

2.5 左移运算和右移运算

左移运算(SHL): 左移运算符为 <<。其功能是对一个二进制数的各个二进位全部左移若干位(高位丢弃,低位补 $0$)。

举个例子,对二进制数 $01101010_{(2)}$ 进行左移 $1$ 位运算,结果为 $11010100_{(2)}$,如图所示:

右移运算(SHR): 右移运算符为 >>。其功能是对一个二进制数的各个二进位全部右移若干位(低位丢弃,高位补 $0$)。

举个例子,对二进制数 $01101010_{(2)}$ 进行右移 $1$ 位运算,结果为 $00110101_{(2)}$,如图所示:

3. 位运算的应用

3.1 位运算的常用操作

3.1.1 判断整数奇偶

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

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

3.1.2 二进制数选取指定位

如果我们想要从一个二进制数 $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$ 位)。

3.1.3 将指定位设置为 $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$,其余位置保留原值)。

3.1.4 反转指定位

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

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

3.1.5 交换两个数

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

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

3.1.6 将二进制最右侧为 $1$ 的二进位改为 $0$

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

比如 $X = 01101100_{(2)}$,$X - 1 = 01101011_{(2)}$,则 X & (X - 1) == 01101100 & 01101011 == 01101000,结果为 $01101000_{(2)}$(即将 $X$ 最右侧为 $1$ 的二进制为改为 $0$)。

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

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

具体代码如下:

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

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

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

这是因为:

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

接下来我们使用 X & (X - 1) 操作,将原数对应二进制数最右侧为 $1$ 的二进位改为 $0$ 之后,得到新值:

  1. 如果原数是 $2$ 的幂次方,则通过 X & (X - 1) 操作之后,新值所有位都为 $0$,值为 $0$
  2. 如果该数不是 $2$ 的幂次方,则通过 X & (X - 1) 操作之后,新值仍存在不为 $0$ 的位,值肯定不为 $0$

所以我们可以通过是否为 $0$ 即可判断该数是否为 $2$ 的幂次方。

3.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

3.3 二进制枚举子集

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

3.3.1 二进制枚举子集简介

先来介绍一下「子集」的概念。

  • 子集:如果集合 $A$ 的任意一个元素都是集合 $S$ 的元素,则称集合 $A$ 是集合 $S$ 的子集。可以记为 $A \in S$

有时候我们会遇到这样的问题:给定一个集合 $S$,枚举其所有可能的子集。

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

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

那么我们就可以用一个长度为 $n$ 的二进制数来表示集合 $S$ 或者表示 $S$ 的子集。其中二进制的每一个二进位都对应了集合中某一个元素的选取状态。对于集合中第 $i$ 个元素来说,二进制对应位置上的 $1$ 代表该元素被选取,$0$ 代表该元素未被选取。

举个例子,比如长度为 $5$ 的集合 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$,我们可以用一个长度为 $5$ 的二进制数来表示该集合。

比如二进制数 $11111_{(2)}$ 就表示选取集合的第 $1$ 位、第 $2$ 位、第 $3$ 位、第 $4$ 位、第 $5$ 位元素,也就是集合 $\lbrace 5, 4, 3, 2, 1 \rbrace$,即集合 $S$ 本身。如下表所示:

集合 S 中元素位置 5 4 3 2 1
二进位对应值 1 1 1 1 1
对应选取状态 选取 选取 选取 选取 选取

再比如二进制数 $10101_{(2)}$ 就表示选取集合的第 $1$ 位、第 $3$ 位、第 $5$ 位元素,也就是集合 $\lbrace 5, 3, 1 \rbrace$。如下表所示:

集合 S 中元素位置 5 4 3 2 1
二进位对应值 1 0 1 0 1
对应选取状态 选取 未选取 选取 未选取 选取

再比如二进制数 $01001_{(2)}$ 就表示选取集合的第 $1$ 位、第 $4$ 位元素,也就是集合 $\lbrace 4, 1 \rbrace$。如下标所示:

集合 S 中元素位置 5 4 3 2 1
二进位对应值 0 1 0 0 1
对应选取状态 未选取 选取 未选取 未选取 选取

通过上面的例子我们可以得到启发:对于长度为 $5$ 的集合 $S$ 来说,我们只需要从 $00000 \sim 11111$ 枚举一次(对应十进制为 $0 \sim 2^5 - 1$)即可得到长度为 $5$ 的集合 $S$ 的所有子集。

我们将上面的例子拓展到长度为 $n$ 的集合 $S$。可以总结为:

  • 对于长度为 $n$ 的集合 $S$ 来说,只需要枚举 $0 \sim 2^n - 1$(共 $2^n$ 种情况),即可得到集合 $S$ 的所有子集。

3.3.2 二进制枚举子集代码

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 - 1
            sub_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                     # 返回所有子集

参考资料