位运算替代布尔数组可将100万布尔值内存从约1MB压缩至125KB，核心是每个uint64_t存储64个bit状态；需封装安全的set/get/clear接口，校验索引、用i&63代替i%64，并注意多线程下原子性保护。
位运算替代布尔数组的内存优化原理
用 std::vector<bool></bool> 或原生 bool[] 存 100 万个布尔值，实际占约 1MB；而用位运算手动打包到 uint64_t 数组里，只需约 125KB——压缩比接近 8:1。这不是理论值，是真实可测的内存节省，尤其在嵌入式、高频交易或大规模图算法中直接影响性能边界。
核心原理很简单：一个 uint64_t 能存 64 个布尔值，每个 bit 对应一个状态。关键不是“能不能”，而是“怎么安全又不失可读地做”。别直接裸写 (data[i/64] >> (i%64)) & 1，容易越界、符号扩展出错、大小端混淆。
手动实现 bitset-like 的 set/get/clear 操作
自己封装一套最小可用接口，比依赖 std::bitset（编译期固定大小）或 boost::dynamic_bitset（引入外部依赖）更可控，也更容易调试。
-
索引必须校验：
i >= size * 64时访问会越界，建议构造时传入总位数n_bits，内部按(n_bits + 63) / 64分配uint64_t* -
位偏移用
i & 63，别用i % 64：前者是编译器能优化的位运算，后者可能生成除法指令（尤其在未开启 -O2 时） -
写操作必须原子性保护：如果多线程同时改同一
uint64_t中不同 bit，仍需std::atomic<uint64_t></uint64_t>或加锁——位运算是非原子的 - 示例 get 操作：
bool get(size_t i) const { return (data[i / 64] & (static_cast<uint64_t>(1) << (i & 63))) != 0; }
与 std::vector 的行为差异和陷阱
std::vector<bool></bool> 是特化容器，返回的是代理对象 std::vector<bool>::reference</bool>，不是 bool&。这导致很多看似合法的代码崩溃或静默错误：
立即学习“C++免费学习笔记（深入）”；
-
auto& b = vec[i]; b = true;✅ 可行（代理重载了operator=） -
bool* p = &vec[i];❌ 编译失败（代理对象不可取地址） -
for (bool b : vec)✅ 但每次迭代都拷贝值，无法修改原位 - 用
std::memcpy直接拷贝vec.data()得到的是压缩后的字节流，不是连续 bool 序列，不可跨平台直接序列化
如果你需要取地址、迭代修改、或保证内存布局完全可控，就别用 std::vector<bool></bool> —— 它是妥协产物，不是通用解。
批量操作：如何高效 flip / count / find_first_set
单 bit 操作只是起点。真正体现位运算价值的是 word-level 并行处理：
-
flip range：用掩码异或，比如翻转 [L,R] 区间，先算出覆盖的完整
uint64_t块，再对首尾做 partial mask，比循环调用set(!get(i))快 10–50 倍 -
popcount：用
__builtin_popcountll(x)（GCC/Clang）或std::popcount(x)（C++20），比手写循环快一个数量级；注意unsigned long long和uint64_t在某些平台不等价，强制 cast 更安全 -
find_first_set：用
__builtin_ctzll(x)找最低位 1 的位置，配合x &= x-1迭代找所有置位——比从头扫描快得多，但要注意x == 0时ctzll行为未定义，必须先判断
这些操作在布隆过滤器、稀疏矩阵、状态压缩 DP 中反复出现，写一次健壮封装，后面项目里直接复用，比每次重新推导位逻辑更省时间。
