← 返回题目列表

AtCoder · APG4b_ac

AC. 3.05.位运算

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_ac 任务ID:3775

上一页 | 下一页

要点

  • 可以表达两种状态的数据单元:“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.递归函数”中也讨论过,但也可以使用全位搜索来解决。

上一页 | 下一页