algorithm - 通用位计数

我知道这是一个很好的整数位数计算方法吗：

CountBits(n)
    count = 0
    while n > 0
        n ← n & (n - 1)
        count ← count + 1

有没有一个类似的优雅的解决方案来计算有多少不重叠的k位组是非零的。我现在有：

CountGroups(n, k)
    count = 0
    mask = (2 << k) - 1
    while n > 0
        if n & mask ≠ 0
            count ← count + 1
        n >> k

在最左边组的位置是线性的在后一种算法中，如果只设置了第一组和最后一组，则必须访问并检查中间的所有组，而前者只执行两个操作。这不是瓶颈什么的，只是好奇有没有更好的方法。

最佳答案

一个人可以通过把字分成奇偶序列来并行计算k个集合位的组。如果且仅当组中的所有位都已设置，则向每个组中添加一个时，将携带到下一个空位置（标记为…）。
最初的问题是任何位都是在一个组中设置的，但这可以通过补n、加1和补结果来转换。（现在，当且仅当原始组全部为零时，结果==1。）

 // ...xxx...xxx...xxx   even sequence
 // yyy...yyy...yyy...   odd sequence

 uint64_t a = ~n & even_mask;         // inverse of n
 uint64_t b = (~n >> k) & even_mask;  // inverse of n
 a += 0010101;  // this is octal, where a "one" is added to each group
 b += 0010101;  // same for odd sequence

 //  a = 001xxx000yyy001xxx  -- e.g. first and last group were all ones
 //  b = 000yyy000yyy001yyy  -- e.g. last group of 'y' was all one

 a &= ~even_mask;   // remove the xxx yyy parts, leaving only carry
 b &= ~even_mask;
 a |= (b << 1);
 return bitcount(a ^ 03030303);   // return total number of carry bits

位计数可以并行进行，如果可用，可以使用特殊指令（\uu popcount）或使用Kerningham Richie方法（n&（n-1））进行，如前所述。
这只说明k==3，但可以扩展到任意k，即使当k增大时利息回报率减小。
根据k，可能有更好的算法来为条件导出布尔表达式。
在这种情况下，每组的条件是n（i）| n（i+1）|n（i+k-1），可以并行计算和/或使用折叠技术，当k是2的幂时，这一技术尤其强大

//  n = aabb ccdd eeff gghh iijj   -- original sequence, k = 4
//      0011 0011 0011 0011 0011   -- mask
n = (n | (n >> 2)) & 0x33333333;   // fold to aa|bb, cc|dd, etc.
n = (n | (n >> 1)) & 0x11111111;   // fold boolean expression as 0th bit position in each group

return bitcount(n);

关于algorithm - 通用位计数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45273128/