编程C++

【STL】bitset，位操作与集合操作

字数统计: 1.7k字   |   阅读时长: 7分
, , , ,

摘要: 本文介绍在 C++ STL 中的 bitset

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

《C++标准库》 第2版，作者 Nicolai M. josuttis，侯捷 译 $12.5

std::bitset 入门

有时候我们经常用整数来表示集合，整数的对应的二进制位为 1 和 0 分别表示该元素是否在集合中。状态压缩DP 就是这种思路的应用。

在 C++ 中我们经常用 int 或者 long long 当做状态压缩的集合使用，配合 &, |, ^ 等操作符，实现集合的运算。

但有的时候集合中的元素很多，超过了 64 个，用 int 和 long long 就不好表示了。此时 std::bitset 就是一种解决方案，它的好处是可以容纳任意个数的元素。

参考以下代码，可容纳的元素个数由模板参数指定。

1
2
3
4
namespace std {
    template <size_t Bits>
    class bitset;
}

这里模板参数不是类型，而是一个无符号整数。如果模板实参不同，实例化所得模板类型就不同。

C++11 的重要新特性

在 c++11 中，bitset 的特性有一些更新：

  • bitset 可以被 string 字面值常量初始化
  • 增加 to_ullong()，实现与 unsigned long long 的转换
  • 增加 all() 检查是否所有 bit 均已置位
  • 为了能够用在 unordered 容器中，bitset 提供了一个默认的 hash 函数, Ref $7-9-2

std::bitset 的功能

C++标准库中的bitset是一个模板类，它提供了一种以紧凑形式操作固定长度位集合的方法。以下是C++ bitset中的一些主要方法：

构造函数

  • bitset<size>()：创建一个具有指定位数的bitset，所有位初始化为0。
  • bitset<size>(int val)：创建一个bitset，所有位初始化为特定的值。
  • bitset<size>(string val)：创建一个bitset，所有位初始化为特定的值。

转换为字符串

to_string：返回一个表示bitset当前状态的字符串。

位操作

置位 set

  • void set(size_t pos, bool value = true)：将指定位置的位设置为1（如果value为true）或0（如果value为false）。

复位 reset

void reset(size_t pos)：将指定位置的位设置为0。

翻转 flip

void flip(size_t pos)：将指定位置的位取反，即0变1，1变0。

对所有位操作

  • void set()：将所有位设置为1。
  • void reset()：将所有位设置为0。
  • void flip()：将所有位取反。

1 的个数

size_t count() const：返回bitset中设置为1的位数。

位的数量

size_t size() const：返回bitset的大小，即位的数量。

访问特定位的值

bool operator[](size_t pos) const：返回指定位置的位值。

补集

bitset<T> operator~() const：返回bitset的补集。

按位与、或、异或

operator&, |, ^：AND, OR, XOR

移位

operator<<, >>：将bitset左移或右移，默认补0。

两集合关系

  • 是否相等：operator==, !=。
  • a 是否是 b 的子集：a & b == a。
  • a 与 b 是否有交集：(a & b).any()。

有1、全0、全1

bool any() const：如果bitset中至少有一个位被设置为1，则返回true。
bool none() const：如果bitset中没有位被设置为1，则返回true。
bool all() const：如果bitset中的所有位都被设置为1，则返回true。

下面是一段实例程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <bitset>

using namespace std;

int main() {
    // 构造函数
    bitset<8> bs1(255); // 初始化一个8位的bitset，值为255 (二进制11111111)
    bitset<9> bs2(0x001110011);
    bitset<9> bs3("001111011");

    // 转换为字符串
    cout << "Initial bitset b1: " << bs1 << endl;
    cout << "Initial bitset b2: " << bs2.to_string() << endl;
    cout << "Initial bitset b2: " << bs3 << endl;

    // 位操作
    bs1.set(5); // 设置第5位为1
    bs1.reset(2); // 将第2位重置为0
    bs1.flip(3); // 将第3位取反
    cout << "位操作后的 b1: " << bs1 << endl; // 输出修改后的 bitset

    // 补集
    cout << "b1 的补集：" << ~bs1 << endl;

    // 访问特定位的值
    for(int i = 0; i < bs1.size(); ++i)
        cout << "bs1[" << i << "]: " << bs1[i] << endl;

    // 移位
    bs1 >>= 1;
    cout << "右移一位后的 bs1：" << bs1 << endl;
    bs1 <<= 2;
    cout << "左移两位后的 bs1：" << bs1 << endl;

    // 1 的个数
    cout << "1 的个数：" << bs1.count() << endl;


    // bs2 是 b3 的子集
    if((bs2 & bs3) == bs2)
        cout << "b2 是 bs3 的子集，bs2：" << bs2 << ", b3：" << bs3 << endl;

    bitset<8> bs4 = bs1.flip();
    // bs1 与 bs4 没有交集
    if(!(bs1 & bs4).any())
        cout << "bs1 与 bs4 没有交集，bs1：" << bs1 << ", bs4：" << bs4 << endl;

    bs4.reset();
    if(bs4.none())
        cout << "bs4 已经 reset：" << bs4 << endl;


    // 位操作
    bitset<9> bs5 = bs2 & bs3; // 位与操作
    bitset<9> bs6 = bs2 | bs3; // 位或操作
    bitset<9> bs7 = bs2 ^ bs3; // 位异或操作

    cout << "bs2 AND bs3: " << bs5 << endl;
    cout << "bs2 OR bs3: " << bs6 << endl;
    cout << "bs2 XOR bx3: " << bs7 << endl;

    return 0;
}

结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Initial bitset b1: 11111111
Initial bitset b2: 000010001
Initial bitset b2: 001111011
位操作后的 b1: 11110011
b1 的补集：00001100
bs1[0]: 1
bs1[1]: 1
bs1[2]: 0
bs1[3]: 0
bs1[4]: 1
bs1[5]: 1
bs1[6]: 1
bs1[7]: 1
右移一位后的 bs1：01111001
左移两位后的 bs1：11100100
1 的个数：4
b2 是 bs3 的子集，bs2：000010001, b3：001111011
bs4 已经 reset：00000000
bs2 AND bs3: 000010001
bs2 OR bs3: 001111011
bs2 XOR bx3: 001101010

例题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

提示：

1
2
0 <= s.length <= 5 * 1e4
s 由英文字母、数字、符号和空格组成

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

算法：双指针 + bitset

用 hashset 维护双指针中的元素，如果仅有小写字母，可以用状态压缩的方式用一个 int 维护集合信息。这里字符不止小写字母，因此可以用 bitset<128> 代替。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int n = s.size();
        int i = 0, j = 0;
        bitset<128> state;
        int ans = 0;
        while(i < n && j < n)
        {
            // 推进 j
            while(j < n && !state[(int)s[j]])
            {
                state.set((int)s[j]);
                ++j;
            }
            // [i..j-1] 为候选答案
            ans = max(ans, j - i);
            // 推进 i
            if(j == n) break;
            char target = s[j];
            while(s[i] != target)
            {
                state.reset((int)s[i]);
                ++i;
            }
            state.reset((int)s[i]);
            ++i;
        }
        return ans;
    }
};
Share