在给定std::bitset<64> bits的情况下设置了任意数量的位，并且设置了位位置X(0-63)
最有效的方法是对X或更低位置的位数进行计数，或者如果未设置X的位，则返回0是最有效的方法
注意:如果该位置1，则返回值始终至少为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;
}
count()的bitset methof将为您提供所有位的popcount，但bitset不支持范围注意:这不是How to count the number of set bits in a 32-bit integer?的副本，因为它询问所有位，而不是0到X的范围
最佳答案
此C++使g++发出very good x86 ASM (godbolt compiler explorer)。我希望它也可以在其他64位体系结构上有效地进行编译(如果有供std::bitset::count使用的HW popcount，否则它将始终很慢；例如，请确保使用g++ -march=nehalem或更高版本，或者如果您不想使用-mpopcnt如果可以将代码限制为仅在支持该x86指令的CPU上运行，请启用其他功能):
#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位构建，请比较其他替代方案。
，这将适用于其他大小的位集，只要您对硬编码的
63做一些处理，并将移位计数的& 63掩码更改为更常规的范围检查。为了获得奇特大小的位集的最佳性能，请对目标计算机的size <= register width进行专门化的模板功能。在这种情况下，将位集提取为适当宽度的unsigned类型，然后移至寄存器的顶部而不是位集的顶部。您可能希望这也会为
bitset<32>生成理想的代码，但事实并非如此。 gcc/clang仍在x86-64上使用64位寄存器。对于大的位集，将整个对象移位要比仅对包含
pos的单词下面的单词进行弹出计数并在该单词上使用该单词慢。 (如果您可以假设SSSE3而不是popcnt insn硬件支持或针对32位目标，则这是矢量化popcount真正在x86上的亮点。AVX2256位pshufb是执行批量popcount的最快方法，但是如果没有AVX2，我认为64位popcnt很漂亮接近于128位pshufb实现。有关更多讨论，请参见评论。)如果您具有64位元素的数组，并且想要分别计算每个位置中某个位置以下的位，那么您绝对应该使用SIMD 。该算法的移位部分是矢量化的，而不仅仅是popcnt部分。对全零寄存器使用
psadbw，以在基于pshufb的popcnt单独生成每个字节的位数之后，对64位块中的水平和字节进行水平求和。 SSE/AVX没有64位算术右移，但是您可以使用另一种技术来混合每个元素的高位。我是怎么想到的:
您要使编译器输出的asm指令将:
进行的明显方法1 是生成一个掩码(
(1<<(pos+1)) -1)并对其进行&。一种更有效的方法是通过63-pos左移，将要打包的位保留在寄存器的顶部。将您要测试的位放在寄存器的最高位还有一个有趣的副作用。测试符号位，而不是任何其他任意位，只需较少的指令。算术右移可以将符号位广播到寄存器的其余部分，从而实现比平时更高效的无分支代码。
进行 popcount 是一个广为讨论的问题，但实际上是难题的棘手部分。在x86上，它具有非常有效的硬件支持，但仅在最近使用的硬件上才如此。在Intel CPU上，
popcnt指令仅在Nehalem及更高版本上可用。我忘了AMD增加支持的时间。因此，为了安全地使用它，您需要使用不使用
popcnt的后备资源来进行CPU调度。或者，制作独立的/不依赖于某些CPU功能的二进制文件。没有
popcnt指令的popcount可以通过几种方法来完成。一个使用SSSE3 pshufb来实现4位LUT。当在整个阵列上使用时，这是最有效的，而不是一次使用单个64b。标量bithack可能是这里最好的，并且不需要SSSE3(因此可以与具有64位但不包含pshufb的古老AMD CPU兼容)。比特广播:
(A[63]? ~0ULL : 0)要求编译器将高位广播到所有其他位位置，以便将其用作AND掩码，以将popcount结果归零(或不归零)。请注意，即使对于较大的位集大小，它仍然仅掩盖了popcnt的输出，而不是位集本身，因此~0ULL很好，我使用ULL来确保不再要求编译器仅将该位广播到ab的低32b。注册(例如，在Windows上使用UL)。可以通过算术右移63来完成此广播，算术右移高位副本。
clang从原始版本生成了此代码。在Glenn对 4 的不同实现提出了一些建议之后，我意识到我可以通过编写更像我想要的ASM的源代码来使gcc转向clang的最佳解决方案。显然，更直接要求算术右移的
((int64_t)something) >> 63并不是严格可移植的，因为带符号的右移是implementation-defined as either arithmetic or logical。该标准未提供任何可移植的算术右移运算符。 (不过，它不是undefined behaviour。)幸运的是，编译器足够聪明:一旦给了足够的提示，gcc就会找到最佳方法。此源代码使用gcc和clang在x86-64和ARM64上编写了出色的代码。两者都只是对popcnt的输入使用算术右移(因此，该移位可以与popcnt并行运行)。它也可以在带有gcc的32位x86上很好地编译，因为屏蔽仅发生在32位变量上(添加了多个popcnt结果之后)。该函数的其余部分在32位(当位集大于寄存器时)令人讨厌。
带有gcc的原始三元运算符
用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
有关gcc使用
-x == ~x + 1 2的补码身份的背景信息，请参见How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?。 (并且Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted?切线地提到shl掩盖了移位计数，因此我们只需要ecx的低6位来保存63 - pos。主要是因为我最近写了它，而且仍然在阅读此段落的任何人都可能觉得它有趣。)在内联时，其中一些指示将消失。 (例如，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个融合域uop，0个延迟，无执行单元xor -zeroing:1个融合域uop，无执行单元not:p0/p1/p5/p6 1 uop，1c延迟，每0.25c吞吐量1个shl(又名sal)，其中cl计数:p0/p6为3 uops:2c延迟，每2c吞吐量1。 (奇怪的是，Agner Fog的数据表明IvyBridge仅需2 oups。)popcnt:1 uop for p1，3c延迟，每1c吞吐量1 shr r,imm:p0/p6为1 uop，延迟为1c。每0.5c吞吐量1个。 imul r,r:p1为1uop，延迟为3c。 ret 总计:
延迟:从准备好位集到获得结果的关键路径:
shl(2)-> popcnt(3)-> imul(3)。总共 8个周期。或准备好pos时的9c，因为not为其额外的1c延迟。最佳
bitbroadcast的版本将shr替换为sar(相同的性能)，并使用imul替换and(延迟为1c，而不是3c，可在任何端口上运行)。因此，唯一的性能变化是，将关键路径延迟减少到6个周期。吞吐量仍然是前端的瓶颈。能够在任何端口上运行的and没什么区别，除非您将其与端口1上出现瓶颈的代码混合在一起(而不是在紧密循环中查看仅运行此代码的吞吐量)。cmov(三元运算符)版本:11个融合域uops(前端:，每2.75c 一次)。执行单位:仍然在转换端口(p0/p6)上每2c出现瓶颈。 延迟:从位集到结果为7c，从位置到结果为8c。 (
cmov是2c延迟，对于p0/p1/p5/p6中的任何一个都是2微秒。)Clang 有一些不同的技巧:代替
test/cmovs，它使用算术右移将符号位广播到寄存器的所有位置，从而生成全1或全0的掩码。我喜欢它:在英特尔上，使用and代替cmov更有效。但是，它仍然具有数据依赖性，并且可以在分支的两侧进行工作(这通常是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 CPU上的2 uop指令，因此非常好。 (对于三元运算符版本)。当使用乘法源版本或“bitbroadcast”源版本时，Clang仍会执行
sar / and技巧而不是实际的imul。因此，这些帮助gcc不会损害clang。 (sar/and绝对比shr/imul更好:在关键路径上的延迟减少了2c。)pow_of_two_sub版本确实伤害了clang(请参阅第一个“godbolt”链接:此答案中省略了它，以避免困惑的想法没有被提出)。实际上，在没有reg，reg移动(零延迟和无执行端口，通过寄存器重命名处理)消除运动的CPU上，
mov ecx, 63/sub ecx, esi实际上更快。这包括Intel之前的IvyBridge，但不包括更新的Intel和AMD CPU。Clang的
mov imm/sub方法仅将pos的延迟周期放到关键路径上(除了bitset-> result延迟之外)，而不是在mov ecx, esi具有1c延迟的CPU上将not ecx/mov r,r延迟两个周期。使用BMI2 (Haswell及更高版本)，最佳的ASM版本可以将
mov保存为ecx。其他所有功能都一样，因为shlx将其移位计数输入寄存器屏蔽为操作数大小，就像shl一样。x86移位指令具有疯狂的CISC语义，其中，如果移位计数为零，则标志不会受到影响。因此，可变计数移位指令对标志的旧值具有(潜在)依赖性。在Haswell上，“普通” x86
shl r, cl解码为3 oups，但是BMI2 shlx r, r, r只有1。因此，非常糟糕的是gcc仍然使用sal而不是-march=haswell发出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
英特尔Haswell性能分析:6个融合域uops(前端:每1.5c 之一)。执行单位:2 p0/p6移位单位。 1 p1哎呀。 2个任意端口oups :(从总执行端口限制中每1.25c发送一个)。关键路径延迟:
shlx(1)-> popcnt(3)-> and(1)= 5c位集->结果。 (或pos-> result中的6c)。请注意，在内联时，人工(或智能编译器)可以避免需要
xor eax, eax。仅因为 popcnt 's false dependency on the output register (on Intel)而存在，并且我们需要eax的输出(调用者最近可能在较长的dep链上使用了该输出)。使用-mtune=bdver2或其他东西，gcc不会将要用于popcnt输出的寄存器清零。进行内联时，我们可以使用至少必须早于
popcnt的源寄存器就已经准备就绪的输出寄存器，以避免出现此问题。当以后不需要源代码时，编译器将执行就地popcnt rdi,rdi，但这不是这种情况。相反，我们可以选择另一个在源之前已经准备好的寄存器。 popcnt的输入取决于63-pos，我们可以破坏它，因此popcnt rsi,rdi的对rsi的依赖关系不会延迟它。或者，如果我们在寄存器中包含63，则可以popcnt rsi,rdi/sarx rax, rsi, reg_63/and eax, esi。否则，BMI2 3操作数转换指令也不会让我们在以后需要输入时费心。如此轻巧，以至于循环开销和设置输入操作数/存储结果将成为主要因素。 (并且
63-pos可以使用编译时常量进行优化，也可以优化到变量计数来自何处。)英特尔编译器很有趣，没有充分利用A [63]是符号位这一事实。
shl/bt rdi, 63/jc。它甚至以非常愚蠢的方式建立分支机构。它可以将eax设为零，然后根据shl设置的符号标志跳过popcnt或不跳过。最佳分支实现，从Godbolt上
-O3 -march=corei7的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案例有一个未采用的分支。但是，与无分支方法相比，它并没有节省太多。如果
A[pos] == false情况更常见:跳过ret指令，转到popcnt/ret。 (或内联之后:跳转到执行popcnt的末尾的一个块并跳回)。