C++ bitset类型的用法（附带实例）

bitset 是 C++ 标准库中的一个类，设计用于处理和操作固定大小的位序列，即一系列的二进制位，每一位取值为 0 或 1。

bitset 可被视为一个长度可观的二进制数，支持位运算及标准模板库中的其他操作。bitset 的结构如下图所示：


初始化 bitset 后，它的各位（val）默认均为 0。为了更好地演示，图中的某些位置预设为 1。需要特别注意的是，bitset 的索引是从右向左计算的，以保证与二进制数字的表达方式一致，这在执行位移运算时尤为重要。

C++ bitset的用法

在处理固定大小的二进制数据时，bitset 提供了一种高效且简便的方式。它不仅支持位级别的操作，还允许执行一些快速的整体位运算。

下表列出了一些 bitset 的常用操作方法及其时间复杂度。

表：bitset 的常用操作方法及其时间复杂度

方法	作用	时间复杂度
operator[idx]	返回 bitset 中第 idx 位的引用	O(1)
reset()	将 bitset 中所有位都设置为 0	O(n)
size()	返回 bitset 的大小，即位数	O(1)
count()	返回 bitset 中 1 的个数	O(n)
&, |, ~, <<, >>	整体位运算	O(n)

虽然上述部分操作的理论时间复杂度为 O(n)，但由于 bitset 的内部优化及其固定小常数的特点，实际执行速度非常快，可以达到 O(n/w)。其中 w 是机器的字长（如 64 或 32 位）。因此，在现代计算机上，bitset 的操作效率非常高。

每个二进制位支持单独的位运算，使用[]操作符取出对应位后，即可对其进行位级别的操作。这使得 bitset 在需要精细控制二进制数据的应用场景下尤为有用。

【实例】给定一个长度为 n 的整数数组，需要求出每个元素的二进制表示中 1 的个数。
1) 输入格式：

• 第一行：一个整数 n（1≤n≤2×10^5）。
• 第二行：n 个整数，表示数组 a（0≤ai≤2×10^9），其中 1≤i≤n。

2) 输出格式：
共一行，输出 n 个整数，其中第 i 个数为 ai 的二进制中1的个数。

样例：


可以利用 bitset 的 count() 函数直接解决，实现代码如下：

#include <bits/stdc++.h>
using namespace std;

signed main() // 主函数，返回值为int类型
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 关闭同步，提高输入/输出效率

    int n; cin >> n; // 输入一个整数n
    for(int i = 1; i <= n; ++ i) // 循环n次
    {
        int x; cin >> x; // 输入一个整数x
        cout << bitset<32>(x).count() << ' '; // 将x转换为32位的二进制数，计算其中1的个数并输出
    }
    return 0;
}