查找阵列中指定索引之前最近使用过的索引（快速）

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 and arrayPos，所有这些使得解决方案的表现像微不足道。

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

Answer 1

我发现最好的解决办法是：
1.使项目1个字节（不超过6位前） - 感谢Skizz
2.使用位图，看看哪些项目是最近的左侧。这要比用djna描述的技术快得多。

速度的改进是令人印象深刻：
在一个测试用例 ，从13S现在6.5s
是在一个又一个，从7.4S到3.6s
性能已经翻了一番：d再次

感谢你的答案！

Answer 2

存在针对搜索位数组的处理器特定指令。这些可以作为编译器内部函数提供。许多Linux文件系统广泛使用这些文件系统。

__builtin_ffs（）是GCC中的一个。

ffsll（）可能是POSIX，尽管直到现在我还没有听说过。

Answer 3

你能说一下表示空对的相邻字节值吗？

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

任何给定的字节，如果它是一对空的6位字符的左手贡献者，必须适合一个特定的位掩码，其值取决于他的位置。 ?? ?? 00 00还是?? 00 00 00或其他。您可以将每个字节依次视为最左边的字节。可以使用哪个掩码的简单查找表。

因此，我们实际上并没有在考虑它们之前拔出6位字符。

我们可以做得更好吗，丢弃了一个字节作为候选人，我们现在可以跳过一个离开吗？

在我们的掩码是00 00 00 00的情况下，如果失败了，那么我们的邻居在左边，如果第一位被设置，是。

这是否真的让事情更快？

Answer 4

按组处理6位值。

您可以在32位字中使用5个值的组，这会浪费2位或大约7％的空间。如果一个单词中的所有值都是0，那么这个单词是零，因此找到一个非空单词很快，然后检查该单词中的5个值。

如果你不能忍受一点浪费的空间，使用96位组，其中96是6和32的最小公倍数。将16位16位值分成三个32位字。