计算一个位置或更低位置的设置位的有效方法是什么？
What is the efficient way to count set bits at a position or lower?
给定 std::bitset<64> bits 设置了任意数量的位和一个位位置 X (0-63)
如果 X 处的位未设置，则计算位置 X 或更低位置或 return 0 的最有效方法是什么
注意：如果设置了该位，return 将始终至少为 1
暴力破解的方式很慢：
int countupto(std::bitset<64> bits, int X)
{
if (!bits[X]) return 0;
int total=1;
for (int i=0; i < X; ++i)
{
total+=bits[i];
}
return total;
}
bitset的count()方法会给你所有位的popcount，但是bitset不支持范围
注意：这不是 How to count the number of set bits in a 32-bit integer? 的重复，因为它询问所有不在 0 到 X
范围内的位
我的第一反应是测试指定的位，然后立即 return 0 是清楚的。
如果你超过了那个，创建一个位掩码，设置该位（和不太重要的位），并 and 使用原始输入。然后使用 count() 成员函数获取结果中设置的位数。
关于创建蒙版：您可以将 1 左移 N 个位置，然后减去 1。
假设 unsigned long 或 unsigned long long 足够大以容纳 64 位，您可以调用 bits.to_unlong()（或 bits.to_ullong()）以整数形式获取位集数据，屏蔽掉 X ((1 << X) - 1) 以上的位，然后按照您 link 到的问题的答案中给出的那些位进行计数。
在一个位和它下面的位的掩码之间转换很容易，所以像这样的东西应该可以工作：
int popcnt(bitset<64> bs, int x) {
// Early out when bit not set
if (!bs[x]) return 0;
// Otherwise, make mask from `x`, mask and count bits
return (bs & bitset<64>((1UL << x) - 1)).count() + 1;
}
这里的假设是 bitset::count 被有效地实现（使用 popcnt 内在函数或有效的回退）；这不能保证，但 STL 人员倾向于优化这类事情。
我编辑了一个我以前见过的问题，它会检查一个数字中设置的位数是奇数还是偶数。它适用于 C，但将其融入 C++ 应该不会太难。解决方案的关键在于 while 循环中的内容。在纸上尝试一下，了解它如何挑选出 LSB，然后将其从 x 中移除。其余代码很简单。代码在 O(n) 中运行，其中 n 是 x 中设置的位数。这比线性时间要好得多，我也认为只有在第一次看这个问题时才有可能。
#include <stdio.h>
int
count(long x, int pos)
{
/* if bit at location pos is not set, return 0 */
if (!((x >> pos) & 1))
{
return 0;
}
/* prepare x by removing set bits after position pos */
long tmp = x;
tmp = tmp >> (pos + 1);
tmp = tmp << (pos + 1);
x ^= tmp;
/* increment count every time the first set bit of x is removed (from the right) */
int y;
int count = 0;
while (x != 0)
{
y = x & ~(x - 1);
x ^= y;
count++;
}
return count;
}
int
main(void)
{
/* run tests */
long num = 0b1010111;
printf("%d\n", count(num, 0)); /* prints: 1 */
printf("%d\n", count(num, 1)); /* prints: 2 */
printf("%d\n", count(num, 2)); /* prints: 3 */
printf("%d\n", count(num, 3)); /* prints: 0 */
printf("%d\n", count(num, 4)); /* prints: 4 */
printf("%d\n", count(num, 5)); /* prints: 0 */
printf("%d\n", count(num, 6)); /* prints: 5 */
}
此 C++ 让 g++ 发出 very good x86 ASM (godbolt compiler explorer)。我希望它也能在其他 64 位架构上高效编译（如果有 std::bitset::count 的 HW popcount 可以使用，否则那将永远是缓慢的部分；例如确保使用 g++ -march=nehalem 或更高版本，或者-mpopcnt 如果您不想启用任何其他功能，如果您可以将您的代码限制为仅 运行 支持该 x86 指令的 CPUs:
#include <bitset>
int popcount_subset(std::bitset<64> A, int pos) {
int high_bits_to_eliminate = 63 - pos;
A <<= (high_bits_to_eliminate & 63); // puts A[pos] at A[63].
return (A[63]? ~0ULL : 0) & A.count(); // most efficient way: great code with gcc and clang
// see the godbolt link for some #ifdefs with other ways to do the check, like
// return A[BSET_SIZE-1] ? A.count() : 0;
}
这在 32 位架构上可能不是最佳选择，因此如果您需要进行 32 位构建，请比较其他替代方案。
这将适用于其他大小的位集，只要您对 hard-coded 63 做一些事情，并更改 & 63掩码换成更一般的计数range-check。为了在奇怪大小的位集上获得最佳性能，请为目标机器的 size <= register width 创建一个专门化的模板函数。在这种情况下，将 bitset 提取为适当宽度的 unsigned 类型，并移至寄存器的顶部而不是 bitset 的顶部。
您希望这也能为 bitset<32> 生成理想的代码，但事实并非如此。 gcc/clang 在 x86-64 上仍然使用 64 位寄存器。
对于大的位集，移动整个东西比只弹出包含 pos 的单词下面的单词并在那个单词上使用它要慢。 （如果您可以假设 SSSE3 而不是 popcnt insn 硬件支持，或者对于 32 位目标，这就是向量化 popcount 在 x86 上真正闪耀的地方。AVX2 256bit pshufb 是进行批量 popcounts 的最快方法，但是没有 AVX2，我认为 64 位 popcnt 非常接近 128 位 pshufb 实现。更多讨论请参阅评论。）
如果你有一个 64 位元素的数组，并且想分别计算每个元素中特定位置以下的位，那么你绝对应该使用 SIMD。该算法的移位部分矢量化，而不仅仅是 popcnt 部分。在基于 pshufb 的 popcnt 之后，对 all-zero 寄存器使用 horizontal-sum 字节到 64 位块中的 horizontal-sum 字节，该 popcnt 分别为每个字节中的位产生计数。 SSE/AVX 没有 64 位算术右移，但您可以使用不同的技术来混合每个元素的高位。
我是怎么想到这个的：
您希望编译器输出的 asm 指令将：
- 从 64 位值中删除不需要的位
- 测试所需位的最高位。
- popcount it.
- return 0 或 popcount，取决于测试结果。 （无分支或分支实现都有优势。如果分支是可预测的，则无分支实现往往更慢。）
执行 1 的明显方法是生成掩码 ((1<<(pos+1)) -1) 并 & 它。一种更有效的方法是 left-shift 通过 63-pos，将您想要的位打包在寄存器的顶部。
这还有一个有趣的地方side-effect，就是把你要测试的位作为寄存器的最高位。测试符号位，而不是任何其他任意位，需要的指令稍微少一些。算术右移可以将符号位广播到寄存器的其余部分，从而允许 more-efficient-than-usual 无分支代码。
做 popcount 是一个 much-discussed 问题，但实际上是难题中比较棘手的部分。在 x86 上，它有非常有效的硬件支持，但仅限于 recent-enough 硬件。在 Intel CPUs 上，popcnt 指令仅适用于 Nehalem 和更新版本。我忘记了 AMD 何时添加了支持。
所以为了安全地使用它，您需要使用不使用 popcnt 的后备进行 CPU 调度。或者，制作 do/don 不依赖某些 CPU 功能的单独二进制文件。
没有 popcnt 指令的 popcount 可以通过几种方法完成。一个使用 SSSE3 pshufb 来实现一个 4 位 LUT。不过，这在整个阵列上使用时最有效，而不是一次使用单个 64b。标量 bithacks 在这里可能是最好的，并且不需要 SSSE3（因此将与具有 64 位但不是 pshufb 的古老 AMD CPUs 兼容。）
比特广播：
(A[63]? ~0ULL : 0) 要求编译器将高位广播到所有其他位位置，允许它用作 AND-mask 以将 popcount 结果归零（或不归零）。请注意，即使对于大的 bitset 大小，它仍然只屏蔽 popcnt 的输出，而不是 bitset 本身，所以 ~0ULL 没问题我使用 ULL 来确保从未要求编译器广播仅位到寄存器的低 32b（例如 Windows 上的 UL）。
这个广播可以通过算术右移 63 来完成，这会移入高位的副本。
clang 从原始版本生成此代码。在 Glenn 对 4 的不同实现提出一些建议后，我意识到我可以通过编写更像我想要的 ASM 的源代码来引导 gcc 走向 clang 的最佳解决方案。更直接地请求算术右移的明显 ((int64_t)something) >> 63 将不是严格可移植的，因为带符号的 right-shifts 是 implementation-defined as either arithmetic or logical. The standard doesn't provide any portable arithmetic right-shift operator. (It's not undefined behaviour。）无论如何，幸运的是编译器足够聪明：gcc 看到最好的一旦你给了足够的提示。
此源代码使用 gcc 和 clang 在 x86-64 和 ARM64 上生成了很棒的代码。两者都简单地在 popcnt 的输入上使用算术右移（因此移位可以 运行 与 popcnt 并行）。它还在 32 位 x86 上使用 gcc 编译得很好，因为屏蔽只发生在 32 位变量上（在添加多个 popcnt 结果之后）。这是函数的其余部分在 32 位上很糟糕（当位集大于寄存器时）。
带有 gcc 的原始 ternary-operator 版本
使用 gcc 5.3.0 编译 -O3 -march=nehalem -mtune=haswell（较旧的 gcc，如 4.9.2，也仍然会发出此消息）：
; the original ternary-operator version. See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
; input bitset in rdi, input count in esi (SysV ABI)
mov ecx, esi ; x86 variable-count shift requires the count in cl
xor edx, edx ; edx=0
xor eax, eax ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
not ecx ; two's complement bithack for 63-pos (in the low bits of the register)
sal rdi, cl ; rdi << ((63-pos) & 63); same insn as shl (arithmetic == logical left shift)
popcnt rdx, rdi
test rdi, rdi ; sets SF if the high bit is set.
cmovs rax, rdx ; conditional-move on the sign flag
ret
请参阅 How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results? for background on gcc's use of the -x == ~x + 1 two's complement identity. (And ，其中切线提到 shl 屏蔽了移位计数，因此我们只需要 ecx 的低 6 位来保存 63 - pos。主要是 link 是因为我最近写的，任何仍在阅读这一段的人可能会觉得它很有趣。）
其中一些指令在内联时会消失。 （例如，gcc 会首先在 ecx 中生成计数。）
使用 Glenn 的乘法而不是三元运算符 想法（由 USE_mul 启用），gcc 确实
shr rdi, 63
imul eax, edi
在最后而不是 xor / test / cmovs.
Haswell perf analysis, using microarch data from Agner Fog（多版本）：
mov r,r: 1 fused-domain uop, 0 延迟, 无执行单元xor-归零：1fused-domainuop，无执行单元not：p0/p1/p5/p6 1 uop，1c 延迟，每 0.25c 吞吐量 1shl（又名 sal）在 cl 中计数：p0/p6 为 3 微指令：2c 延迟，每 2c 吞吐量 1。 （奇怪的是，Agner Fog 的数据表明 IvyBridge 只需要 2 微指令。）popcnt：p1 1 uop，3c 延迟，每 1c 吞吐量 1shr r,imm：p0/p6 1 uop，1c 延迟。每 0.5c 吞吐量 1 个。imul r,r：p1 为 1uop，延迟为 3c。- 不算
ret
总计：
- 9 fused-domain uops，可以在 2.25 个周期内发出（理论上；uop cache-line 效果通常会稍微阻碍前端）。
- p0/p64 微指令（班次）。 p1 为 2 微指令。 1 any-ALU-port 微指令。可以每 2c 执行一次（使移位端口饱和），因此前端是最严重的瓶颈。
延迟：从位集准备就绪到结果为：shl(2) -> popcnt(3) -> imul(3) 的关键路径。总计 8 个周期 。或者从 pos 准备好时开始的 9c，因为 not 是它的额外 1c 延迟。
最佳bitbroadcast版本将shr替换为sar（相同性能），将imul替换为and（1c 延迟而不是 3c，运行s 在任何端口上）。因此，唯一的性能变化是 将关键路径延迟减少到 6 个周期 。吞吐量仍然是前端的瓶颈。 and 能够在任何端口上 运行 没有什么区别，除非你将它与端口 1 上的瓶颈代码混合在一起（而不是只查看 运行ning 的吞吐量这个 代码在一个紧密的循环中）。
cmov（三元运算符）版本：11 fused-domain uops（前端：每 2.75c 一个）。执行单元：每 2c 一个在移位端口 (p0/p6) 上仍然是瓶颈。 延迟：从 bitset 到结果 7c，从 pos 到结果 8c。 （cmov 是 2c 延迟，p0/p1/p5/p6 中的任何一个都是 2 微指令。）
Clang 有一些不同的技巧：它生成的掩码不是 test/cmovs，而是 all-ones 或all-zeros 通过使用算术 right-shift 将符号位广播到寄存器的所有位置。我喜欢它：使用 and 而不是 cmov 在 Intel 上效率更高。不过，它仍然有 data-dependency 并为分支的两侧工作（这通常是 cmov 的主要缺点）。更新：使用正确的源代码，gcc 也将使用此方法。
clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell
popcount_subset(std::bitset<64ul>, int):
mov ecx, 63
sub ecx, esi ; larger code size, but faster on CPUs without mov-elimination
shl rdi, cl ; rdi << ((63-pos) & 63)
popcnt rax, rdi ; doesn't start a fresh dep chain before this, like gcc does
sar rdi, 63 ; broadcast the sign bit
and eax, edi ; eax = 0 or its previous value
ret
sar / and 替换了 xor / test / cmov，并且 cmov 是 Intel CPUs 上的 2-uop 指令，所以这真的很好。 （对于 ternary-operator 版本）。
当使用多源版本或 "bitbroadcast" 源版本时，Clang 仍然使用 sar / and 技巧而不是实际的 imul。所以那些帮助 gcc 而不会伤害 clang。 （sar/and 肯定比 shr/imul 好：关键路径上的延迟少 2c。）pow_of_two_sub 版本确实伤害了 clang（请参阅第一个 godbolt link：从这个答案中省略以避免因没有成功的想法而混乱）。
mov ecx, 63 / sub ecx, esi 实际上 在 CPU 上 没有 mov-elimination 用于 reg,reg 移动（零延迟和无执行端口，由寄存器重命名处理）。这包括英特尔 pre-IvyBridge，但不包括最近的英特尔和 AMD CPU。
Clang 的 mov imm / sub 方法只将 pos 的一个延迟周期放到关键路径上（超出位集->结果延迟），而不是 pos 的两个延迟周期=92=] / not ecx 在 CPUs 上 mov r,r 有 1c 延迟。
使用 BMI2（Haswell 及更高版本），最佳 ASM 版本可以将 mov 保存到 ecx。其他一切都一样，因为 shlx 将其 shift-count 输入寄存器隐藏到 operand-size，就像 shl 一样。
x86 移位指令具有疯狂的 CISC 语义，如果移位计数为零，则标志不受影响。所以 variable-count 移位指令对标志的旧值具有（潜在的）依赖性。 "Normal" x86 shl r, cl 在 Haswell 上解码为 3 微码，但 BMI2 shlx r, r, r 仅为 1。所以 gcc 仍然使用 -march=haswell 发出 sal 太糟糕了，而不是使用 shlx（它在其他一些情况下确实使用）。
// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
not esi ; The low 6 bits hold 63-pos. gcc's two-s complement trick
xor eax, eax ; break false dependency on Intel. maybe not needed when inlined.
shlx rdi, rdi, rsi ; rdi << ((63-pos) & 63)
popcnt rax, rdi
sar rdi, 63 ; broadcast the sign bit: rdi=0 or -1
and eax, edi ; eax = 0 or its previous value
ret
Intel Haswell 性能分析：6 fused-domain uops（前端：每 1.5c 一个 ）。执行单位：2 p0/p6 shift uops。 1 p1 uop。 2 any-port uops：（总执行端口限制每 1.25c 一个）。关键路径延迟：shlx(1) -> popcnt(3) -> and(1) = 5c bitset->result。 （或来自 pos->result 的 6c）。
请注意，在内联时，人类（或智能编译器）可以避免对 xor eax, eax 的需要。它之所以存在是因为 popcnt's false dependency on the output register (on Intel)，我们需要 eax 中的输出（调用者最近可能使用了一个长的 dep 链）。使用 -mtune=bdver2 或其他东西，gcc 不会将它将用于 popcnt 输出的寄存器清零。
在内联时，我们可以使用至少与 popcnt 的源寄存器一样早准备好的输出寄存器来避免该问题。当稍后不需要源代码时，编译器将执行 in-place popcnt rdi,rdi，但这里不是这种情况。相反，我们可以选择另一个必须在源之前就绪的寄存器。 popcnt 的输入依赖于 63-pos，我们可以破坏它，所以 popcnt rsi,rdi 对 rsi 的依赖不能延迟它。或者如果我们在寄存器中有 63，我们可以 popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi。或者 BMI2 3 操作数移位指令也可以让我们不会破坏输入，以防以后需要它们。
如此 light-weight 循环开销和设置输入操作数/存储结果将成为主要因素。 （并且 63-pos 可以使用 compile-time 常量进行优化，或者优化到变量计数的来源。）
可笑的是，Intel 编译器搬起石头砸自己的脚，没有利用 A[63] 是符号位这一事实。 shl / bt rdi, 63 / jc。它甚至以一种非常愚蠢的方式设置分支。它可以将 eax 置零，然后根据 shl.
设置的符号标志是否跳过 popcnt
最佳分支实现，从 -O3 -march=corei7 在 Godbolt 上的 ICC13 输出开始：
// hand-tuned, not compiler output
mov ecx, esi ; ICC uses neg/add/mov :/
not ecx
xor eax, eax ; breaks the false dep, or is the return value in the taken-branch case
shl rdi, cl
jns .bit_not_set
popcnt rax, rdi
.bit_not_set:
ret
这非常理想：A[pos] == true 案例有一个 not-taken 分支。不过，它并没有比无分支方法节省太多。
如果 A[pos] == false 情况更常见：跳过 ret 指令，跳转到 popcnt / ret。 （或者在内联之后：跳转到执行 popcnt 的末尾的块并跳回）。
给定 std::bitset<64> bits 设置了任意数量的位和一个位位置 X (0-63)
如果 X 处的位未设置，则计算位置 X 或更低位置或 return 0 的最有效方法是什么
注意：如果设置了该位，return 将始终至少为 1
暴力破解的方式很慢：
int countupto(std::bitset<64> bits, int X)
{
if (!bits[X]) return 0;
int total=1;
for (int i=0; i < X; ++i)
{
total+=bits[i];
}
return total;
}
bitset的count()方法会给你所有位的popcount，但是bitset不支持范围
注意：这不是 How to count the number of set bits in a 32-bit integer? 的重复，因为它询问所有不在 0 到 X
范围内的位我的第一反应是测试指定的位，然后立即 return 0 是清楚的。
如果你超过了那个，创建一个位掩码，设置该位（和不太重要的位），并 and 使用原始输入。然后使用 count() 成员函数获取结果中设置的位数。
关于创建蒙版：您可以将 1 左移 N 个位置，然后减去 1。
假设 unsigned long 或 unsigned long long 足够大以容纳 64 位，您可以调用 bits.to_unlong()（或 bits.to_ullong()）以整数形式获取位集数据，屏蔽掉 X ((1 << X) - 1) 以上的位，然后按照您 link 到的问题的答案中给出的那些位进行计数。
在一个位和它下面的位的掩码之间转换很容易，所以像这样的东西应该可以工作：
int popcnt(bitset<64> bs, int x) {
// Early out when bit not set
if (!bs[x]) return 0;
// Otherwise, make mask from `x`, mask and count bits
return (bs & bitset<64>((1UL << x) - 1)).count() + 1;
}
这里的假设是 bitset::count 被有效地实现（使用 popcnt 内在函数或有效的回退）；这不能保证，但 STL 人员倾向于优化这类事情。
我编辑了一个我以前见过的问题，它会检查一个数字中设置的位数是奇数还是偶数。它适用于 C，但将其融入 C++ 应该不会太难。解决方案的关键在于 while 循环中的内容。在纸上尝试一下，了解它如何挑选出 LSB，然后将其从 x 中移除。其余代码很简单。代码在 O(n) 中运行，其中 n 是 x 中设置的位数。这比线性时间要好得多，我也认为只有在第一次看这个问题时才有可能。
#include <stdio.h>
int
count(long x, int pos)
{
/* if bit at location pos is not set, return 0 */
if (!((x >> pos) & 1))
{
return 0;
}
/* prepare x by removing set bits after position pos */
long tmp = x;
tmp = tmp >> (pos + 1);
tmp = tmp << (pos + 1);
x ^= tmp;
/* increment count every time the first set bit of x is removed (from the right) */
int y;
int count = 0;
while (x != 0)
{
y = x & ~(x - 1);
x ^= y;
count++;
}
return count;
}
int
main(void)
{
/* run tests */
long num = 0b1010111;
printf("%d\n", count(num, 0)); /* prints: 1 */
printf("%d\n", count(num, 1)); /* prints: 2 */
printf("%d\n", count(num, 2)); /* prints: 3 */
printf("%d\n", count(num, 3)); /* prints: 0 */
printf("%d\n", count(num, 4)); /* prints: 4 */
printf("%d\n", count(num, 5)); /* prints: 0 */
printf("%d\n", count(num, 6)); /* prints: 5 */
}
此 C++ 让 g++ 发出 very good x86 ASM (godbolt compiler explorer)。我希望它也能在其他 64 位架构上高效编译（如果有 std::bitset::count 的 HW popcount 可以使用，否则那将永远是缓慢的部分；例如确保使用 g++ -march=nehalem 或更高版本，或者-mpopcnt 如果您不想启用任何其他功能，如果您可以将您的代码限制为仅 运行 支持该 x86 指令的 CPUs:
#include <bitset>
int popcount_subset(std::bitset<64> A, int pos) {
int high_bits_to_eliminate = 63 - pos;
A <<= (high_bits_to_eliminate & 63); // puts A[pos] at A[63].
return (A[63]? ~0ULL : 0) & A.count(); // most efficient way: great code with gcc and clang
// see the godbolt link for some #ifdefs with other ways to do the check, like
// return A[BSET_SIZE-1] ? A.count() : 0;
}
这在 32 位架构上可能不是最佳选择，因此如果您需要进行 32 位构建，请比较其他替代方案。
这将适用于其他大小的位集，只要您对 hard-coded 63 做一些事情，并更改 & 63掩码换成更一般的计数range-check。为了在奇怪大小的位集上获得最佳性能，请为目标机器的 size <= register width 创建一个专门化的模板函数。在这种情况下，将 bitset 提取为适当宽度的 unsigned 类型，并移至寄存器的顶部而不是 bitset 的顶部。
您希望这也能为 bitset<32> 生成理想的代码，但事实并非如此。 gcc/clang 在 x86-64 上仍然使用 64 位寄存器。
对于大的位集，移动整个东西比只弹出包含 pos 的单词下面的单词并在那个单词上使用它要慢。 （如果您可以假设 SSSE3 而不是 popcnt insn 硬件支持，或者对于 32 位目标，这就是向量化 popcount 在 x86 上真正闪耀的地方。AVX2 256bit pshufb 是进行批量 popcounts 的最快方法，但是没有 AVX2，我认为 64 位 popcnt 非常接近 128 位 pshufb 实现。更多讨论请参阅评论。）
如果你有一个 64 位元素的数组，并且想分别计算每个元素中特定位置以下的位，那么你绝对应该使用 SIMD。该算法的移位部分矢量化，而不仅仅是 popcnt 部分。在基于 pshufb 的 popcnt 之后，对 all-zero 寄存器使用 horizontal-sum 字节到 64 位块中的 horizontal-sum 字节，该 popcnt 分别为每个字节中的位产生计数。 SSE/AVX 没有 64 位算术右移，但您可以使用不同的技术来混合每个元素的高位。
我是怎么想到这个的：
您希望编译器输出的 asm 指令将：
- 从 64 位值中删除不需要的位
- 测试所需位的最高位。
- popcount it.
- return 0 或 popcount，取决于测试结果。 （无分支或分支实现都有优势。如果分支是可预测的，则无分支实现往往更慢。）
执行 1 的明显方法是生成掩码 ((1<<(pos+1)) -1) 并 & 它。一种更有效的方法是 left-shift 通过 63-pos，将您想要的位打包在寄存器的顶部。
这还有一个有趣的地方side-effect，就是把你要测试的位作为寄存器的最高位。测试符号位，而不是任何其他任意位，需要的指令稍微少一些。算术右移可以将符号位广播到寄存器的其余部分，从而允许 more-efficient-than-usual 无分支代码。
做 popcount 是一个 much-discussed 问题，但实际上是难题中比较棘手的部分。在 x86 上，它有非常有效的硬件支持，但仅限于 recent-enough 硬件。在 Intel CPUs 上，popcnt 指令仅适用于 Nehalem 和更新版本。我忘记了 AMD 何时添加了支持。
所以为了安全地使用它，您需要使用不使用 popcnt 的后备进行 CPU 调度。或者，制作 do/don 不依赖某些 CPU 功能的单独二进制文件。
popcnt 指令的 popcount 可以通过几种方法完成。一个使用 SSSE3 pshufb 来实现一个 4 位 LUT。不过，这在整个阵列上使用时最有效，而不是一次使用单个 64b。标量 bithacks 在这里可能是最好的，并且不需要 SSSE3（因此将与具有 64 位但不是 pshufb 的古老 AMD CPUs 兼容。）
比特广播：
(A[63]? ~0ULL : 0) 要求编译器将高位广播到所有其他位位置，允许它用作 AND-mask 以将 popcount 结果归零（或不归零）。请注意，即使对于大的 bitset 大小，它仍然只屏蔽 popcnt 的输出，而不是 bitset 本身，所以 ~0ULL 没问题我使用 ULL 来确保从未要求编译器广播仅位到寄存器的低 32b（例如 Windows 上的 UL）。
这个广播可以通过算术右移 63 来完成，这会移入高位的副本。
clang 从原始版本生成此代码。在 Glenn 对 4 的不同实现提出一些建议后，我意识到我可以通过编写更像我想要的 ASM 的源代码来引导 gcc 走向 clang 的最佳解决方案。更直接地请求算术右移的明显 ((int64_t)something) >> 63 将不是严格可移植的，因为带符号的 right-shifts 是 implementation-defined as either arithmetic or logical. The standard doesn't provide any portable arithmetic right-shift operator. (It's not undefined behaviour。）无论如何，幸运的是编译器足够聪明：gcc 看到最好的一旦你给了足够的提示。
此源代码使用 gcc 和 clang 在 x86-64 和 ARM64 上生成了很棒的代码。两者都简单地在 popcnt 的输入上使用算术右移（因此移位可以 运行 与 popcnt 并行）。它还在 32 位 x86 上使用 gcc 编译得很好，因为屏蔽只发生在 32 位变量上（在添加多个 popcnt 结果之后）。这是函数的其余部分在 32 位上很糟糕（当位集大于寄存器时）。
带有 gcc 的原始 ternary-operator 版本
使用 gcc 5.3.0 编译 -O3 -march=nehalem -mtune=haswell（较旧的 gcc，如 4.9.2，也仍然会发出此消息）：
; the original ternary-operator version. See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
; input bitset in rdi, input count in esi (SysV ABI)
mov ecx, esi ; x86 variable-count shift requires the count in cl
xor edx, edx ; edx=0
xor eax, eax ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
not ecx ; two's complement bithack for 63-pos (in the low bits of the register)
sal rdi, cl ; rdi << ((63-pos) & 63); same insn as shl (arithmetic == logical left shift)
popcnt rdx, rdi
test rdi, rdi ; sets SF if the high bit is set.
cmovs rax, rdx ; conditional-move on the sign flag
ret
请参阅 How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results? for background on gcc's use of the -x == ~x + 1 two's complement identity. (And shl 屏蔽了移位计数，因此我们只需要 ecx 的低 6 位来保存 63 - pos。主要是 link 是因为我最近写的，任何仍在阅读这一段的人可能会觉得它很有趣。）
其中一些指令在内联时会消失。 （例如，gcc 会首先在 ecx 中生成计数。）
使用 Glenn 的乘法而不是三元运算符 想法（由 USE_mul 启用），gcc 确实
shr rdi, 63
imul eax, edi
在最后而不是 xor / test / cmovs.
Haswell perf analysis, using microarch data from Agner Fog（多版本）：
mov r,r: 1 fused-domain uop, 0 延迟, 无执行单元xor-归零：1fused-domainuop，无执行单元not：p0/p1/p5/p6 1 uop，1c 延迟，每 0.25c 吞吐量 1shl（又名sal）在cl中计数：p0/p6 为 3 微指令：2c 延迟，每 2c 吞吐量 1。 （奇怪的是，Agner Fog 的数据表明 IvyBridge 只需要 2 微指令。）popcnt：p1 1 uop，3c 延迟，每 1c 吞吐量 1shr r,imm：p0/p6 1 uop，1c 延迟。每 0.5c 吞吐量 1 个。imul r,r：p1 为 1uop，延迟为 3c。- 不算
ret
总计：
- 9 fused-domain uops，可以在 2.25 个周期内发出（理论上；uop cache-line 效果通常会稍微阻碍前端）。
- p0/p64 微指令（班次）。 p1 为 2 微指令。 1 any-ALU-port 微指令。可以每 2c 执行一次（使移位端口饱和），因此前端是最严重的瓶颈。
延迟：从位集准备就绪到结果为：shl(2) -> popcnt(3) -> imul(3) 的关键路径。总计 8 个周期 。或者从 pos 准备好时开始的 9c，因为 not 是它的额外 1c 延迟。
最佳bitbroadcast版本将shr替换为sar（相同性能），将imul替换为and（1c 延迟而不是 3c，运行s 在任何端口上）。因此，唯一的性能变化是 将关键路径延迟减少到 6 个周期 。吞吐量仍然是前端的瓶颈。 and 能够在任何端口上 运行 没有什么区别，除非你将它与端口 1 上的瓶颈代码混合在一起（而不是只查看 运行ning 的吞吐量这个 代码在一个紧密的循环中）。
cmov（三元运算符）版本：11 fused-domain uops（前端：每 2.75c 一个）。执行单元：每 2c 一个在移位端口 (p0/p6) 上仍然是瓶颈。 延迟：从 bitset 到结果 7c，从 pos 到结果 8c。 （cmov 是 2c 延迟，p0/p1/p5/p6 中的任何一个都是 2 微指令。）
Clang 有一些不同的技巧：它生成的掩码不是 test/cmovs，而是 all-ones 或all-zeros 通过使用算术 right-shift 将符号位广播到寄存器的所有位置。我喜欢它：使用 and 而不是 cmov 在 Intel 上效率更高。不过，它仍然有 data-dependency 并为分支的两侧工作（这通常是 cmov 的主要缺点）。更新：使用正确的源代码，gcc 也将使用此方法。
clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell
popcount_subset(std::bitset<64ul>, int):
mov ecx, 63
sub ecx, esi ; larger code size, but faster on CPUs without mov-elimination
shl rdi, cl ; rdi << ((63-pos) & 63)
popcnt rax, rdi ; doesn't start a fresh dep chain before this, like gcc does
sar rdi, 63 ; broadcast the sign bit
and eax, edi ; eax = 0 or its previous value
ret
sar / and 替换了 xor / test / cmov，并且 cmov 是 Intel CPUs 上的 2-uop 指令，所以这真的很好。 （对于 ternary-operator 版本）。
当使用多源版本或 "bitbroadcast" 源版本时，Clang 仍然使用 sar / and 技巧而不是实际的 imul。所以那些帮助 gcc 而不会伤害 clang。 （sar/and 肯定比 shr/imul 好：关键路径上的延迟少 2c。）pow_of_two_sub 版本确实伤害了 clang（请参阅第一个 godbolt link：从这个答案中省略以避免因没有成功的想法而混乱）。
mov ecx, 63 / sub ecx, esi 实际上 在 CPU 上 没有 mov-elimination 用于 reg,reg 移动（零延迟和无执行端口，由寄存器重命名处理）。这包括英特尔 pre-IvyBridge，但不包括最近的英特尔和 AMD CPU。
Clang 的 mov imm / sub 方法只将 pos 的一个延迟周期放到关键路径上（超出位集->结果延迟），而不是 pos 的两个延迟周期=92=] / not ecx 在 CPUs 上 mov r,r 有 1c 延迟。
使用 BMI2（Haswell 及更高版本），最佳 ASM 版本可以将 mov 保存到 ecx。其他一切都一样，因为 shlx 将其 shift-count 输入寄存器隐藏到 operand-size，就像 shl 一样。
x86 移位指令具有疯狂的 CISC 语义，如果移位计数为零，则标志不受影响。所以 variable-count 移位指令对标志的旧值具有（潜在的）依赖性。 "Normal" x86 shl r, cl 在 Haswell 上解码为 3 微码，但 BMI2 shlx r, r, r 仅为 1。所以 gcc 仍然使用 -march=haswell 发出 sal 太糟糕了，而不是使用 shlx（它在其他一些情况下确实使用）。
// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
not esi ; The low 6 bits hold 63-pos. gcc's two-s complement trick
xor eax, eax ; break false dependency on Intel. maybe not needed when inlined.
shlx rdi, rdi, rsi ; rdi << ((63-pos) & 63)
popcnt rax, rdi
sar rdi, 63 ; broadcast the sign bit: rdi=0 or -1
and eax, edi ; eax = 0 or its previous value
ret
Intel Haswell 性能分析：6 fused-domain uops（前端：每 1.5c 一个 ）。执行单位：2 p0/p6 shift uops。 1 p1 uop。 2 any-port uops：（总执行端口限制每 1.25c 一个）。关键路径延迟：shlx(1) -> popcnt(3) -> and(1) = 5c bitset->result。 （或来自 pos->result 的 6c）。
请注意，在内联时，人类（或智能编译器）可以避免对 xor eax, eax 的需要。它之所以存在是因为 popcnt's false dependency on the output register (on Intel)，我们需要 eax 中的输出（调用者最近可能使用了一个长的 dep 链）。使用 -mtune=bdver2 或其他东西，gcc 不会将它将用于 popcnt 输出的寄存器清零。
在内联时，我们可以使用至少与 popcnt 的源寄存器一样早准备好的输出寄存器来避免该问题。当稍后不需要源代码时，编译器将执行 in-place popcnt rdi,rdi，但这里不是这种情况。相反，我们可以选择另一个必须在源之前就绪的寄存器。 popcnt 的输入依赖于 63-pos，我们可以破坏它，所以 popcnt rsi,rdi 对 rsi 的依赖不能延迟它。或者如果我们在寄存器中有 63，我们可以 popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi。或者 BMI2 3 操作数移位指令也可以让我们不会破坏输入，以防以后需要它们。
如此 light-weight 循环开销和设置输入操作数/存储结果将成为主要因素。 （并且 63-pos 可以使用 compile-time 常量进行优化，或者优化到变量计数的来源。）
可笑的是，Intel 编译器搬起石头砸自己的脚，没有利用 A[63] 是符号位这一事实。 shl / bt rdi, 63 / jc。它甚至以一种非常愚蠢的方式设置分支。它可以将 eax 置零，然后根据 shl.
最佳分支实现，从 -O3 -march=corei7 在 Godbolt 上的 ICC13 输出开始：
// hand-tuned, not compiler output
mov ecx, esi ; ICC uses neg/add/mov :/
not ecx
xor eax, eax ; breaks the false dep, or is the return value in the taken-branch case
shl rdi, cl
jns .bit_not_set
popcnt rax, rdi
.bit_not_set:
ret
这非常理想：A[pos] == true 案例有一个 not-taken 分支。不过，它并没有比无分支方法节省太多。
如果 A[pos] == false 情况更常见：跳过 ret 指令，跳转到 popcnt / ret。 （或者在内联之后：跳转到执行 popcnt 的末尾的块并跳回）。