如何高效搜索 128 位二进制串的部分匹配？

2026-11-04数据小许

结论

针对这条匹配规则，可以先用两个 uint64_t 表示 128 位 Haystack 和 Needle，再逐个偏移对齐，通过 XOR 和掩码比较。这是适用于 Ivy Bridge 的直接基线：每个偏移只需少量 64 位整数操作，也能由 MSVC 编译。SSE4.2 的字符串指令按字节比较，无法直接处理任意位偏移。若先旋转数据再使用这些指令，通常会增加开销，是否值得采用要看实际基准测试结果。

下面的实现假设两对 64 位值都按 MSB 对齐：逻辑位 0 位于 hi 的最高位，逻辑位 64 位于 lo 的最高位。对于偏移 k，只比较 min(NeedleLen, 128-k) 个重叠位。函数返回最小匹配偏移 0..127；没有匹配时返回 -1。

C 实现

#include <stdint.h>

static uint64_t mask_top_bits(unsigned n)
{
    if (n == 64)
        return UINT64_MAX;
    return UINT64_MAX << (64 - n);  // n 在此处为 1..63
}

static void shift_left_128(uint64_t hi, uint64_t lo, unsigned shift,
                           uint64_t *out_hi, uint64_t *out_lo)
{
    if (shift == 0) {
        *out_hi = hi;
        *out_lo = lo;
    } else if (shift < 64) {
        *out_hi = (hi << shift) | (lo >> (64 - shift));
        *out_lo = lo << shift;
    } else {
        *out_hi = lo << (shift - 64);
        *out_lo = 0;
    }
}

/*
 * hi/lo 均为 MSB 对齐的 128 位值。
 * needle_len 必须在 2..128 之间。
 */
int cross_correlate_128(uint64_t hay_hi, uint64_t hay_lo,
                        uint64_t needle_hi, uint64_t needle_lo,
                        unsigned needle_len)
{
    if (needle_len < 2 || needle_len > 128)
        return -1;

    for (unsigned k = 0; k < 128; ++k) {
        unsigned overlap = needle_len < 128 - k
                         ? needle_len : 128 - k;
        uint64_t aligned_hi, aligned_lo;

        shift_left_128(hay_hi, hay_lo, k, &aligned_hi, &aligned_lo);

        if (overlap <= 64) {
            uint64_t diff = aligned_hi ^ needle_hi;
            if ((diff & mask_top_bits(overlap)) == 0)
                return (int)k;
        } else {
            unsigned low_bits = overlap - 64;
            if (aligned_hi == needle_hi &&
                (((aligned_lo ^ needle_lo) & mask_top_bits(low_bits)) == 0))
                return (int)k;
        }
    }

    return -1;
}

needle_hi 和 needle_lo 只需将 Needle 的有效位从最高位开始排列；比较掩码会忽略 Needle 长度之外的位。如果数据来自字节数组，应按大端位序组装这两个整数，避免将平台的内存字节序误当成题目要求的位序。

性能取舍

每个偏移最多检查两个 64 位片段。虽然这不是 SIMD 实现，但它省去了逐位循环，可以作为 Ivy Bridge 上的性能基线。先用真实输入分布测量吞吐量，再决定是否增加复杂度。
Needle 长度不超过 64 位时，匹配检查只需比较一个经过掩码处理的 64 位片段；较长的 Needle 才需要检查第二个片段。若调用频繁，可以按 Needle 长度分开处理，减少循环中的条件判断。
AVX1 和 SSE4.2 都没有能直接按任意位偏移比较这两段数据的指令。PCMPESTRI / PCMPESTRM 按字节处理元素；题目中的部分重叠行为还取决于字符串指令的长度和终止规则，因此不能直接用它们实现等价的任意位匹配。
对 AVX2 及更新的 CPU，可以考虑并行检查多个候选偏移，但需要为每个候选生成对齐窗口和有效位掩码。它是否快于上述整数循环，取决于 Needle 长度、命中位置和批量调用方式，应在目标机器上实测。Ivy Bridge 不支持 AVX2，因此这类路径只能用于后续 CPU 的专门实现。

需要确认的匹配语义

按题目给出的规则，Haystack 末尾附近的候选偏移只需匹配剩余的重叠位。因此，偏移 127 只比较一个位，可能产生很短的尾部匹配。如果业务要求至少匹配指定长度，或只接受完整 Needle 匹配，可以在计算 overlap 后加入相应限制。这会改变当前定义下的返回结果。