c - 有效地找到大数组中的最低有效位？

Question

我在一个内存页中有一个大小为 N 位的巨大内存块(位 vector )，考虑 N 平均为 5000，即 5k 位来存储一些标志信息。
在某个时间点(超频繁 - 关键)，我需要在整个大位 vector 中找到第一个位集。现在我按 64 个字来做，即在 __builtin_ctzll 的帮助下)。但是当 N 增长并且搜索算法无法改进时，可以通过扩展内存访问宽度来扩展这种搜索。这是几句话的主要问题
有一条汇编指令叫做 BSF 它给出了最高设置位的位置(GCC 的 __builtin_ctzll() )。
所以在 x86-64我可以在 64 位字中廉价地找到最高位。
但是通过内存宽度扩展呢？
例如。有没有办法使用 128/256/512 位寄存器有效地做到这一点？
基本上我对一些C API函数来实现这个感兴趣，但也想知道这个方法是基于什么的。
更新:至于 CPU，我对这种优化很感兴趣，以支持以下 CPU 阵容:
Intel Xeon E3-12XX、Intel Xeon E5-22XX/26XX/E56XX、Intel Core i3-5XX/4XXX/8XXX、Intel Core i5-7XX、Intel Celeron G18XX/G49XX(Intel Atom N2600、Intel Celeron N2807、Cortex-可选A53/72)
附言在最终位扫描之前提到的算法中，我需要将 k(平均 20-40)N 位 vector 与 CPU AND 相加(AND 结果只是位扫描的准备阶段)。这对于内存宽度缩放也是可取的(即比每 64 位字 AND 更有效)
另请阅读:Find first set

Answer 1

这个答案是不同的，但如果你事先知道你将要维护一个 B 位的集合，并且需要能够有效地设置和清除位，同时还要弄清楚哪个位是第一个设置的位，你可能想使用像 van Emde Boas tree 这样的数据结构。或 y-fast trie .这些数据结构旨在存储小范围内的整数，因此您可以添加或删除要设置/清除的位的索引，而不是设置或清除单个位。它们非常快 - 您可以在 O(log log B) 时间内添加或删除项目，并且它们让您在 O(1) 时间内找到最小的项目。假设如果 B ≈ 50000，则 log log B 约为 4。
我知道这并没有直接解决如何在巨大的位 vector 中找到最高位。如果您的设置必须使用位 vector ，那么其他答案可能会更有帮助。但是，如果您可以选择以不涉及位 vector 搜索的方式重新构建问题，那么这些其他数据结构可能更适合。