如何统计boost::dynamic_bitset指定区间内的置1位且不修改原对象

核心思路是直接访问boost::dynamic_bitset的底层块存储结构，复用boost内置的优化popcount逻辑，全程无需拷贝原比特集，性能和原生count()方法基本一致，完全满足不修改原对象、优先使用优化计数能力的需求。

实现逻辑 #

boost::dynamic_bitset内部以固定大小的原生整数为存储块（通常是32位或64位无符号整数），对外暴露了只读访问块的接口，我们可以把待统计的区间拆分为三部分分别计算：

• 起始位置所在的首个不完整块：用掩码清除区间外的低位后计数
• 中间所有完整的块：直接调用优化的popcount计数
• 结束位置所在的末尾不完整块：用掩码清除区间外的高位后计数

示例代码 #

#include <boost/dynamic_bitset.hpp>
#include <cstdint>
#include <algorithm>

template <typename Block, typename Allocator>
uint64_t count_range(const boost::dynamic_bitset<Block, Allocator>& bits, size_t start, size_t end) {
    // 边界校验
    if (start >= bits.size() || end <= start) return 0;
    end = std::min(end, bits.size());

    const size_t bits_per_block = boost::dynamic_bitset<Block, Allocator>::bits_per_block;
    uint64_t total = 0;

    size_t first_block = start / bits_per_block;
    size_t last_block = (end - 1) / bits_per_block;

    if (first_block == last_block) {
        // 区间完全落在同一个块内
        Block mask = ((Block(1) << (end - start)) - 1) << (start % bits_per_block);
        total += __builtin_popcountll(bits.get_block(first_block) & mask);
        return total;
    }

    // 处理首块
    size_t first_offset = start % bits_per_block;
    Block first_mask = ~((Block(1) << first_offset) - 1);
    total += __builtin_popcountll(bits.get_block(first_block) & first_mask);

    // 处理中间完整块
    for (size_t i = first_block + 1; i < last_block; ++i) {
        total += __builtin_popcountll(bits.get_block(i));
    }

    // 处理末尾块
    size_t last_offset = end % bits_per_block;
    Block last_mask = (Block(1) << last_offset) - 1;
    total += __builtin_popcountll(bits.get_block(last_block) & last_mask);

    return total;
}

说明 #

• 代码中使用的__builtin_popcountll是gcc/clang等编译器内置的优化popcount函数，和boostcount()方法的底层实现完全一致，硬件支持的场景下会直接调用CPU的POPCNT指令，性能达到最优。如果使用MSVC编译器，替换为_mm_popcnt_u64即可。
• 全程只读访问原比特集，没有任何拷贝操作，内存开销为O(1)，比特集规模越大，相比拷贝副本的方案性能优势越明显。

内容的提问来源于stack exchange，提问作者escapist