在一个位置或更低的位置上计数集位的有效方法是什么?< / h1 >

给定std::bitset<64> bits的任意位数和位位置X(0-63)

对位置X或以下的位进行计数的最有效方法是什么?如果X处的位没有设置，则返回0。

注意:如果设置了该位，返回值总是至少为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编译器资源管理器)。我希望它也能在其他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位构建，请比较其他替代方案。

这将适用于其他大小的bitset只要您对硬编码的63s做一些事情，并将移位计数的& 63掩码更改为更通用的范围检查。对于大小奇怪的bitset，为了获得最佳性能，可以为目标机器的size <= register width创建一个专门化的模板函数。在这种情况下，将bitset提取为具有适当宽度的unsigned类型，并移到寄存器的顶部而不是bitset的顶部。

您希望这也为bitset<32>生成理想的代码，但它并不完全如此。Gcc/clang在x86-64上仍然使用64位寄存器。

对于大的比特集，移动整个东西将比仅仅弹出包含pos的单词下面的单词，并在那个单词上使用这个更慢。(这是矢量化popcount在x86上真正发挥作用的地方，如果您可以假设SSSE3而不是popcnt的硬件支持，或者对于32位目标。AVX2 256bitpshufb是进行批量popcount的最快方式，但没有AVX2，我认为64位popcnt非常接近128位pshufb的实现。查看注释获得更多讨论)

如果您有一个64位元素的数组，并且希望分别计数每个元素中特定位置以下的位，那么您绝对应该使用SIMD．这个算法的移位部分是矢量化的，而不仅仅是流行部分。对一个全零寄存器使用psadbw，在一个基于pshufb的popcnt之后，在64位块中水平求和字节，该popcnt分别产生每个字节中的位计数。SSE/AVX没有64位算术右移，但您可以使用不同的技术来混合每个元素的高位。

我是怎么想到这个的:

你想让编译器输出的asm指令如下:

