c++ - 在数组中的指定索引之前查找最近使用的索引(快速)

Question

这个问题与Array of pairs of 3 bit elements有关
这个数组有 52 对(大约 40 个字节)，我想在指定的一对之前找到第一对，它的值不同于 0(使用的对)。显而易见的解决方案是检查每一对<而不是这一对(从右到左扫描)，但如果有许多未使用的对(设置为 0)，这似乎效率很低。

这张图片可以更好地解释情况:

使用了 0、1 和 51 对。
我想找到 51(这里是 1)之前使用的第一个对。

我试过像

这样的技巧

if(*((int *)&array[arrayPos]) == 0) {
    arrayPos -= sizeof(int);
    pairPos -= ???
}  

这里的问题是从 pairPos 中减去不是那么简单，因为 6 位/对，所以我以基于 pairPos 和 arrayPos，所有这些使得解决方案的性能与普通解决方案一样。

有什么方法可以加快查找速度吗？另一个问题是只有 1 个未使用的字节......也许我可以为另外 4 个腾出空间。如果至少有 7 个我可以使用数组的位图并且跳过未使用的对会更快。

Answer 1

您能说说表示空对的相邻字节值吗？

我想建议查看字节而不是位。

任何给定的字节如果要成为一对空的 6 位字符的左侧贡献者，则必须符合特定的位掩码，其值取决于他的位置。 ？？ ？？ 00 00 或 ?? 00 00 00 或其他。您可以依次考虑每个字节作为最左边的字节的候选资格。可以使用一个简单的查找表来确定要使用的掩码。

因此，我们实际上不必在考虑之前提取 6 位字符。

我们是否可以做得更好，丢弃了一个字节作为候选字节，我们现在可以跳过左边的字节吗？

在我们的掩码为 00 00 00 00 的情况下，如果失败则我们左边的邻居，如果第一位已设置则为是。

这真的会让事情变得更快吗？