bitset

A bitset is an array whose each value is either 0 or 1. For example, the following code creates a bitset that contains 10 elements:

  1. bitset<10> s;
  2. s[1] = 1;
  3. s[3] = 1;
  4. s[4] = 1;
  5. s[7] = 1;
  6. cout << s[4] << "\n"; // 1
  7. cout << s[5] << "\n"; // 0

The benefit of using bitsets is that they require less memory than ordinary arrays, because each element in a bitset only uses one bit of memory. For example, if n bits are stored in an int array, 32n bits of memory will be used, but a corresponding bitset only requires n bits of memory. In addition, the values of a bitset can be efficiently manipulated using bit operators, which makes it possible to optimize algorithms using bit sets.（一个重要的优化工具）

  1. bitset<10> s(string("0010011010")); // from right to left
  2. cout << s[4] << "\n"; // 1
  3. cout << s[5] << "\n"; // 0
  5. bitset<10> s(string("0010011010"));
  6. cout << s.count() << "\n"; // 4
  8. bitset<10> a(string("0010110110"));
  9. bitset<10> b(string("1011011000"));
  10. cout << (a&b) << "\n"; // 0010010000
  11. cout << (a|b) << "\n"; // 1011111110
  12. cout << (a^b) << "\n"; // 1001101110
  1. foo.size() 返回大小（位数）
  2. foo.count() 返回1的个数
  3. foo.any() 返回是否有1
  4. foo.none() 返回是否没有1
  5. foo.set() 全都变成1
  6. foo.set(p) 将第p + 1位变成1
  7. foo.set(p, x) 将第p + 1位变成x
  8. foo.reset() 全都变成0
  9. foo.reset(p) 将第p + 1位变成0
  10. foo.flip() 全都取反
  11. foo.flip(p) 将第p + 1位取反
  12. foo.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
  13. foo.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
  14. foo.to_string() 返回它转换为string的结果
  16. foo.test(0) test函数用来查下标处的元素是０还是１

std::bitset

https://www.cplusplus.com/reference/bitset/bitset/?kw=bitset
image.png