从64位值中删除不需要的位
测试所需位的最高位。
popcount。
根据测试结果返回0或popcount。(无分支或分支实现都有各自的优势。如果分支是可预测的，那么无分支的实现往往会更慢。

1是生成掩码((1<<(pos+1)) -1)和&它。一种更有效的方法是通过63-pos左移，将想要打包的位留在寄存器的顶部。

这也有一个有趣的副作用，把你想要测试的位作为寄存器的顶部位。测试符号位，而不是其他任意位，需要的指令要少一些。算术右移可以将符号位广播到寄存器的其余部分，从而允许比通常的无分支代码更高效。

做popcount是一个被广泛讨论的问题，但实际上是这个谜题中更棘手的部分。在x86上，它有非常高效的硬件支持，但仅限于最新的硬件。在Intel cpu上，popcnt指令仅在Nehalem和更新版本上可用。我忘了AMD是什么时候加入支持的

因此，为了安全地使用它，您需要使用不使用popcnt的回退来执行CPU调度。或者，制作单独的二进制文件，这些文件不依赖于某些CPU特性。

没有popcnt

指令的popcount可以通过几种方式实现。一种是使用SSSE3pshufb实现4位LUT。但是，当在整个数组上使用时，而不是一次使用单个64b时，这是最有效的。标量二进制可能是最好的，并且不需要SSSE3(因此可以与具有64位但不具有pshufb的老式AMD cpu兼容)。

Bitbroadcast:

(A[63]? ~0ULL : 0)要求编译器将高位广播到所有其他位，允许它被用作零(或不)popcount结果的与掩码。请注意，即使对于较大的bitset大小，它仍然只屏蔽popcnt的输出，而不是bitset本身，所以~0ULL是好的，我使用ULL来确保没有要求编译器将比特广播到寄存器的低32b(例如，在Windows上使用UL)。

这个广播可以通过算术右移63来完成，这将在高位的拷贝中移位。

clang从原始版本生成此代码。在Glenn对4的不同实现进行了一些催促之后，我意识到我可以把源代码写得更像我想要的ASM，从而使gcc朝着clang的最佳解决方案发展。明显的((int64_t)something) >> 63(更直接地请求算术右移)并不严格可移植，因为带符号的右移是在实现上定义为算术或逻辑的。该标准不提供任何可移植的算术右移运算符。(不过，这不是未定义行为。)无论如何，幸运的是编译器足够聪明:一旦你给它足够的提示，gcc就会看到最好的方法。

这个源代码在x86-64和ARM64上使用gcc和clang编写了很好的代码。两者都只是在popcnt的输入上使用算术右移(因此移位可以与popcnt并行运行)。它在使用gcc的32位x86上也可以很好地编译，因为屏蔽只发生在32位变量上(在添加多个popnt结果之后)。在32位(当bitset大于寄存器时)是函数的其余部分令人讨厌。

使用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

参见如何证明C语句-x， ~x+1和~(x-1)产生相同的结果?有关gcc使用-x == ~x + 1二补标识的背景信息。(如果只需要结果的低部分，那么哪一个2's补整数操作可以在不将输入中的高位归零的情况下使用?它间接提到shl掩盖了移位计数，所以我们只需要ecx的低6位来容纳63 - pos。主要是把它链接起来，因为我是最近写的，如果有人还在读这段话，可能会觉得很有趣。

其中一些指令将在内联时消失。(例如GCC首先会在ecx中生成计数)

用Glenn乘法代替三元运算符(由USE_mul启用)，gcc做

shr     rdi, 63
imul    eax, edi

以代替xor/test/cmovs。

Haswell性能分析，使用Agner Fog (Multiply版本)的微拱数据:

mov r,r: 1融合域up, 0延迟，无执行单元
xor-归零:1融合域up，无执行单元
not: 1 up for p0/p1/p5/p6, 1c latency, 1/0.25c throughput
shl(又名sal)在cl中计数:3 up for p0/p6: 2c延迟，1/2c吞吐量。(Agner Fog的数据表明，IvyBridge只需要2升，奇怪的是。)
popcnt: 1 up for p1, 3c时延，1/1c吞吐量
shr r,imm: 1 up for p0/p6, 1c latency。
imul r,r: 1uop for p1, 3c latency.
不包括ret

总数:

9个融合域up，可以在2.25个周期内发出(理论上;
4 up (shift) for p0/p6。2个向上的p1。1任意alu端口上。可以在每2c执行一个(饱和移位端口)，所以前端是最糟糕的瓶颈。

Latency:从bitset就绪到结果为:shl(2) ->popcnt(3) ->imul(3)的关键路径。Total8 cycles．或者从pos准备好开始延迟9c，因为not对它来说是额外的1c延迟。

最优bitbroadcast版本将shr替换为sar(相同的性能)，将imul替换为and(1c延迟而不是3c，在任何端口上运行)。所以唯一的perf变化是将关键路径延迟减少到6个周期．前端的吞吐量仍然是瓶颈。and能够在任何端口上运行并没有什么区别，除非您将其与port1上的瓶颈代码混合在一起(而不是在紧密循环中查看仅运行此代码的吞吐量)。

cmov(三元操作符)version: 11个融合域uops(前端:每2.75c一个))。执行单元:在移位端口(p0/p6)上仍然存在瓶颈，每2c有一个延迟:从bitset到result 7c，从pos到result 8c。(cmov为2c延迟，p0/p1/p5/p6中的任何一个为2 up .)

叮当声有一些不同的技巧:与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上是一条二层指令，所以这真的很好。(对于三元操作符版本)。

Clang在使用多重源版本或"比特广播"源版本时仍然使用sar / and技巧而不是实际的imul。所以这些帮助了gcc而不伤害了clang。(sar/and肯定比shr/imul好:关键路径上的延迟减少了2c。)pow_of_two_sub版本确实伤害了clang(见第一个godbolt链接:省略了这个答案，以避免没有成功的想法混乱)。

mov ecx, 63/sub ecx, esi实际上是更快在cpu上没有移动消除reg,reg移动(零延迟和无执行端口，通过寄存器重命名处理)。这包括英特尔之前的ivybridge，但不包括最新的英特尔和AMD cpu。

Clang的mov imm/sub方法只将pos的一个周期延迟放到关键路径上(超出bitset->result延迟)，而在mov r,r具有1c延迟的cpu上，mov ecx, esi/not ecx的两个周期延迟。

与BMI2(Haswell和以后的版本)，一个最佳的ASM版本可以保存mov到ecx。其他一切都是一样的，因为shlx将其移位计数输入寄存器隐藏到操作数大小，就像shl一样。

x86移位指令具有疯狂的CISC语义，如果移位计数为零，则标志不受影响。因此，可变计数移位指令(潜在地)依赖于标志的旧值。"正常"x86shl r, cl在Haswell上解码为3 op，但BMI2shlx r, r, r只有1 op。因此，gcc仍然在使用-march=haswell的同时发布sal，而不是使用shlx(它在其他一些情况下确实使用CC_94)，这太糟糕了。

// 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个融合域uops (前端:每1.5c一个))。执行单位:2个p0/p6档。1 p1向上。2个任意端口上限:(从总执行端口限制中每1.25c一个)。关键路径延迟:shlx(1) ->popcnt(3) ->and(1) = 5c bitset->result。(或6c frompos->result).

注意，当内联时，人工(或智能编译器)可以避免需要xor eax, eax。它的存在只是因为popcnt对输出寄存器的错误依赖(在Intel上)，并且我们需要eax中的输出(调用者最近可能已经使用了长深度链)。对于-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]是符号位这一事实。Cc_114/bt rdi, 63/jc。它甚至以一种非常愚蠢的方式设置分支。它可以将ax归零，然后根据shl设置的符号标志跳过popcnt或不跳过popcnt。

最优分支实现

从-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并跳转回的块)。

我的第一反应是测试指定的位，并立即返回0。

如果您通过了，则创建一个位掩码，设置该位(和不太重要的位)，并使用原始输入创建and。然后使用count()成员函数获取结果中设置的位的计数。

对于创建蒙版:你可以向左移动N个位置，然后减去1。

假设unsigned long或unsigned long long足够大，可以容纳64位，您可以调用bits.to_unlong()(或bits.to_ullong())以获取bitset数据作为整数，屏蔽掉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是有效实现的(使用popcntintrinsic或有效的回退);这不能保证，但是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("%dn", count(num, 0)); /* prints: 1 */
printf("%dn", count(num, 1)); /* prints: 2 */
printf("%dn", count(num, 2)); /* prints: 3 */
printf("%dn", count(num, 3)); /* prints: 0 */
printf("%dn", count(num, 4)); /* prints: 4 */
printf("%dn", count(num, 5)); /* prints: 0 */
printf("%dn", count(num, 6)); /* prints: 5 */
}

我是怎么想到这个的:

Bitbroadcast:

Haswell性能分析，使用Agner Fog (Multiply版本)的微拱数据:

相关内容

最新更新

热门标签：