对于稀疏位集（全真或全假，少数例外），您可以使用任何集合数据结构（包括哈希表）来存储一组索引。当然，您可以在 asm 中手动实现任何算法，就像在 C 中一样。可能有一些更专门的数据结构适合各种目的/用例。
对于“正常”的布尔数组，您的两个主要选项是
-
每个字节解压 1 个 bool，值 0 / 1，如 Cbool arr[size]
(in .bss或者动态分配，无论你想把它放在哪里，与任何字节数组相同).
占用打包位数组空间（以及缓存占用空间）的 8 倍，但是非常容易使用。对于随机访问特别有效，尤其是写入，因为您可以存储一个字节而不会干扰其邻居。 （不必读取/修改/写入包含的字节或双字）。
除了缓存占用空间会导致更多缓存未命中（如果它加上其余数据不适合任何级别的缓存）之外，较低的密度也不利于搜索、弹出计数、复制或设置/清除一系列元素。
如果可以在写入数组的代码中保存指令，则可以允许 0 / 非 0，而不是 0 / 1。但是，如果您想比较两个元素或计算真实值或其他任何内容，那么在阅读时可能会花费指令。请注意，大多数 C/C++ ABI 严格使用 0 / 1 字节bool，并通过bool拿着一个2到 C 函数可能会导致崩溃 https://stackoverflow.com/questions/54120862/does-the-c-standard-allow-for-an-uninitialized-bool-to-crash-a-program/54125820#54125820.
-
每包装 1 布尔bit，如 C++std::vector<bool>。 （当然，您可以将其存储在任何您想要的地方，这与总是动态分配的 std::vector 不同）。
霍华德·辛南特的文章On vector<bool> https://isocpp.org/blog/2012/11/on-vectorbool讨论了位数组擅长的一些事情（通过适当优化的实现），例如寻找一个true可以一次检查整个块，例如使用 qword 搜索一次 64 位，或者使用 AVX 一次 256 位vptest。 （然后tzcnt or bsf当您找到非零块时，或多或少与字节元素相同：有效地找到大型数组中的最低有效设置位？ https://stackoverflow.com/questions/67605508/efficiently-find-least-significant-set-bit-in-a-large-array）。因此，比字节数组快 8 倍（即使假设缓存命中相同），除了使用 SIMD 进行向量化时需要进行一些额外的工作，以便在向量内找到正确的字节或双字后查找元素内的位。与字节数组相比vpslld $7, %ymm0, %ymm0 and vpmovmskb %ymm0, %eax / bsf %eax,%eax将字节转换为位图并搜索它。
x86 位数组又名位串指令：内存操作数缓慢
x86 does有位数组指令，例如bt https://www.felixcloutier.com/x86/bt（位测试）和bts https://www.felixcloutier.com/x86/bts（位测试和设置），还有重置（清除）和补码（翻转），但它们是慢速记忆目的地 https://stackoverflow.com/a/32704227/224132和寄存器位索引；实际上，手动索引正确的字节或双字并加载它，然后使用会更快bts %reg,%reg并存储结果。将 bts 汇编指令与 gcc 编译器一起使用 https://stackoverflow.com/questions/1983303/using-bts-assembly-instruction-with-gcc-compiler/33908467#33908467
# fast version:
# set the bit at index n (RSI) in bit-array at RDI
mov %esi, %edx # save the original low bits of the index
shr $5, %rsi # dword index = bit-index / 8 / 4
mov (%rdi, %rsi, 4), %eax # load the dword containing the bit
bts %edx, %eax # eax |= 1 << (n&31) BTS reg,reg masks the bit-index like shifts
mov %eax, (%rdi, %rsi, 4) # and store it back
这有效地将位索引分为双字索引和双字内位索引。双字索引是通过移位显式计算的（并通过缩放索引寻址模式转回对齐双字的字节偏移量）。双字内位索引是隐式计算的，作为如何计算的一部分bts %reg,%reg掩盖计数。
（如果您的位数组肯定小于 2^32 位（512 MiB），您可以使用以下方法节省一个字节的代码大小shr $5, %esi，丢弃位索引的高 32 位。）
这会在 CF 中留下旧位的副本，以防万一您关心。bts reg,reg在 Intel 上是单次，在 AND 上是 2 次，所以与手动操作相比绝对值得mov $1, %reg / shl / or.
在现代 Intel CPU 上这只有 5 uops (https://uops.info/ https://uops.info/ and https://agner.org/optimize/ https://agner.org/optimize/)，与 10 uop 相比bts %rsi, (%rdi)它执行完全相同的操作（但不需要任何 tmp 寄存器）。
您会注意到我只使用了双字块，而不是像在 C 中您经常看到的代码使用unsigned long or uint64_t块，以便搜索可以快速进行。但是在 asm 中，使用不同大小的访问相同的内存是零问题，除了如果先进行窄存储然后进行宽加载时存储转发停顿。更窄的 RMW 操作实际上更好，因为这意味着不同位上的操作可以更紧密地结合在一起，而不会实际创建错误的依赖关系。如果这是一个主要问题，您甚至可以使用字节访问，除了bts而朋友们只能降到 16 位word操作数大小，所以你必须手动and $7, %reg从位索引中提取字节内位。
例如像这样阅读：
# byte chunks takes more work:
mov %esi, %edx # save the original low bits
shr $3, %rsi # byte index = bit-index / 8
movzbl (%rdi, %rsi), %eax # load the byte containing the bit
and $7, %edx
bt %edx, %eax # CF = eax & 1 << (n&7)
# mov %al, (%rdi, %rsi) if you used BTS, BTR, or BTC
字节加载最好用movzx（又名 AT&Tmovzbl）以避免写入部分寄存器。
16位访问宽度是最好的权衡
bts适用于 16 位、32 位和 64 位操作数大小，其中 16 位是最窄的大小，我们仍然可以免费对计数进行掩码以获得字内位。movzx大多数 CPU 上的负载与 32 位负载一样便宜。
BMI2 shrx允许复制和移位，但需要另一个寄存器中的计数。在像埃拉托色尼筛这样需要进行大量位访问的用例中，值得在外循环之外使用一条指令来保存内循环中的指令。 （这与您使用 32 位还是 16 位块正交。）
; NASM syntax
; ahead of a loop
mov r13d, 4
; inside a loop
; set the bit at index n (ESI) in bit-array at RDI
shrx eax, esi, r13d ; eax = j >> 4 = index of aligned word containing the bit. Byte offsets would be worse, store-forwarding stalls as well as misalignment
movzx edx, word [rdi+rax*2]
bts dx, si ; BTS reg,reg is fast and does the mod 16 part for free.
mov [rdi+rax*2], dx
这是我在 x86-64 Linux 的 NASM 中使用的埃拉托斯特尼筛法（https://godbolt.org/z/vcz969bPa https://godbolt.org/z/vcz969bPa对于包含偶数的基本位数组，https://godbolt.org/z/Ee8j1hz1x https://godbolt.org/z/Ee8j1hz1x对于仅包含奇数的位图，因此需要额外的右移计数。令人惊讶的是，在许多情况下，速度并没有更快，也许只是在缓存大小之间的截止点。两者都没有尝试使用 SIMD 一次设置多个位以获取小素数或更好的局部性）。我最终可能会发布答案我评论了这个代码审查问答 https://codereview.stackexchange.com/questions/277090/sieve-of-eratosthenes-in-x86-assembly
在我的筛子中使用字操作数大小可以显着加快速度，对于一些较小的问题大小 IIRC 来说可能会加快 20%，特别是对于更密集的位图（省略偶数），其中设置每第 3 位将意味着大约 32/ 的大链3 = 10.6 次存储/重新加载每个双字，然后再继续下一个。使用较窄的块可以实现大约两倍的内存级别并行性。 （尽管对于较大的步幅，每次访问都是对不同的双字，但使用筛子时，步幅越小，该步幅的总访问次数就越多。）
线程安全原子
如果您需要原子地设置一点（例如在多线程程序中），你可以lock bts %reg, mem，或者你可以生成1<<(n&31)在寄存器中和lock or %reg, mem如果你不关心旧值是什么。lock bts无论如何，它很慢并且是微编码的，所以如果你需要原子性，你可能应该使用它，而不是试图避免疯狂的 CISC 位数组语义lock or.
在多线程情况下，更有理由考虑每个字节使用 1 个 bool，这样您就可以使用简单的movb $1, (%rdi, %rsi)（保证原子性并且不会干扰其邻居：现代 x86 硬件不能将单个字节存储到内存中吗？ https://stackoverflow.com/questions/46721075/can-modern-x86-hardware-not-store-a-single-byte-to-memory），而不是原子 RMW。
