位运算
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据,位运算是相当快的。
基本的位运算共
为了方便叙述,下文中省略“按位”。
与、或、异或¶
这三者都是两数间的运算,因此在这里一起讲解。
它们都是将两个整数作为二进制数,对二进制表示中的每一位逐一运算。
运算 | 运算符 | 数学符号表示 | 解释 |
---|---|---|---|
与 | & | 只有两个对应位都为 | |
或 | | | 只要两个对应位中有一个 | |
异或 | ^ | 只有两个对应位不同时才为 |
注意区分逻辑与(对应的数学符号为
异或运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即
举例:
取反¶
取反是对一个数
取反暂无默认的数学符号表示,其对应的运算符为 ~
。它的作用是把 ~
运算中同样会取反。
补码:在二进制表示下,正数和
举例(有符号整数):
左移和右移¶
num << i
表示将
num >> i
表示将
举例:
移位运算中如果出现如下情况,则其行为未定义:
- 右操作数(即移位数)为负值;
- 右操作数大于等于左操作数的位数;
例如,对于 int
类型的变量 a
, a<<-1
和 a<<32
都是未定义的。
对于左移操作,需要确保移位后的结果能被原数的类型容纳,否则行为也是未定义的。1对一个负数执行左移操作也未定义。2
对于右移操作,右侧多余的位将会被舍弃,而左侧较为复杂:对于无符号数,会在左侧补
复合赋值位运算符¶
和 +=
, -=
等运算符类似,位运算也有复合赋值运算符: &=
, |=
, ^=
, <<=
, >>=
。(取反是单目运算,所以没有。)
关于优先级¶
位运算的优先级低于算术运算符(除了取反),而按位与、按位或及异或低于比较运算符(详见 运算页面 ),所以使用时需多加注意,在必要时添加括号。
位运算的应用¶
位运算一般有三种作用:
-
高效地进行某些运算,代替其它低效的方式。
-
表示集合。(常用于 状压 DP 。)
-
题目本来就要求进行位运算。
需要注意的是,用位运算代替其它运算方式(即第一种应用)在很多时候并不能带来太大的优化,反而会使代码变得复杂,使用时需要斟酌。(但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算,因为此时使用位运算可以优化复杂度。)
有关 2 的幂的应用¶
由于位运算针对的是变量的二进制位,因此可以推广出许多与 2 的整数次幂有关的应用。
将一个数乘(除) 2 的非负整数次幂:
1 2 3 4 5 6 7 |
|
1 2 3 4 5 |
|
Warning
我们平常写的除法是向 -1 / 2
的值为 -1 >> 1
的值为
判断一个数是不是
1 2 |
|
1 2 3 |
|
对
1 2 |
|
1 2 3 |
|
取绝对值¶
在某些机器上,效率比 n > 0 ? n : -n
高。
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
取两个数的最大/最小值¶
在某些机器上,效率比 a > b ? a : b
高。
1 2 3 4 |
|
1 2 3 4 5 6 |
|
判断两非零数符号是否相同¶
1 2 3 4 |
|
1 2 3 4 |
|
交换两个数¶
该方法具有局限性
这种方式只能用来交换两个整数,使用范围有限。
对于一般情况下的交换操作,推荐直接调用 algorithm
库中的 std::swap
函数。
1 |
|
操作一个数的二进制位¶
获取一个数二进制的某一位:
1 2 3 |
|
1 2 3 4 |
|
将一个数二进制的某一位设置为
1 2 3 |
|
1 2 3 4 |
|
将一个数二进制的某一位设置为
1 2 3 |
|
1 2 3 4 |
|
将一个数二进制的某一位取反:
1 2 3 |
|
1 2 3 4 |
|
这些操作相当于将一个
模拟集合操作¶
一个数的二进制表示可以看作是一个集合(
操作 | 集合表示 | 位运算语句 |
---|---|---|
交集 | a & b | |
并集 | a|b | |
补集 | ~a (全集为二进制都是 1) | |
差集 | a & (~b) | |
对称差 | a ^ b |
子集遍历:
1 2 3 4 |
|
用这种方法可以在
汉明权重¶
汉明权重是一串符号中不同于(定义在其所使用的字符集上的)零符号(zero-symbol)的个数。对于一个二进制数,它的汉明权重就等于它 popcount
)。
求一个数的汉明权重可以循环求解:我们不断地去掉这个数在二进制下的最后一位(即右移
代码如下:
1 2 3 4 5 6 7 8 9 |
|
求一个数的汉明权重还可以使用 lowbit
操作:我们将这个数不断地减去它的 lowbit
4,直到这个数变为
代码如下:
1 2 3 4 5 6 7 8 9 |
|
构造汉明权重递增的排列¶
在 状压 DP 中,按照 popcount 递增的顺序枚举有时可以避免重复枚举状态。这是构造汉明权重递增的排列的一大作用。
下面我们来具体探究如何在
我们知道,一个汉明权重为
而找出一个数
-
把
(10110)_2 1 1 (11010)_2 -
把得到的
(11010)_2 1 1 1 010 001 (11001)_2
这个过程可以用位运算优化:
1 2 |
|
- 第一个步骤中,我们把数
x lowbit
,在二进制表示下,就相当于把x 1 1 (10110)_2 lowbit
后是(11000)_2 - 我们接下来要把答案后面的
1 t lowbit
是x 1 1 x lowbit
则是x 1 (10110)_2 t = (11000)_2 \operatorname{lowbit}(t) = (01000)_2 \operatorname{lowbit}(x)=(00010)_2 - 接下来的除法操作是这种位运算中最难理解的部分,但也是最关键的部分。我们设原数最右边连续一段
1 1 r 0 1 l t lowbit
等于1 << (r+1)
,x lowbit
等于1 << l
,(((t&-t)/(x&-x))>>1)
得到的,就是(1<<(r+1))/(1<<l)/2 = (1<<r)/(1<<l) = 1<<(r-l)
,在二进制表示下就是1 r-l 1 1 \frac{\operatorname{lowbit(t)\div 2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2 1
所以枚举
1 2 3 4 5 |
|
其中要注意
内建函数¶
GCC 中还有一些用于位运算的内建函数:
-
int __builtin_ffs(int x)
:返回x 1 1 1 x 0 0 -
int __builtin_clz(unsigned int x)
:返回x 0 x 0 -
int __builtin_ctz(unsigned int x)
:返回x 0 x 0 -
int __builtin_clrsb(int x)
:当x 0 x 0 x 1 -
int __builtin_popcount(unsigned int x)
:返回x 1 -
int __builtin_parity(unsigned int x)
:判断x 1
这些函数都可以在函数名末尾添加 l
或 ll
(如 __builtin_popcountll
)来使参数类型变为 ( unsigned
) long
或 ( unsigned
) long long
(返回值仍然是 int
类型)。 例如,我们有时候希望求出一个数以二为底的对数,如果不考虑 0
的特殊情况,就相当于这个数二进制的位数 -1
,而一个数 n
的二进制表示的位数可以使用 32-__builtin_clz(n)
表示,因此 31-__builtin_clz(n)
就可以求出 n
以二为底的对数。
由于这些函数是内建函数,经过了编译器的高度优化,运行速度十分快(有些甚至只需要一条指令)。
更多位数¶
如果需要操作的集合非常大,可以使用 bitset 。
题目推荐¶
参考资料与注释¶
- 位运算技巧: https://graphics.stanford.edu/~seander/bithacks.html
- Other Builtins of GCC: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
-
适用于 C++14 以前的标准。在 C++14 和 C++17 标准中,若原值为带符号类型,且移位后的结果能被原类型的无符号版本容纳,则将该结果 转换 为相应的带符号值,否则行为未定义。在 C++20 标准中,规定了无论是带符号数还是无符号数,左移均直接舍弃移出结果类型的位。 ↩
-
适用于 C++20 以前的标准。 ↩
-
这种右移方式称为算术右移。在 C++20 以前的标准中,并没有规定带符号数右移运算的实现方式,大多数平台均采用算术右移。在 C++20 标准中,规定了带符号数右移运算是算术右移。 ↩
-
一个数二进制表示从低往高的第一个
1 (1010)_2 lowbit
是(0010)_2
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用