字节数组中特定3位模式0b101的出现次数统计优化咨询

你的原始实现思路正确（O(1)空间），但存在性能瓶颈：每个字节需要循环6次检查3位窗口，带来额外的循环控制和位运算开销。以下是两种更优的优化方案，均保持O(1)空间复杂度，同时显著提升运行效率。

方案一：预计算查找表（推荐，简洁高效） #

核心思路是提前为所有可能的字节值（0-255）预计算单个字节内部0b101的出现次数；处理跨字节模式时，仅需保留前一个字节的最后2位，与当前字节的前1-2位组合检查即可，无需累积整个字节流。

实现代码 #

#include <array>

// 编译期预计算每个字节内部的0b101出现次数
constexpr int compute_inner_count(uint8_t b) {
    int count = 0;
    // 检查字节内的6个3位窗口：bits7-5, 6-4, ..., 2-0
    for (int i = 0; i <= 5; ++i) {
        if (((b >> (5 - i)) & 0b111) == 0b101) {
            ++count;
        }
    }
    return count;
}

// 编译期生成查找表
constexpr std::array<int, 256> inner_counts = []() {
    std::array<int, 256> arr{};
    for (int i = 0; i < 256; ++i) {
        arr[i] = compute_inner_count(static_cast<uint8_t>(i));
    }
    return arr;
}();

int count_3bit_pattern_occurrences(const uint8_t* array, size_t size) {
    if (size == 0) return 0;

    int count = 0;
    uint8_t prev_suffix = array[0] & 0b11; // 保留第一个字节的最后2位
    count += inner_counts[array[0]];

    for (size_t i = 1; i < size; ++i) {
        const uint8_t curr = array[i];
        // 检查跨字节的第一个3位窗口：前字节最后2位 + 当前字节最高位
        const uint8_t triplet1 = (prev_suffix << 1) | (curr >> 7);
        if (triplet1 == 0b101) {
            ++count;
        }
        // 检查跨字节的第二个3位窗口：前字节最后1位 + 当前字节最高2位
        const uint8_t triplet2 = ((prev_suffix & 1) << 2) | (curr >> 6);
        if (triplet2 == 0b101) {
            ++count;
        }
        // 累加当前字节内部的出现次数
        count += inner_counts[curr];
        // 更新后缀为当前字节的最后2位
        prev_suffix = curr & 0b11;
    }

    return count;
}

优化点说明 #

• 消除内层循环：每个字节仅需2次跨字节检查 + 1次查表，替代原有的6次循环检查，大幅减少运算量。
• 编译期预计算：查找表在编译阶段生成，无 runtime 初始化开销，且完全缓存友好（256字节大小，可直接放入L1缓存）。
• 位运算简化：跨字节检查仅用简单的移位和或操作，避免复杂的位掩码计算。

方案二：SIMD并行处理（进阶，极致性能） #

如果目标平台支持SSE/AVX指令集，可以一次性处理16/32字节，通过并行位运算统计所有模式出现次数。这种方案复杂度较高，但能最大化利用CPU的向量计算能力。核心思路是：

1. 将字节流加载到SIMD寄存器中
2. 使用位掩码和比较指令，一次性标记所有匹配0b101的3位窗口
3. 统计标记位的数量并累加

由于实现依赖具体硬件指令集，这里不再展开，适合对性能有极致要求的场景。

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