algorithm - 计算在任何位偏移处包含 4 位值的字节的最快方法？

Question

我有一个算法来搜索包含 64 个字节值的数组，我想找到一个 4 位值并查看它在数组中出现了多少次。

例如，数组中的第一个元素可能是 10101010，而 4 位值是 1010，其中这只计算一次。如果下一个元素是 10000000，这将算作 0。

遍历数组中的所有元素并检查每个元素是否包含我们的 4 位结果很容易，但是有没有更快的方法来做到这一点？

Answer 1

precompute:
- 4bit key offset by 0bit
- 4bit key offset by 1bit
- 4bit key offset by 2bit
- 4bit key offset by 3bit

- 4 bit mask offset by 0bit
- 4 bit mask offset by 1bit
- 4 bit mask offset by 2bit
- 4 bit mask offset by 3bit

for each byte in bytes:
  for each offset:
    mask out bytes we care about
    check if it matches our precomputed key

• 由于我们未查看的任何项都可能匹配或不匹配，因此我们必须查看所有项，因此 O(n)至少。
• 由于一次查看所有项目就足够了，因此没有理由使用非线性算法。
• 因为总共只有 64 个值，高度优化的 SIMD 指令可能不值得这么麻烦。它不太可能提高性能。

---

key 和掩码的预计算是通过每次将 key 左移一位，并将掩码中的 4 个相关位设置为 1 来完成的。

match = (bytes[i] & (0x0F << offset)) == (key << offset)

对于一些 key和每个偏移量 0-3 .自 (key << offset)和 (0x0F << offset)将每四个循环重复使用一次，预先计算四个值并展开循环会更快。您的编译器可能会为您执行此操作，但如果没有，请按照以下方法手动执行此操作:

matches = 0
for (int i = 0; i < 64; i += 4) {
    const mask0 = 0x0F << 0
    const key0 = key << 0
    match0 = (bytes[i+0] & mask0) == key0

    const mask1 = 0x0F << 1
    const key1 = key << 1
    match1 = (bytes[i+1] & mask1) == key1

    ...

    matches += match0 + match1 + match2 + match3
}