要点
- 可以表达两种状态的数据单元:“0”或“1”。位是排列成一行的一串位。位串这就是所谓的
- 对位串执行操作,如下表所示。位运算这就是所谓的
| 位运算 | 演算子 | 意味 |
|---|---|---|
| 按位与运算 | & |
对每一位应用“如果两个位都为 1,则为 1”运算。 |
| 按位或运算 | | |
对每一位应用“如果至少一位为 1,则为 1”运算。 |
| 按位异或运算 | ^ |
对每一位应用“如果只有一个为 1,则为 1”运算。 |
| 按位非运算 | ~ |
对每一位应用“反转位”操作。 |
| 左移操作 | << |
将位串向左移动指定的位数。超出范围的位将被截断,缺失的位将用 0 填充。 |
| 右移操作 | >> |
将位串右移指定的位数。超出范围的位将被截断,缺失的位将用 0 填充。 |
- 位运算有时可用于方便地处理集合。
- 在 C++ 中处理位串时
使用
bitset使用
bitset<ビット数> 変数名; // すべてのビットが0の状態で初期化される
bitset<ビット数> 変数名("ビット列(長さはビット数に合わせる)"); // 指定したビット列で初期化される
変数.set(位置, 値); // ビットの値を変更
変数.test(位置); // ビットの値を調べる
- 通过使用 C++ 整数类型,您(通常)可以处理最多 64 位的位字符串。
- 位运算符很容易被误解,所以明确
()让它出来
位运算
首先我们解释一下按位运算的概念,然后介绍如何在C++中进行按位运算。 它被称为
位
可以表达两种状态的数据单元:“0”或“1”。位。
位序列 它被称为位串。 例如,“0011”是4位的位串,“10101010”是8位的位串。
位运算
位串操作位运算。
我们将介绍以下六位操作。
- 与运算
- 或运算
- 异或运算
- 不操作
- 左移操作
- 右移操作
与运算
下表中定义的操作是与运算(或論理積)。 将这种 AND 运算应用于每位的运算称为按位 AND 运算。
| x | y | x 和 y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
在 AND 运算中,只有当 x 和 y 位都为 1 时,结果才为 1。
具体例
0111 AND 0100 = 0100
垂直排列时,它看起来像这样:
0111 AND 0100 -------- = 0100
或运算
下表中定义的操作是或运算(或論理和)。 对每一位进行 OR 运算的运算称为按位 OR 运算。
| x | y | x 或 y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
在 OR 运算中,如果 x 和 y 位至少有一位为 1,则结果为 1。 反之,只有两者都为 0 时,结果才为 0。
具体例
0111 OR 0100 = 0111
垂直排列时,它看起来像这样:
0111 OR 0100 -------- = 0111
异或运算
下表中定义的操作是异或运算(或排他的論理和)。 对每一位应用 XOR 运算的运算称为按位 XOR 运算。
| x | y | x 异或 y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
在异或运算中,仅当 x 或 y 的任意一位为 1 时,结果才为 1。 如果x和y的位相等,也可以看作0。 它被称为
具体例
0111 XOR 0100 = 0011
垂直排列时,它看起来像这样:
0111 XOR 0100 -------- = 0011
不操作
下表中定义的操作是不操作。 对每一位进行 NOT 运算的运算称为按位 NOT 运算。
| x | 不是 x |
|---|---|
| 0 | 1 |
| 1 | 0 |
NOT 运算只是反转位; 0 位变为 1,1 位变为 0。
具体例
NOT 0111 = 1000
垂直排列时,它看起来像这样:
NOT 0111 -------- = 1000
左移操作
位串左移操作逻辑左移运算或简单地左移。
经过逻辑左移操作后,溢出的位被丢弃,缺失的位用0填充。
具体例
0111 を2ビット左シフトすると 1100
垂直排列时,它看起来像这样:
2ビット左シフト
|0111|
01|11 |
----------
= |1100|
突出的“01”部分被截断,最右边的2位用0填充。
右移操作
执行将位串右移的操作。逻辑右移操作或简单地右移。
与逻辑左移操作类似,超出移位范围的位将被丢弃,缺失的位将用 0 填充。
具体例
0111 を2ビット右シフトすると 0001
垂直排列时,它看起来像这样:
2ビット右シフト
|0111|
| 01|11
----------
= |0001|
突出的“11”部分被截去,最左边的2位用0填充。
如何使用位运算
位运算用于执行设置运算或需要高速运算时。
设置操作
位串可用于表示事物的集合(以下简称集合)。 可以通过如果包含某个元素则将相应位设置为1,如果不包含某个元素则将相应位设置为0来表示。 当你有一些写有数字
具体例
例如,1〜10的牌作为一手牌时,这手牌可以使用10位的位串来表示。 在这里,我们将使用“将与卡片上写入的数字对应的位置中的位设置为 1”的规则将手与位串关联起来。 例如,手{2,3,7}对应于位串“0110001000”。 包含写有 2 的卡片,因此第二位(左起)为 1。 写有 5 的卡片不包括在内,因此第 5 位为 0。
如果将其表示为这样的位串, 例如,当你想查找两个人手中共同包含的牌时, 通过对两个人手上的比特串进行按位与运算, 您可以一次性获取“两个人手中共同包含的一组牌”对应的比特串。
设置运算与位运算对应关系示例
| 操作 | 对应按位运算 |
|---|---|
| 提取两个集合共有的元素 | 按位与运算 |
| 提取至少存在于两个集合之一中的元素 | 按位或运算 |
| 提取不包含在某个集合中的元素 | 按位非运算 |
当然,您可以使用数组执行类似的集合操作。 但是,对于简单的集合运算(例如上表中列出的操作), 使用按位运算的优点是使程序更简单、更快。
从两个集合中提取共同元素的示例 两个集合
A = {1, 2, 3, 5, 7}和B = {1, 3, 5, 7, 9}的共同元素是{1, 3, 5, 7}。 A对应的位串为“1110101000”,B对应的位串是“1010101010”。 对这些结果应用按位 AND 运算得到“1010101000”,这是一个集合{1, 3, 5, 7}表示可以提取共同元素。
高速化
按位运算允许您一次对多个位执行计算。 通过利用这个特性,您也许能够加快您的程序。
STL 位集
如何在 C++ 中处理位串
使用bitset。
声明/初始化
bitset<ビット数> 変数名; // すべてのビットが0の状態で初期化される
bitset<ビット数> 変数名("ビット列(長さはビット数に合わせる)"); // 指定したビット列で初期化される
注意,“位数”部分必须是常量,不能是变量。
例
bitset<4> b("1010");
位运算
bitset上的按位运算定义为 C++ 运算符。
对应关系如下表所示。
| 位运算 | bitset运算符 |
如何使用 |
|---|---|---|
| 按位与运算 | & |
変数1 & 変数2 |
| 按位或运算 | | |
変数1 | 変数2 |
| 按位异或运算 | ^ |
変数1 ^ 変数2 |
| 按位非运算 | ~ |
~変数 |
| 逻辑左移运算 | << |
変数 << シフトするビット数 |
| 逻辑右移操作 | >> |
変数 >> シフトするビット数 |
在这些位操作结束时
通过添加=,它可以用作复合赋值运算符。
示例程序
#include <bits/stdc++.h>
using namespace std;
int main() {
bitset<8> a("00011011");
bitset<8> b("00110101");
auto c = a & b;
cout << "1: " << c << endl; // 1: 00010001
cout << "2: " << (c << 1) << endl; // 2: 00100010
cout << "3: " << (c << 2) << endl; // 3: 01000100
cout << "4: " << (c << 3) << endl; // 4: 10001000
cout << "5: " << (c << 4) << endl; // 5: 00010000
c <<= 4;
c ^= bitset<8>("11010000"); // XOR演算の複合代入演算子
cout << "6: " << c << endl; // 6: 11000000
}
実行結果
1: 00010001 2: 00100010 3: 01000100 4: 10001000 5: 00010000 6: 11000000
位集操作
bitset在处理位字符串时提供有用的函数。
主要的如下所示。
| 操作 | 怎么写 | 備考 |
|---|---|---|
| 更改特定位的值 | 変数.set(位置, 値); |
使用从 0 开始的索引指定要更改的位的位置。将值指定为 0 或 1。 |
| 检查特定位是否为 1 | 変数.test(調べる位置); |
使用基于 0 的索引指定要检查的位的位置。如果该位为1true,如果该位为 0
返回false。 |
关于指定位置,位串从右到左对应0, 1, 2, .... 请注意,这与指定数组位置相反。
示例程序
#include <bits/stdc++.h>
using namespace std;
int main() {
bitset<4> S;
S.set(0, 1); // 0番目のビットを1にする
cout << S << endl;
if (S.test(3)) {
cout << "4th bit is 1" << endl;
} else {
cout << "4th bit is 0" << endl;
}
}
実行結果
0001 4th bit is 0
其他功能将在“详情”部分介绍。
整数和位串的对应关系
其实到目前为止我已经处理过了。int呀
诸如int64_t之类的整数类型是
在计算机内部,它被表示为一个位串。
此外,普通计算机可以处理的所有内容都是位串。
计算机通过将数字分配给位串中的 01 模式来处理数字。 例如,“00000111”对应7,“00100100”对应36。
这样的位串和数值之间的对应关系是 它基于规则二進法。
为了简单起见,下面我们将解释如何表示无符号整数。
许多计算机接受负数作为二进制补码表示格式表示。 我不会介绍这个,因为它与位运算的主题有点偏离,但如果您有兴趣,请研究一下。
二進法
二进制将整数表示为“1,2,4,8,16,32,64,...(2的幂)”之和,0和1对应是否相加。
此外,它可以用二进制表示法表示。 它被称为二進数表記。 另一方面,我们通常使用的数字0到9的系统称为十进制数。
例如,十进制数“7”为7 = 4 + 2 + 1,因此二进制表示为“111”。前导 0 通常被省略。
以下是一些示例。请注意,该位串从右端开始对应于 1、2、4、8、...。
| 十進数 | 二進数 | |
|---|---|---|
| 4 | 100 | 4 = 2^2 |
| 5 | 101 | 5 = 4 + 1 = 2^2 + 2^0 |
| 36 | 100100 | 36 = 32 + 4 = 2^5 + 2^2 |
| 100 | 1100100 | 100 = 64 + 32 + 4 = 2^6 + 2^5 + 2^2 |
0到15的二进制表示如下。如果您对二进制数不熟悉,请查看一下。
| 十進数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 二進数 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
整数的按位运算
C++ 提供了将整数视为位字符串的运算符。
整数按位运算的运算符是
与bitset相同。
但是,由于位串的长度根据整数类型是固定的,
它不像bitset那么灵活。
例如,uint32_t可以被视为32位的位串,uint8_t可以被视为 8 位的位串。
此外,C++标准可以处理的最大整数类型是uint64_t,这是一个64位的位串,所以
只有 64 位或更少的整数才能被视为位字符串。
另外,
如果尝试用cout输出,则会以十进制整数的形式输出,难以理解。
基本上
使用bitset很方便,但是
当执行诸如“枚举所有可能的集合”之类的处理时,将整数视为位串可能更简洁。
更多详细信息,请参阅“详细信息”中的“全位搜索”。
注意点
运算符优先级
许多用于位运算的运算符的优先级较低,因此明确
您可能需要将其包装在()中。
示例程序
#include <bits/stdc++.h>
using namespace std;
int main() {
int x = 5; // 0101
int y = 10; // 1010
// if (x & y > 0) { // &演算子よりも>演算子の優先度の方が高いので x & (y > 0) と解釈される
if ((x & y) > 0) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
実行結果
no
主要运算符的优先级如下所示。优先级越高,优先级越高。
记住所有的优先级是很困难的,所以为了防止错误,总是
确保将其包裹在()中。
| 演算子 | 説明 |
|---|---|
a++, a--, . |
递增、递减、成员访问 |
!, ~ |
逻辑非,按位 NOT 运算 |
a*b, a/b, a%b |
乗算、除算、剰余 |
a+b, a-b |
加算、減算 |
<<, >> |
左移操作、右移操作 |
<, <=, >, >= |
比較演算 |
==, != |
関係演算子 |
& |
按位与运算 |
^ |
按位异或运算 |
| |
按位或运算 |
&& |
逻辑运算(与) |
|| |
逻辑运算(或) |
=, ◯= |
代入演算、複合代入演算 |
详细信息
位集函数
在下表中
我们总结一下对bitset位串的操作。
| 操作 | 怎么写 | 備考 |
|---|---|---|
| 将所有位设置为 1 | 変数.set(); |
|
| 将特定位设置为 1 | 変数.set(1にする位置); |
使用从 0 开始的索引指定要设置为 1 的位的位置。 |
| 更改特定位的值 | 変数.set(位置, 値); |
使用从 0 开始的索引指定要更改的位的位置。将值指定为 0 或 1。 |
| 将所有位设置为 0 | 変数.reset(); |
|
| 将特定位设置为 0 | 変数.reset(0にする位置); |
使用基于 0 的索引指定要设置为 0 的位的位置。 |
| 反转所有位 | 変数.flip(); |
|
| 反转特定位 | 変数.flip(反転する位置); |
使用从 0 开始的索引指定要反转的位的位置。 |
| 检查特定位是否为 1 | 変数.test(調べる位置); |
使用基于 0 的索引指定要检查的位的位置。如果该位为1true,如果该位为 0
返回false。 |
| 判断所有位是否都为1 | 変数.all() |
如果所有位均为 1true,否则false。 |
| 判断是否有任意位为1 | 変数.any() |
如果存在一位 1true,否则false。 |
| 统计1位的个数 | 変数.count() |
|
| 输出位串 | cout << 変数; |
|
| 将位串转换为字符串 | 変数.to_string() |
|
| 访问位 相当于 | 変数[位置] |
基本上
使用test、set/reset,但请注意,指定范围之外的位置不会导致错误。 |
全位搜索
我们将介绍一种称为“位穷举搜索”的技术。
组合的完整枚举可以简单地通过按位遍历来实现。
全位搜索是指对“位串的所有组合”执行某种处理。
例如,对于长度为2的位串,所有位串有四种组合:“00”、“01”、“10”和“11”。
每个位有两种可能:0或1,所以长度N的位串是2^N存在。
以下示例程序枚举了所有“长度为 3 的位串”。
示例程序
#include <bits/stdc++.h>
using namespace std;
int main() {
// 3ビットのビット列をすべて列挙する
for (int tmp = 0; tmp < (1 << 3); tmp++) {
bitset<3> s(tmp);
// ビット列を出力
cout << s << endl;
}
}
実行結果
000 001 010 011 100 101 110 111
第6行是
这是一个 for 语句,将变量tmp从 0 开始到 8。
1 << 3是求2的立方的公式。
如果将
1向左移动 3 位,则该位串变为“1000”,它被解释为二进制数。2の3乗=8。
2k要获取功率值, 它通常写为
1 << k。这是一个简单的形状,所以请记住它。
第7行,
将tmp解释为位串bitset<3>类型
正在初始化s。
第 9 行
正在输出s的位串。
0到7的位串如下。
| 十進数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 二進数 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
你可以看到所有长度为3的位串都出现在这些中。
更一般地说, 通过循环0我决定将所有值添加到2^N-1范围, 长度 您可以枚举N中的所有位串。
位详尽搜索模板
您可以按以下形式执行全位搜索。 请注意,变量不能用于指定
for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
bitset<ビット数> s(tmp);
// (ビット列sに対する処理)
}
bitset的长度。
该算法还减少了位串的长度。N至少 请注意计算量,因为它会循环超过2^N次。 给出了
例題
A_1, A_2, \cdots A_N的N整数。 选择其中一些整数并找出它们的和是 查找是否存在满足K的选择方法。
制約
- 1 \leq N \leq 20
- 1 \leq K \leq 100
- 1 \leq A_i \leq 100 (1 \leq i \leq N)
入力
N K A_1 A_2 \ldots A_N
出力
总和是
如果存在K这样的整数组合,则写在一行中。
请输出YES,否则NO。
只需选择 2 和 9 即可
入力例1
5 11 2 8 4 2 9
出力例1
YES
2 + 9 = 11。
入力例2
5 3 2 8 4 2 9
出力例2
NO
入力例3
5 25 2 8 4 2 9
出力例3
YES
解答例
#include <bits/stdc++.h>
using namespace std;
int main () {
int N, K;
cin >> N >> K;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A.at(i);
}
bool ans = false;
// すべての選び方を試して、総和がKになるものがあるかを調べる
for (int tmp = 0; tmp < (1 << 20); tmp++) {
bitset<20> s(tmp); // 最大20個なので20ビットのビット列として扱う
// ビット列の1のビットに対応する整数を選んだとみなして総和を求める
int sum = 0;
for (int i = 0; i < N; i++) {
if (s.test(i)) {
sum += A.at(i);
}
}
if (sum == K) {
ans = true;
}
}
if (ans) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
位集和整数之间的相互转换
从整数到位集的转换 通过将整数传递给
bitset的构造函数,您可以将该整数视为位字符串。
它可以转换为bitset。
bitset<ビット数> 変数名(整数);
位集到整数的转换 当用作
map键或执行四次算术运算时,
您可能想要将bitset转换为整数。在这种情况下,
使用bitset的to_ullong函数。
如果
bitsetの変数.to_ullong()
bitset中的位数超过64位,则无法转换为整数,并且会出现运行时错误。
二进制文字 通过使用
二进制文字 通过使用,您可以用二进制表示法写入整数。
二进制文字是
就像0b0101呀
诸如0b11111111,
在0b后面写入01的位串。
#include <bits/stdc++.h>
using namespace std;
int main() {
uint32_t x = 0b100;
cout << x << endl; // 4
cout << (x | 0b010) << endl; // 計算結果は 0b110 = 6
}
実行結果
4 6
按位运算复杂度
使用整数作为位串时
全部O(1)。
使用位集时
基本上
使用bitset操作的计算复杂度为N作为O(N)。
然而,在内部,通常使用整数位运算来实现一次处理多个位。 基本上如果是64位以内的话O(1)。 即使超过64位,它的运行速度也往往比根据计算量估计的执行时间要快。
负整数右移
我们解释了在逻辑右移中,空位用 0 填充。 负数右移时,空位基本都补1。 此操作称为算术右移。
演習問題
请解决链接目的地的问题。
ABC/ARC问题
我们将介绍AtCoder初学者竞赛/AtCoder常规竞赛的过去问题,可以用到目前为止的知识解决。 如果您对练习题不满意,请尝试一下。
这个问题在“2.05.递归函数”中也讨论过,但也可以使用全位搜索来解决。