在大数组中有效地找到最低有效设置位？
我有一个巨大的内存块（位向量），在一个内存页中大小为N位，考虑N平均为 5000，即 5k 位来存储一些标志信息。
在某个时间点（超级频繁 - 关键），我需要在整个大位向量中找到第一个位集。现在我每 64 个字都这样做，即在 ) 的帮助下__builtin_ctzll。但是当N增长并且搜索算法无法改进时，可以通过扩展内存访问宽度来扩展此搜索。这是几句话的主要问题
有一条被调用的汇编指令BSF 给出了最高设置位（GCC's __builtin_ctzll()）的位置。因此，在x86-64 arch 中，我可以在 64 位字中廉价地找到最高位。
但是通过内存宽度进行缩放呢？
例如，有没有办法用 128 / 256 / 512 位寄存器有效地做到这一点？
基本上我对一些 C API 函数来实现这个感兴趣，但也想知道这个方法是基于什么的。
UPD：至于 CPU，我对这种优化感兴趣，以支持以下 CPU 阵容：
英特尔至强 E3-12XX、英特尔至强 E5-22XX/26XX/E56XX、英特尔酷睿 i3-5XX/4XXX/8XXX、英特尔酷睿 i5- 7XX、英特尔赛扬 G18XX/G49XX（英特尔凌动 N2600、英特尔赛扬 N2807、Cortex-A53/72 可选）
PS在最终位扫描之前提到的算法中，我需要将k（平均 20-40）个N位向量与 CPU AND相加（AND 结果只是位扫描的准备阶段）。这也适用于内存宽度缩放（即比每 64 位字 AND 更有效）
另请阅读：查找第一组
回答
这个答案是不同的，但如果你事先知道你将维护一个 B 位的集合，并且需要能够有效地设置和清除位，同时还要弄清楚哪个位是第一个设置的位，您可能想要使用像van Emde Boas 树或y-fast trie这样的数据结构。这些数据结构旨在存储小范围内的整数，因此您可以添加或删除要设置/清除的位的索引，而不是设置或清除单个位。它们非常快 - 您可以在 O(log log B) 时间内添加或删除项目，并且它们可以让您在 O(1) 时间内找到最小的项目。如图，如果 B ？50000，那么log log B大约是4。
我知道这并没有直接解决如何在巨大的位向量中找到最高位的问题。如果您的设置必须使用位向量，则其他答案可能会更有帮助。但是，如果您可以选择以不涉及位向量搜索的方式重新构建问题，那么这些其他数据结构可能更适合。
-
Thanks for the information!
The bottleneck of the algorithm is precisely the final search (bit-scan), because it is linear. Setting and clearing bits is one level lower in other data structures, and it is not super-frequent..