01. 位运算知识
01. 位运算知识
1. 位运算简介
1.1 位运算与二进制简介
位运算(Bit Operation):在计算机内部,数是以「二进制(Binary)」的形式来进行存储。位运算就是直接对数的二进制进行计算操作,在程序中使用位运算进行操作,会大大提高程序的性能。
在学习二进制数的位运算之前,我们先来了解一下什么叫做「二进制数」。
二进制数(Binary):由
和 两个数码来表示的数。二进制数中每一个 或每一个 都称为一个「位(Bit)」。
我们通常使用的十进制数有
: 加上 等于 。 : 加上 之后个位大于等于 ,符合「满十进一」,结果等于 。
而在二进制数中,我们只有
: 加上 等于 。 : 加上 ,大于等于 ,符合「逢二进一」,结果等于 。 。
1.2 二进制数的转换
1.2.1 二进制转十进制数
在十进制数中,数字
同理,在二进制数中,
我们可以通过这样的方式,将一个二进制数转为十进制数。
1.2.2 十进制转二进制数
十进制数转二进制数的方法是:除二取余,逆序排列法。
我们以十进制数中的
我们反向遍历每次计算的余数,依次是
2. 位运算基础操作
在二进制的基础上,我们可以对二进制数进行相应的位运算。基本的位运算共有
这里的「按位与运算」、「按位或运算」、「按位异或运算」、「左移运算」、「右移运算」是双目运算。
- 「按位与运算」、「按位或运算」、「按位异或运算」是将两个整数作为二进制数,对二进制数表示中的每一位(即二进位)逐一进行相应运算,即双目运算。
- 「左移运算」、「右移运算」是将左侧整数作为二进制数,将右侧整数作为移动位数,然后对左侧二进制数的全部位进行移位运算,每次移动一位,总共移动右侧整数次位,也是双目运算。
而「取反运算」是单目运算,是对一个整数的二进制数进行的位运算。
我们先来看下这
运算符 | 描述 | 规则 |
---|---|---|
| | 按位或运算符 | 只要对应的两个二进位有一个为 |
& | 按位与运算符 | 只有对应的两个二进位都为 |
<< | 左移运算符 | 将二进制数的各个二进位全部左移若干位。<< 右侧数字指定了移动位数,高位丢弃,低位补 |
>> | 右移运算符 | 对二进制数的各个二进位全部右移若干位。>> 右侧数字指定了移动位数,低位丢弃,高位补 |
^ | 按位异或运算符 | 对应的两个二进位相异时,结果位为 |
~ | 取反运算符 | 对二进制数的每个二进位取反,使数字 |
2.1 按位与运算
按位与运算(AND):按位与运算符为
&
。其功能是对两个二进制数的每一个二进位进行与运算。
按位与运算规则:只有对应的两个二进位都为
时,结果位才为 。1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
举个例子,对二进制数
2.2 按位或运算
按位或运算(OR):按位或运算符为
|
。其功能对两个二进制数的每一个二进位进行或运算。
- 按位或运算规则:只要对应的两个二进位有一个为
时,结果位就为 。1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
举个例子,对二进制数
2.3 按位异或运算
按位异或运算(XOR):按位异或运算符为
^
。其功能是对两个二进制数的每一个二进位进行异或运算。
按位异或运算规则:对应的两个二进位相异时,结果位为
,二进位相同时则结果位为 。0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0
举个例子,对二进制数
2.4 取反运算
取反运算(NOT):取反运算符为
~
。其功能是对一个二进制数的每一个二进位进行取反运算。
- 取反运算规则:使数字
变为 , 变为 。~0 = 1
~1 = 0
举个例子,对二进制数
2.5 左移运算和右移运算
左移运算(SHL): 左移运算符为
<<
。其功能是对一个二进制数的各个二进位全部左移若干位(高位丢弃,低位补)。
举个例子,对二进制数
右移运算(SHR): 右移运算符为
>>
。其功能是对一个二进制数的各个二进位全部右移若干位(低位丢弃,高位补)。
举个例子,对二进制数
3. 位运算的应用
3.1 位运算的常用操作
3.1.1 判断整数奇偶
一个整数,只要是偶数,其对应二进制数的末尾一定为
(x & 1) == 0
为偶数。(x & 1) == 1
为奇数。
3.1.2 二进制数选取指定位
如果我们想要从一个二进制数 X & Y
),即可得到想要的数。
举个例子,比如我们要取二进制数 01101010 & 00001111 == 00001010
。其结果
3.1.3 将指定位设置为
如果我们想要把一个二进制数 X | Y
),即可得到想要的数。
举个例子,比如我们想要将二进制数 01101010 | 00001111 = 01101111
。其结果
3.1.4 反转指定位
如果我们想要把一个二进制数 X ^ Y
),即可得到想要的数。
举个例子,比如想要将二进制数 01101010 ^ 00001111 = 01100101
。其结果
3.1.5 交换两个数
通过按位异或运算可以实现交换两个数的目的(只能用于交换两个整数)。
a, b = 10, 20
a ^= b
b ^= a
a ^= b
print(a, b)
3.1.6 将二进制最右侧为 的二进位改为
如果我们想要将一个二进制数 X & (X - 1)
的操作即可完成。
比如 X & (X - 1) == 01101100 & 01101011 == 01101000
,结果为
3.1.7 计算二进制中二进位为 的个数
从 3.1.6 中得知,通过 X & (X - 1)
我们可以将二进制 X & (X - 1)
操作,最终将二进制
具体代码如下:
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
n = n & (n - 1)
cnt += 1
return cnt
3.1.8 判断某数是否为 的幂次方
通过判断 X & (X - 1) == 0
是否成立,即可判断
这是因为:
- 凡是
的幂次方,其二进制数的某一高位为 ,并且仅此高位为 ,其余位都为 。比如: 、 。 - 不是
的幂次方,其二进制数存在多个值为 的位。比如: 、 。
接下来我们使用 X & (X - 1)
操作,将原数对应二进制数最右侧为
- 如果原数是
的幂次方,则通过X & (X - 1)
操作之后,新值所有位都为 ,值为 。 - 如果该数不是
的幂次方,则通过X & (X - 1)
操作之后,新值仍存在不为 的位,值肯定不为 。
所以我们可以通过是否为
3.2 位运算的常用操作总结
功 能 | 位运算 | 示例 |
---|---|---|
从右边开始,把最后一个 | x & (x - 1) | 100101000 -> 100100000 |
去掉右边起第一个 | x & (x ^ (x - 1)) 或 x & (-x) | 100101000 -> 1000 |
去掉最后一位 | x >> 1 | 101101 -> 10110 |
取右数第 | x >> (k - 1) & 1 | 1101101 -> 1, k = 4 |
取末尾 | x & 7 | 1101101 -> 101 |
取末尾 | x & 15 | 1101101 -> 1101, k = 4 |
只保留右边连续的 | (x ^ (x + 1)) >> 1 | 100101111 -> 1111 |
右数第 | x ^ (1 << (k - 1)) | 101001 -> 101101, k = 3 |
在最后加一个 | x << 1 | 101101 -> 1011010 |
在最后加一个 | (x << 1) + 1 | 101101 -> 1011011 |
把右数第 | x & ~(1 << (k - 1)) | 101101 -> 101001, k = 3 |
把右数第 | x | (1 << (k - 1)) | 101001 -> 101101, k = 3 |
把右边起第一个 | x | (x + 1) | 100101111 -> 100111111 |
把右边连续的 | x | (x - 1) | 11011000 -> 11011111 |
把右边连续的 | x & (x + 1) | 100101111 -> 100100000 |
把最后一位变成 | x | 1 - 1 | 101101 -> 101100 |
把最后一位变成 | x | 1 | 101100 -> 101101 |
把末尾 | x | (1 << k - 1) | 101001 -> 101111, k = 4 |
最后一位取反 | x ^ 1 | 101101 -> 101100 |
末尾 | x ^ (1 << k - 1) | 101001 -> 100110, k = 4 |
3.3 二进制枚举子集
除了上面的这些常见操作,我们经常常使用二进制数第
3.3.1 二进制枚举子集简介
先来介绍一下「子集」的概念。
- 子集:如果集合
的任意一个元素都是集合 的元素,则称集合 是集合 的子集。可以记为 。
有时候我们会遇到这样的问题:给定一个集合
枚举子集的方法有很多,这里介绍一种简单有效的枚举方法:「二进制枚举子集算法」。
对于一个元素个数为
那么我们就可以用一个长度为
举个例子,比如长度为
比如二进制数
集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|
二进位对应值 | 1 | 1 | 1 | 1 | 1 |
对应选取状态 | 选取 | 选取 | 选取 | 选取 | 选取 |
再比如二进制数
集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|
二进位对应值 | 1 | 0 | 1 | 0 | 1 |
对应选取状态 | 选取 | 未选取 | 选取 | 未选取 | 选取 |
再比如二进制数
集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|
二进位对应值 | 0 | 1 | 0 | 0 | 1 |
对应选取状态 | 未选取 | 选取 | 未选取 | 未选取 | 选取 |
通过上面的例子我们可以得到启发:对于长度为
我们将上面的例子拓展到长度为
- 对于长度为
的集合 来说,只需要枚举 (共 种情况),即可得到集合 的所有子集。
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 # 返回所有子集
参考资料
- 【博文】Python 中的按位运算符 |【生长吧!Python!】- 云社区 - 华为云
- 【博文】一文读懂位运算的使用 - 小黑说 Java - 掘金
- 【博文】枚举排列和枚举子集 - CUC ACM-Wiki
- 【博文】Swift 运算符 | 菜鸟教程
来源:https://github.com/itcharge/LeetCode-Py