问题标题: c++ bitset类

在我的网站内阅读效果更佳

什么是 std::bitset

std::bitset是C++标准库中用于存储bool值的容器。

std::bitset通过固定的优化，让bool值的存储变得更加节约内存和时间（其实就是01串状态压缩）。

在标准的bool数组中，因为计算机存储数据的最小单元是字节(byte)，因此一个bool类型的变量实际占用了8个字节，这就造成了极大的空间浪费，而bitset解决了这个问题。

std::vector的一个特化vector<bool>的储存方式同std::bitset一样，区别在于其支持动态开空间。

不过，因为std::bitset拥有更多专门处理bool值的库函数，所以在没有特殊需求的情况下一般使用bitset。

std::bitset 的基本使用

头文件

#include <bitset>

定义

// bitset<大小> bs;
bitset<1000> bs;

运算

// bs[x]：访问第x位
bs[0] = true;
// bs1 ==/!= bs2：比较bs1和bs2是否相同
if (bs1 == bs2) { ... }
// bitset支持位运算
bs |= 1;

库函数

bs.count(); // 返回 true 的数量
bs.size(); //返回 bs 的大小
bs.to_string(); //返回 bs 的字符串表达
bs.to_ulong(); //返回 bs 对应的 unsigned long 值

std::bitset 的复杂度

std::bitset的时间复杂度一般记作O(n/w)（O(n)为对应bool数组的复杂度，w为32）

std::bitset 的应用

洛谷P4289：

这道题有dfs的解法，不过思路较为复杂。但是用bitset暴力广搜，更为简单。

q.push({st, 0});
vis[st.to_ulong()] = 1;
while (!q.empty()) { // bfs模板
    auto h = q.front();
    q.pop();
    if (h.x == ed) { // 到了目标状态
        cout << h.bs;
        return;
    }
    for (int i = 1; i <= 4; i++) { // 遍历每个点
        for (int j = 1; j <= 4; j++) {
            if (h.x[(i - 1) * 4 + j - 1]) { // 若该点可以移动
                for (auto k : dir) { // 遍历下一点
                    int nx = i + k[0], ny = j + k[1];
                    if (nx >= 1 && ny >= 1 && nx <= 4 && ny <= 4 && !h.x[(nx - 1) * 4 + ny - 1]) { // 若下一点可以移动到
                        auto n = h.x;
                        n[(i - 1) * 4 + j - 1] = 0;
                        n[(nx - 1) * 4 + ny - 1] = 1;
                        if (!vis[n.to_ulong()]) { // 若下一点未被走过
                            vis[n.to_ulong()] = 1; 
                            q.push({n, h.bs + 1}); //继续广搜
                        }
                    }
                }
            }
        }
    }
}