什么是在一个位置或更低位置计数设置位的有效方法？
给定std::bitset<64> bits ，设置任意数量的位并将位位置X （0-63）
在X位或更低位计数位的最有效方法是什么，如果X位没有设置则返回0
注意：如果该位被设置，返回将总是至less为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不支持范围
注意：这不是一个重复的如何计算一个32位整数的设置位数？ 因为这要求所有的位不是从0到X的范围
这个C ++得到g ++发出非常好的x86 ASM（godbolt编译器资源pipe理器） 。 我希望它也能在其他64位体系结构上有效地进行编译（如果有一个HW popcount用于std::bitset::count ，否则这将永远是缓慢的部分）：
#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位体系结构的最佳select，所以如果需要构build32位体系结构，请比较其他select。
这将适用于其他大小的bitset ，只要你做了一些关于硬编码的63 ，并将shift_count的& 63掩码更改为更一般的范围检查。 要获得具有奇怪大小位集的最佳性能，请为目标机器的size <= register width一个专门化的模板函数。 在这种情况下，将位集合提取为适当宽度的unsignedtypes，然后移至寄存器的顶部而不是位集的顶部。
你会期望这也为bitset<32>生成理想的代码，但它不完全。 gcc / clang仍然使用x86-64上的64位寄存器。
对于大的位组，移动整个事物将比在包含pos下面的单词更加慢，并且在该单词上使用它。 （这是一个向量化的popcount，如果你可以假设SSSE3，而不是支持popcnt硬件，或者是32位的目标，那么这个向量化的popcount真的会在x86上出现popcnt 256bit pshufb是批量popup窗口的最快方法，但是如果没有AVX2，我认为64bit popcnt很漂亮接近128位的pshufb实现。查看更多讨论的评论。）
如果你有一个64位元素的数组，并且要分别计算每个元素中特定位置的位数，那么你一定要使用SIMD 。 这个algorithm的偏移部分不仅仅是popcnt部分。 在一个基于pshufb的popcnt之后，对全零寄存器使用psadbw以64位块为单位对字节进行水平求和，从而分别为每个字节的位生成计数。 SSE / AVX没有64位算术右移，但可以使用不同的技术来混合每个元素的高位。
我是怎么想出来的：
你想让编译器输出的asm指令将会：
- 从64位值中删除不需要的位
- testing想要的比特的最高位。
- popup它。
- 返回0或者popcount，这取决于testing的结果。 （无分支或分支实现都有优势，如果分支是可预测的，无分支实现往往会变慢）。
做1的显而易见的方法是生成一个掩码（ (1<<(pos+1)) -1 ）和& it。 更有效的方法是左移63-pos位，将想要打包的位留在寄存器的顶部。
这也有一个有趣的副作用，把你想testing的位作为最高位。 testing符号位，而不是任何其他任意位，只需要稍微less一点的指令。 算术右移可以将符号位广播到寄存器的其余部分，从而实现更高效的通常无分支代码。
做这个问题是一个非常讨论的问题，但实际上这是难题的一个棘手的部分。 在x86上，它有非常高效的硬件支持，但是只有在最新的硬件上。 在Intel CPU上， popcnt指令只在Nehalem和更新版本上可用。 当AMDjoin支持时我忘记了。
因此要安全地使用它，您需要使用不使用popcnt的后备进行CPU调度。 或者，制作单独的二进制文件，这些二进制文件不依赖某些CPUfunction。
没有popcnt指令的popcnt可以通过几种方法来完成。 一个使用SSSE3 pshufb来实现一个4位LUT。 但是，在整个arrays上使用时，这是最有效的，而不是一次一个64b。 标量bithacks在这里可能是最好的，不需要SSSE3（所以可以兼容具有64位而不是pshufb的古代AMD CPU）。
Bitbroadcast：
(A[63]? ~0ULL : 0)要求编译器将高位广播到所有其他位的位置，允许它被用作AND掩码来使得（或不）该结果的结果为零。 请注意，即使对于大的bitset大小，它仍然只掩盖popcnt的输出，而不是bitset本身，所以~0ULL是好的我用ULL来确保没有要求编译器只播放该位的低32b一个寄存器（例如在Windows上有UL ）。
这个广播可以用一个63位的算术右移来完成，它移动高位的副本。
铿锵从原始版本生成此代码。 经过Glenn的一些关于4的不同实现的刺激后，我意识到我可以通过写更多的源代码来引导gcc走向clang的最佳解决scheme。 显而易见的((int64_t)something) >> 63更直接的请求一个算术右移将不会被严格的移植，因为有符号的右移是实现定义为算术或逻辑 。 该标准不提供任何便携式算术右移运算符。 （尽pipe这并不是未定义的行为 。）无论如何，幸运的是编译器足够聪明：一旦你给了足够的提示，gcc就会看到最好的方法。
这个源代码在x86-64和ARM64上使用gcc和clang编码。 两者都只是在input上使用一个算术右移来popup（所以这个移位可以和popcnt并行运行）。 它也用gcc编译32位x86，因为掩码只发生在一个32位variables（添加多个popup结果之后）。 这是在32位上讨厌的function的其余部分（当比特大于寄存器时）。
原始的三元操作符版本与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
请参阅如何certificateC语句-x，〜x + 1和〜（x-1）产生相同的结果？ 对于gcc使用-x == ~x + 1二进制补码标识的背景。 （和哪个2的补码整数运算可以不使input中的高位为零，如果只有结果的低部分是需要的 ，哪个正切地提到shl掩盖了移位计数，所以我们只需要低6位的ecx持有63 - pos 。大多数连接，因为我最近写了，任何人仍然阅读本段可能会发现它有趣。）
其中一些指令将在内联时消失。 （例如，gcc会首先在ecx中生成计数。）
随着格伦的乘法，而不是三元运算符的想法（由USE_mul启用）， USE_mul
shr rdi, 63 imul eax, edi
最后而不是xor / test / cmovs 。
Haswell性能分析，使用来自Agner Fog （Multiply版本）的微数据 ：
-
mov r,r：1个融合域uop，0个延迟，没有执行单元 -
xor-zeroing：1个融合域uop，没有执行单元 -
not：1 pop / p1 / p5 / p6，1c延迟，每0.25c吞吐量1 -
shl（又称sal），计数为cl：3 uops，p0 / p6：2c等待时间，每2c吞吐量1。 （Agner Fog的数据表明，IvyBridge奇怪地只用了2次。 -
popcnt：1用于popcnt等待时间，每1c吞吐量1 -
shr r,imm：1用于p0 / p6,1c延迟。 每0.5c吞吐量1个。 -
imul r,r：1uop为p1,3c等待时间。 - 不包括
ret
总计：
- 9个融合域uop，可以在2.25个周期内发布 （理论上，uop cache-line效应通常会稍微瓶颈前端）。
- 4个uops（移位）为p0 / p6。 2个p1。 1个任意ALU端口用户。 可以每2c执行一次（使移位端口饱和），所以前端是最糟糕的瓶颈。
延迟：从bitset准备好到结果popcnt关键path： shl （2） – > popcnt （3） – > imul （3）。 共8个周期 。 或者当pos准备就绪时，因为not额外的1c延迟。
最佳的bitbroadcast版本用sar （相同的perf）代替shr ，并且and （1c延迟代替3c，运行在任何端口上）。 所以唯一的改变就是将关键path延迟减less到6个周期 。 吞吐量仍然是瓶颈在前端。 and能够在任何端口上运行都没有什么不同，除非你将这个代码与port1上的瓶颈混合在一起（而不是在紧密的循环中查看吞吐量来运行这个代码）。
cmov（三元运算符）版本 ：11个融合域uops （前端： 每2.75c一个 ）。 执行单元：仍然瓶颈在移位端口（p0 / p6）每2c一个。 延迟 ：从bitset到结果7c，从pos到结果8c。 （ cmov是2c的延迟，对于p0 / p1 / p5 / p6中的任何一个，是2个）。
Clang有一些不同的技巧：不是test / cmovs ，它通过使用算术右移将符号位广播到寄存器的所有位置来生成全1或全零的掩码。 我喜欢它：在英特尔上使用and不是cmov更有效率。 它仍然具有数据依赖性，并且为分支双方（这是总体上cmov的主要缺点）做了工作。 更新：使用正确的源代码，gcc也将使用此方法。
铛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 / andreplacexor / test / cmov ， cmov是Intel CPU上的2-uop指令，所以非常好。 （对于三元操作符版本）。
当使用多源版本或“bitbroadcast”源版本时，Clang仍然使用sar / and trick来代替实际的imul 。 所以那些帮助gcc没有伤害叮当声。 （ sar/and肯定比shr/imul更好：2c关键path上的延迟更less） pow_of_two_sub版本确实伤害了clang（请参阅第一个godbolt链接：从这个答案中省略，以避免混淆没有泛过的想法） 。
mov ecx, 63 / sub ecx, esi对于reg，reg移动（零延迟和没有执行端口，由寄存器重命名处理）没有mov-elimination，CPU实际上更快 。 这包括Intel pre-IvyBridge，但不包括最近的Intel和AMD CPU。
Clang的mov imm / sub方法只在pos关键path（超出bitset-> result latency）上放置一个pos延迟周期，而不是两个mov ecx, esi / not ecx ，其中mov r,r有1c延迟。
使用BMI2 （Haswell和更高版本），最佳的ASM版本可以将mov保存到ecx 。 其他的工作原理是一样的，因为shlx它的移位计数input寄存器屏蔽到操作数大小，就像shl一样。
x86移位指令具有疯狂的CISC语义，如果移位计数为零，则标志不受影响。 因此，可变计数移位指令对标志的旧值具有（潜在的）依赖性。 “正常”的x86 shl r, cl在Haswell上解码为3个uops，但是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
英特尔Haswell的Perf分析：6个融合域微软 （ 前端：每1.5c一个 ）。 执行单位：2个p0 / p6移位微分。 1 p1 uop。 2个任意端口的uops :(从总执行端口限制中每1.25c一个）。 关键path延迟： shlx （1） – > popcnt （3） – > and （1）= 5c bitset-> result。 （或6c从pos – >结果）。
请注意，内联时，人类（或智能编译器）可以避免使用xor eax, eax 。 这只是因为popcnt对输出寄存器（在Intel上）的错误依赖 ，并且我们需要eax的输出（调用者最近可能使用这个输出来处理长链）。 使用-mtune=bdver2或其他东西，gcc不会将它将用于popcnt输出的寄存器popcnt 。
popcnt联时，我们可以使用一个输出寄存器，至less在popcnt的源registry中已经准备就绪，以避免这个问题。 以后不需要源时popcnt rdi,rdi编译器会执行一个就地的popcnt rdi,rdi ，但这不是这种情况。 相反，我们可以select另一个已经准备就绪的寄存器。 popcnt的input取决于63-pos ，我们可以把它popcnt rsi,rdi ，所以popcnt rsi,rdi对rsi的依赖不能延迟它。 或者如果我们有一个registry中的63 ，我们可以popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi 。 或者BMI2 3操作数转换指令也可以让我们不会在以后需要的情况下重复input。
这是轻量级的，循环开销和设置input操作数/存储结果将是主要因素。 （ 63-pos可以用一个编译时间常量来优化，或者到一个variables来自哪里。
英特尔编译器在脚下自娱自乐，并没有利用A [63]是符号位的事实。 shl / bt rdi, 63 / jc 。 它甚至以非常愚蠢的方式设置分支。 它可以将eax清零，然后根据shl设置的符号标志跳过popcnt或不跳过。
一个最佳的分支实现 ，从IC3的输出-O3 -march=corei7 on godbolt：
// 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 case有一个未被采取的分支。 尽pipe如此，它并没有在无分支方法上节省很多。
如果A[pos] == false情况比较普遍：跳过一个ret指令，到一个popcnt / ret 。 （或者popcnt联之后：跳转到结束时执行popcnt和跳回的块）。
我的直接反应是testing指定的位，并立即返回0清楚。
如果你通过这个，创build一个位掩码（那些不重要的）和原始input。 然后使用count()成员函数来获取结果中设置的位数。
至于创build掩码：可以将1个左移N个位置，然后减1。
假设一个unsigned long或unsigned long long长度足够容纳64位，你可以调用bits.to_unlong() （或bits.to_ullong() ）来获取位集数据作为一个整数，屏蔽X（ (1 << X) - 1 ）然后将这些位计算在您链接到的问题的答案中。
在一个位和一个掩码之间进行转换很容易，所以像这样的东西应该工作：
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 ++。 解决scheme的关键在于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 */ }
