C++ bitset 模板类

bitset<256> 数据类型详解

bitset<256> 是 C++ 标准库中的一个模板类，用于处理固定大小的位集合（Bit Set）。它可以高效地操作和存储二进制位，特别适合需要处理大量布尔标志或简单计数的场景。

基本定义与特性

1. 模板参数

bitset<N> 中的 N 表示位集合的固定大小（必须是编译时常量）。例如：

• bitset<8>：8 位（1 字节）的位集合
• bitset<256>：256 位（32 字节）的位集合

2. 核心特性

• 按位存储：每个位仅占 1 位内存，空间效率极高。
• 编译时确定大小：大小在编译期确定，不支持运行时动态调整。
• 位操作支持：提供按位与、或、异或、取反等操作。

在 LeetCode 266 中的应用

在判断回文排列的问题中，bitset<256> 用于记录字符出现次数的奇偶性：

bitset<256> bits;  // 256 位，对应 ASCII 字符集的 256 个字符

for (char c : s) {
    bits.flip(c);  // 每次遇到字符 c，翻转其对应位（0变1，1变0）
}

return bits.count() <= 1;  // 统计1的个数（奇数次字符的数量）

工作原理：

• 每个字符的 ASCII 码（0~255）对应 bitset<256> 中的一个位。
• 字符首次出现时，对应位设为 1（奇数次）；再次出现时，对应位设为 0（偶数次）。
• 最终 bits.count() 返回值为 1 的位的数量，即出现奇数次的字符数量。

常用操作与方法

1. 位操作

2. 统计与查询

3. 位运算

支持按位与（&）、或（|）、异或（^）、取反（~）等运算符。

示例：bitset 基本操作

#include <bitset>
#include <iostream>

int main() {
    // 创建 8 位的 bitset
    std::bitset<8> bits;
    
    // 设置位
    bits.set(0, 1);  // 第 0 位设为 1
    bits.set(3);     // 第 3 位设为 1（默认值 1）
    
    // 翻转位
    bits.flip(3);    // 第 3 位从 1 变 0
    
    // 访问位
    std::cout << "第 0 位: " << bits[0] << std::endl;  // 输出: 1
    std::cout << "第 3 位: " << bits[3] << std::endl;  // 输出: 0
    
    // 统计
    std::cout << "1的个数: " << bits.count() << std::endl;  // 输出: 1
    std::cout << "二进制表示: " << bits << std::endl;       // 输出: 00000001
    
    return 0;
}

与其他数据结构的对比

总结

bitset<256> 是一种高效的位操作工具，特别适合：

• 处理已知范围的离散值（如 ASCII 字符集）。
• 需要标记奇偶性、存在性的场景。
• 追求极致空间效率的算法（如回文排列判断、布隆过滤器）。

在 LeetCode 266 题中，它通过位翻转操作巧妙地统计了奇数次字符的数量，代码简洁且效率极高。

另： 关于256

bitset<256> 中数字 256 的充足性分析

在计算机科学中，256 是一个非常关键的数值，它在字符编码、位操作等场景中具有特殊意义。以下从多个维度分析 256 的充足性：

1. 字符编码层面：完全覆盖常用字符集

• ASCII 码范围：标准 ASCII 码使用 7 位表示 128 个字符（0~127），扩展 ASCII 码用 8 位表示 256 个字符（0~255）。

  • 常见字符（字母、数字、符号、控制字符）均包含在 0~127 范围内。
  • 扩展 ASCII 码覆盖了西欧语言字符、特殊符号等（如 €、© 等）。

• 实际应用场景：
  在 LeetCode 266 题（回文排列）中，输入字符串通常由常见字符组成，256 足以覆盖所有可能出现的字符。即使处理包含扩展 ASCII 字符的字符串，256 也能完全容纳。

2. 位操作层面：空间与效率的平衡

• 空间占用：bitset<256> 占用 32 字节（256位），相比其他数据结构（如 unordered_map）节省大量空间。

  • 若使用 int[256]，需占用 1024 字节（256×4字节），空间开销是 bitset 的 32 倍。
  • 若使用 unordered_map<char, int>，每个键值对至少占用 24 字节（含哈希表开销），存储 256 个字符时空间开销更大。

• 操作效率：位操作（如 flip、count）是硬件级指令，效率极高。例如：

  bitset<256> bits;
  bits.flip(c);  // 直接操作第 c 位，时间复杂度 O(1)
  

  这种效率是哈希表或数组无法比拟的。

3. 边界情况验证：极端输入的覆盖能力

• 最大字符值测试：
  当字符为 char 类型的最大值（即 255，二进制 11111111）时，bitset<256> 的第 255 位会被正确操作，不会越界。

  • 若使用 bitset<128>，则无法处理扩展 ASCII 字符（128~255），导致漏判。

• 多语言字符场景：
  若输入包含 Unicode 字符（如中文、日文等），char 类型只能存储其 UTF-8 编码的部分字节（每个 Unicode 字符可能占用 2~4 字节）。此时：

  • 若直接用 char 类型遍历字符串，会将多字节字符拆分为多个单字节处理，导致 bitset<256> 误判。
  • 但在 LeetCode 此类题目中，输入通常为单字节字符（如英文、数字），256 足够使用。
  • 若需处理 Unicode 字符，需改用 wchar_t 或 char32_t，并调整 bitset 大小（如 bitset<65536> 对应 UTF-16）。

4. 与其他数值的对比：为什么不用更大或更小的数？

5. 实际应用案例：LeetCode 中的典型场景

• 回文排列（LeetCode 266）：
  题目要求判断字符串是否可以重新排列成回文，核心逻辑是：最多一个字符出现奇数次。

  • 使用 bitset<256> 时，每个字符的 ASCII 码对应一个位，翻转操作记录奇偶性，最终统计 1 的个数。
  • 若输入包含扩展 ASCII 字符（如 ñ，ASCII 码 241），bitset<256> 仍能正确处理。

• 同构字符串（LeetCode 205）：
  虽然该题更适合用哈希表，但如果用 bitset，256 也足以记录两个字符串的字符映射关系。

结论：256 是字符处理场景的理想选择

• 充足性：完全覆盖 ASCII 及扩展 ASCII 字符集，满足 99% 以上的字符处理需求。
• 高效性：32 字节的固定空间开销，搭配硬件级位操作，效率极高。
• 通用性：在 LeetCode 等算法题目中，bitset<256> 是处理字符奇偶性、存在性的标准方案。

扩展建议：若需处理 Unicode 字符，可改用 bitset<65536>（对应 UTF-16）或 bitset<1114112>（对应 UTF-32），但需注意空间开销的显著增加。