计算 32 位整数中设置的位数

Question

代表数字 7 的 8 位如下所示：

00000111

设置了 3 位。

确定 32 位整数中设置位数的算法有哪些？

Answer 1

C++20 std::popcount

以下提案已合并http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html 并且应该将其添加到 标头中。

我希望用法是这样的：

#include <bit>
#include <iostream>

int main() {
    std::cout << std::popcount(0x55) << std::endl;
}

当 GCC 支持时我会尝试一下，带有 g++-9 -std=c++2a 的 GCC 9.1.0 仍然不支持它。

该提案称：

标头：<位>

命名空间 std { 

    // 25.5.6，计数 
    模板<类T> 
      constexpr int popcount(T x) noexcept; 
  

和：

模板 
    constexpr int popcount(T x) noexcept; 
  

约束：T 是无符号整数类型（3.9.1 [basic.fundamental]）。

返回：x的值中1的位数。

还添加了 std::rotl 和 std::rotr 来进行循环位旋转：C++ 中循环移位（旋转）操作的最佳实践

Answer 2

我大约在 1990 年为 RISC 机器编写了一个快速位计数宏。它不使用高级算术（乘法、除法、%）、内存获取（太慢）、分支（太慢），但它确实假设 CPU 有一个32 位桶式移位器（换句话说，>> 1 和>> 32 占用相同数量的周期。）它假设小常量（例如 6、12、24）不需要任何成本即可加载到寄存器中，或者存储在临时文件中并一遍又一遍地重复使用。

有了这些假设，在大多数 RISC 机器上，它可以在大约 16 个周期/指令中计算 32 位。 请注意，15 个指令/周期接近周期或指令数量的下限，因为似乎至少需要 3 条指令（掩码、移位、运算符）才能将加数数量减半，因此 log_2(32) = 5, 5 x 3 = 15 条指令是准下界。

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

这是第一个也是最复杂的步骤的秘密：

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

因此，如果我将上面的第一列 (A) 右移 1 位，然后从 AB 中减去它，我就会得到输出 (CD)。 扩展到 3 位的情况类似； 如果你愿意的话，你可以用像我上面这样的 8 行布尔表来检查它。

• 唐吉利斯

Answer 3

有多种算法可以对设置的位数进行计数； 但我认为最好的就是更快的！
您可以在此页面上查看详细信息：

Bit Twiddling Hacks

我建议这个：

计数位设置使用 64 位指令的 14、24 或 32 位字

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

此方法需要具有快速模数除法的 64 位 CPU 才能高效。 第一个选项只需要3次操作； 第二个选项取10； 第三个选项取15。

Answer 4

我总是在竞争性编程中使用它，它很容易编写并且很高效：

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Answer 5

我发现使用 SIMD 指令（SSSE3 和 AVX2）在数组中实现位计数。 与使用 __popcnt64 内部函数相比，它的性能提高了 2-2.5 倍。

SSSE3 版本：

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

AVX2 版本：

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}

Answer 6

一种快速 C# 解决方案，使用预先计算的字节位计数表并根据输入大小进行分支。

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}

Answer 7

Java JDK1.5

Integer.bitCount(n);

其中 n 是要计算 1 的数量。

还检查，

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }

Answer 8

我特别喜欢财富档案中的这个例子：

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

我最喜欢它，因为它太漂亮了！

Answer 9

你可以这样做：

while(n){
    n = n & (n-1);
    count++;
}

这背后的逻辑是 n-1 的位与 n 的最右边的设置位反转。

如果n=6，即110，那么5就是101，这些位从n的最右边设置位开始反转。

因此，如果我们 & 这两个位，我们将在每次迭代中将最右边的位设置为 0，并且始终转到下一个最右边的设置位。 因此，对设置位进行计数。 当每一位都被设置时，最坏的时间复杂度将为 O(log n)。

Answer 10

如果您使用 C++，另一个选择是使用模板元编程：

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

用法是：

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

您当然可以进一步扩展此模板以使用不同的类型（甚至自动检测位大小），但为了清晰起见，我保持简单。

编辑：忘记提及这很好，因为它应该可以在任何 C++ 编译器中工作，并且如果使用常量值作为位数，它基本上只是为您展开循环（换句话说，我很确定这是您能找到的最快的通用方法）

Answer 11

unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

让我解释一下这个算法。

该算法基于分治算法。 假设有一个8位整数213（二进制为11010101），算法的工作原理如下（每次合并两个相邻块）：

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

Answer 12

来自《黑客之乐》，第 12 页 66，图 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

以大约 20 条指令执行（依赖于架构），无分支。

黑客的乐趣 令人愉快！ 强烈推荐。

Answer 13

“最佳算法”是什么意思？ 短路代码还是禁食代码？ 您的代码看起来非常优雅，并且执行时间恒定。 代码也很短。

但如果速度是主要因素而不是代码大小，那么我认为以下可能会更快：

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

我认为对于 64 位值来说这不会更快，但 32 位值可能会更快。

Answer 14

我使用下面的代码更直观。

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

逻辑：n & (n-1) 重置 n 的最后设置位。

PS：我知道这不是 O(1) 解决方案，尽管这是一个有趣的解决方案。

Answer 15

几个悬而未决的问题：-

1. 如果数字是负数呢？
2. 如果数字是 1024 ，那么“迭代除以 2”方法将迭代 10 次。

我们可以修改算法以支持负数，如下所示：-

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

现在为了克服第二个问题，我们可以编写如下算法：-

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

有关完整参考，请参阅：

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

Answer 16

private int get_bits_set(int v)
{
    int c; // 'c' accumulates the total bits set in 'v'
    for (c = 0; v>0; c++)
    {
        v &= v - 1; // Clear the least significant bit set
    }
    return c;
}

Answer 17

您正在寻找的函数通常称为二进制数的“横向和”或“总体计数”。 Knuth 在前分册 1A，第 11-12 页中对此进行了讨论（尽管在第 2 卷，4.6.3-(7) 中有一个简短的参考。）

经典轨迹是 Peter Wegner 的文章“A Technique for在二进制计算机中计数”，来自 ACM 通讯，第 3 卷 (1960) 第 5 期，第 322 页。 他在那里给出了两种不同的算法，一种针对预期“稀疏”的数字（即数量较少）进行了优化，另一种针对相反的情况进行了优化。

Answer 18

这不是最快或最好的解决方案，但我以我的方式发现了同样的问题，我开始思考再思考。 最后我意识到，如果你从数学方面得到问题，并绘制一个图表，然后你发现它是一个具有一些周期性部分的函数，然后你意识到周期之间的差异......所以可以这样做干得好：

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}

Answer 19

我认为 Brian Kernighan 的 方法也很有用......
它会经历与设置位一样多的迭代。 因此，如果我们有一个仅设置高位的 32 位字，那么它只会循环一次。

/** count the number of bits set in n */
int countSetBits(unsigned int n) {
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

1988 年出版，C 编程语言第二版。 （作者：Brian W. Kernighan 和 Dennis M. Ritchie）在练习 2-9 中提到了这一点。 2006年4月19日，Don Knuth向我指出，这个方法“首先由Peter Wegner发表在CACM 3 (1960), 322上。（也由Derrick Lehmer独立发现，并于1964年发表在Beckenbach编辑的一本书中。）”

Answer 20

当您写出位模式时，黑客之乐的位操作变得更加清晰。

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

第一步将偶数位与奇数位相加，产生每两个位的和。 其他步骤将高阶块添加到低阶块中，将块大小一直加倍，直到我们得到占据整个 int 的最终计数。

Answer 21

对于 2³² 查找表和单独迭代每个位之间的折中方案：

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

来自 http： //ctips.pbwiki.com/CountBits

Answer 22

这可以在 O(k) 中完成，其中 k 是设置的位数。

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

Answer 23

为什么不迭代除以 2？

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

我同意这不是最快的，但“最好”有点含糊。 我认为“最好”应该有一个清晰的要素

Answer 24

这是有助于了解微架构的问题之一。 我刚刚对使用 -O3 编译的 gcc 4.3.3 下的两个变体进行了计时，使用 C++ 内联来消除函数调用开销，十亿次迭代，保持所有计数的运行总和以确保编译器不会删除任何重要的内容，使用 rdtsc 进行计时（时钟周期精确）。

inline int pop2(unsigned x, unsigned y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x+y) & 0x000000FF;
}

未经修改的 Hacker's Delight 需要 12.2 gigacycle。 我的并行版本（位数是其两倍）运行速度为 13.0 GB。 在 2.4GHz Core Duo 上，两者总共花费了 10.5 秒。 25 gigacycles = 在此时钟频率下仅超过 10 秒，所以我确信我的计时是正确的。

这与指令依赖链有关，这对该算法非常不利。 通过使用一对 64 位寄存器，我几乎可以将速度再次提高一倍。 事实上，如果我聪明一点，早点添加 x+ya，我就可以减少一些班次。 经过一些小调整的 64 位版本的结果大约是偶数，但位数又是原来的两倍。

凭借 128 位 SIMD 寄存器（又一个两倍），SSE 指令集通常也有巧妙的快捷方式。

代码没有理由特别透明。 界面简单，算法可以在很多地方在线引用，并且可以进行全面的单元测试。 偶然发现它的程序员甚至可能会学到一些东西。 这些位操作在机器级别上是非常自然的。

好的，我决定对调整后的 64 位版本进行测试。 对于这个 sizeof(unsigned long) == 8

inline int pop2(unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return x & 0xFF;
}

看起来差不多是正确的（不过我没有仔细测试）。 现在计时结果为 10.70 gigacycles / 14.1 gigacycles。 后来的数字总计 1280 亿位，相当于这台机器上经过的 5.9 秒。 非并行版本加快了一点点，因为我在 64 位模式下运行，并且它喜欢 64 位寄存器，比 32 位寄存器稍好一些。

让我们看看这里是否还有更多的 OOO 管道。 这有点复杂，所以我实际上测试了一下。 每个项的总和为 64，所有总和为 256。

inline int pop4(unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  enum { m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF };

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    return x & 0x000001FF;
}

我有一瞬间很兴奋，但事实证明 gcc 正在使用 -O3 玩内联技巧，即使我在某些测试中没有使用 inline 关键字。 当我让 gcc 发挥作用时，对 pop4() 的十亿次调用需要 12.56 gigacycle，但我确定它将参数折叠为常量表达式。 更现实的数字似乎是 19.6gc，另外加速 30%。 我的测试循环现在看起来像这样，确保每个参数都足够不同以阻止 gcc 玩把戏。

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

8.17 秒内总计 2560 亿比特。 按照 16 位表查找的基准计算，3200 万位的计算结果为 1.02 秒。 无法直接比较，因为另一个bench没有给出时钟速度，但看起来我已经从64KB表格版本中打掉了鼻涕，这首先是L1缓存的悲剧性使用。

更新：决定做显而易见的事情并通过添加四个重复行来创建 pop6() 。 结果为 22.8gc，9.5 秒内总计 3840 亿位。 因此，现在还有 20% 的时间为 320 亿位，时间为 800 毫秒。

Answer 25

如果您碰巧使用 Java，内置方法 Integer.bitCount 将执行此操作。

Answer 26

我感到无聊，并对三种方法的十亿次迭代进行了计时。 编译器是gcc -O3。 CPU 是他们在第一代 Macbook Pro 中安装的任何东西。

最快的是以下代码，用时 3.7 秒：

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

第二名是相同的代码，但查找 4 个字节而不是 2 个半字。 这花了大约 5.5 秒。

第三名是有点麻烦的“横向加法”方法，用时 8.6 秒。

第四名是 GCC 的 __builtin_popcount()，成绩为可耻的 11 秒。

一次一位计数的方法要慢得多，而且我厌倦了等待它完成。

因此，如果您最关心性能，那么请使用第一种方法。 如果您关心，但又不足以花费 64Kb RAM，请使用第二种方法。 否则，请使用可读（但速度慢）的一次一位方法。

很难想象在什么情况下您会想要使用位调整方法。

编辑：类似的结果此处。

Answer 27

我认为最快的方法（不使用查找表和 popcount）如下。 只需 12 次操作即可计算设置位。

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

它之所以有效，是因为您可以通过将设置位分成两半来计算设置位的总数，计算两半中设置位的数量，然后将它们相加。 也称为分而治之范式。 让我们详细说明一下。

v = v - ((v >> 1) & 0x55555555); 

两位中的位数可以是 0b00、0b01 或 0b10。 让我们尝试在 2 位上解决这个问题。

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这就是所需要的：最后一列显示每两个位对中设置位的计数。 如果两位数为 >= 2 (0b10)，则 and 生成 0b01，否则生成 0b00 。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这个说法应该很容易理解。 第一次操作后，我们得到了每两位中设置位的计数，现在我们将每 4 位中的计数相加。

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们对上面的结果求和，得到 4 位中设置位的总数。 最后一条语句是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分解...

v + (v >> 4)

它与第二个语句类似； 我们以 4 为一组来计算设置的位。 由于我们之前的操作，我们知道每个半字节中都有设置位的计数。 让我们看一个例子。 假设我们有字节 0b01000010。 这意味着第一个半字节设置了 4 位，第二个半字节设置了 2 位。 现在我们将这些小块加在一起。

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了第二个半字节 0b01000110 中一个字节中设置位的计数，因此我们屏蔽了该数字中所有字节的前四个字节（丢弃它们）。

0b01000110 & 0x0F = 0b00000110

现在每个字节都有设置位的计数。 我们需要将它们加在一起。 诀窍是将结果乘以 0b10101010，它有一个有趣的属性。 如果我们的数字有四个字节 ABC D，它将产生一个具有这些字节 A+B+C+DB+C+D C+D D 的新数字。 4 字节数字最多可以设置 32 位，可以表示为 0b00100000。

现在我们需要的是第一个字节，它具有所有字节中所有设置位的总和，我们可以通过 >> 得到它。 24。 该算法专为 32 位 字设计，但可以轻松修改为 64 位 字。

Answer 28

在我看来，“最好”的解决方案是可以被另一位程序员（或两年后的原始程序员）阅读而无需大量注释的解决方案。 您可能很想要最快或最聪明的解决方案，有些已经提供了，但我更喜欢可读性而不是聪明。

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

如果您想要更快的速度（假设您很好地记录了它以帮助您的继任者），您可以使用表查找：

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

这些依赖于特定的数据类型大小，因此它们不那么可移植。 但是，由于许多性能优化无论如何都不可移植，因此这可能不是问题。 如果您想要可移植性，我会坚持使用可读的解决方案。

Answer 29

某些语言以一种可以使用有效硬件支持（如果可用）的方式可移植地公开操作，否则希望有一些不错的库回退。

例如（来自按语言列出的表格）：

• C++ 有 std:: bitset<>::count()，或 C++20 < code>std::popcount(T x)
• Java 有 java.lang.Integer.bitCount() （也适用于 Long 或 BigInteger）
• C# 有 System. Numerics.BitOperations.PopCount()
• Python 有 int.bit_count() （自 3.10 起）

不过，并非所有编译器/库实际上都能在可用时使用硬件支持。 （特别是 MSVC，即使使用使 std::popcount 内联为 x86 popcnt 的选项，其 std::bitset::count 仍然始终使用查找表。这有望在未来版本中改变。）

还要考虑以下内置函数当可移植语言没有这种基本的位操作时，您的编译器。 以 GNU C 为例：

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

在最坏的情况下（没有单指令硬件支持），编译器将生成对函数的调用（在当前的 GCC 中使用移位/和位黑客 喜欢这个答案，至少对于 x86 ）。 在最好的情况下，编译器将发出一条 cpu 指令来完成这项工作。 （就像 * 或 / 运算符 - GCC 将使用硬件乘法或除法指令（如果可用），否则将调用 libgcc 辅助函数。）或者甚至更好，如果操作数是内联后的编译时常量，它可以进行常量传播以获得编译时常量 popcount 结果。

GCC 内置程序甚至可以跨多个平台工作。 Popcount 几乎已成为 x86 架构中的主流，因此现在开​​始使用内置指令是有意义的，这样当您使用 -mpopcnt 或包含该指令的内容进行编译时，您可以重新编译以使其内联硬件指令（ 示例）。 其他架构已经流行多年，但在 x86 世界中，仍然有一些古老的 Core 2 和类似的老式 AMD CPU 在使用。

---

在 x86 上，您可以告诉编译器它可以使用 -mpopcnt（也由 -msse4.2 暗示）支持 popcnt 指令。 请参阅 GCC x86 选项。 -march=nehalem -mtune=skylake （或 -march= 您希望代码采用并调整的任何 CPU）可能是一个不错的选择。 在较旧的 CPU 上运行生成的二进制文件将导致非法指令错误。

要使二进制文件针对您构建它们的计算机进行优化，请使用-march=native（使用 gcc、clang 或 ICC）。

MSVC 为 x86 popcnt 指令提供了一个内在函数，但是与 gcc 不同，它实际上是硬件指令的内在特征，需要硬件支持。

---

使用 std::bitset<>::count() 而不是内置函数

理论上，任何知道如何为目标 CPU 有效弹出计数的编译器都应该通过 ISO C++ 公开该功能 std::bitset。 实际上，在某些情况下，对于某些目标 CPU，您可能会更好地使用位破解 AND/shift/ADD。

对于硬件 popcount 是可选扩展的目标体系结构（例如 x86），并非所有编译器都具有在可用时利用它的 std::bitset。 例如，MSVC 无法在编译时启用 popcnt 支持，并且它的 std::bitset<>::count 始终使用 表查找，即使使用 /Ox /arch:AVX （其中意味着 SSE4.2，这又意味着 popcnt 功能。）（更新：见下文；确实让 MSVC 的 C++20 std::popcount 使用 x86 < code>popcnt，但仍然不是它的 bitset<>::count。MSVC 可以通过更新其标准库头以使用 std::popcount（如果可用）来解决这个问题。）

但至少你得到了一些可以在任何地方使用的可移植的东西。 ，并且使用带有正确目标选项的 gcc/clang，您可以获得支持它的架构的硬件 popcount。

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

See 来自 Godbolt 编译器资源管理器上的 gcc、clang、icc 和 MSVC 的 asm。

x86-64 gcc -O3 -std=gnu++11 -mpopcnt 发出此消息：

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret

unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax        # unnecessary 64-bit operand size
    ret

unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11 发出（对于 int arg version)：

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

该源代码根本不是 x86 特定或 GNU 特定的，但只能与 gcc/clang/icc 良好地编译，至少在针对 x86（包括 x86-64）时是这样。

另请注意，gcc 对于没有单指令 popcount 的体系结构的后备是一次字节表查找。 对于 ARM 来说，这并不是什么好事，例如。

C++20 有 std::popcount(T)< /a>

不幸的是，当前的 libstdc++ 标头在开始时使用特殊情况 if(x==0) return 0; 定义了它，在编译 x86 时，clang 不会优化：

#include <bit>
int bar(unsigned x) {
    return std::popcount(x);
}

clang 11.0.1 -O3 -std=gnu++20 -march=nehalem 现场演示

# clang 11
    bar(unsigned int):                                # @bar(unsigned int)
        popcnt  eax, edi
        cmove   eax, edi         # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
        ret

但 GCC 编译得很好：

# gcc 10
        xor     eax, eax         # break false dependency on Intel SnB-family before Ice Lake.
        popcnt  eax, edi
        ret

甚至 MSVC 也能很好地使用它，只要您使用 -arch:AVX 或更高版本（并使用 -std:c++latest）。 现场演示

int bar(unsigned int) PROC                                 ; bar, COMDAT
        popcnt  eax, ecx
        ret     0
int bar(unsigned int) ENDP                                 ; bar

Answer 30

这称为“汉明权重”、“popcount”或“横向加法”。

一些 CPU 有一条内置指令来完成此操作，而另一些 CPU 则具有作用于位向量的并行指令。 像 x86 的 popcnt 这样的指令（在支持它的 CPU 上）几乎肯定会对于单个整数来说是最快的。 某些其他架构可能具有通过微编码循环实现的慢速指令，该微编码循环在每个周期测试一位（需要引用 - 硬件弹出计数通常很快，如果存在的话。）。

“最佳”算法实际上取决于您使用的 CPU 以及您的使用模式。

您的编译器可能知道如何执行适合您正在编译的特定 CPU 的操作，例如 C++20 std::popcount() 或 C++ std::bitset<32>::count()，作为访问内置/内在函数的可移植方式（请参阅关于这个问题的另一个答案）。 但是您的编译器为没有硬件 popcnt 的目标 CPU 选择的回退可能不是您的用例的最佳选择。 或者您的语言（例如 C）可能不会公开任何可以使用特定于 CPU 的 popcount 的可移植函数（当有一个函数时）。

---

不需要（或受益于）任何硬件支持的可移植算法

如果您的 CPU 具有较大的缓存并且您在紧密循环中执行大量此类操作，则预填充的表查找方法可能会非常快。 然而，它可能会因为“高速缓存未命中”的代价而受到影响，即 CPU 必须从主内存中获取一些表。 （单独查找每个字节以保持表格较小。）如果您想要连续范围的数字的 popcount，则只有低字节会更改 256 个数字的组，这非常好。

如果您知道您的字节大部分是 0 或大部分是 1，那么对于这些​​情况有一些有效的算法，例如，在循环中使用 bithack 清除最低的集合，直到它变为零。

我相信下面是一个非常好的通用算法，称为“并行”或“可变精度 SWAR 算法”。 我已经用类似 C 的伪语言表达了这一点，您可能需要调整它以适用于特定语言（例如，在 C++ 中使用 uint32_t，在 Java 中使用 >>）：

GCC10 和 clang 10.0 可以识别此模式/ idiom 并将其编译为硬件 popcnt 或可用的等效指令，为您提供两全其美的效果。 (Godbolt)

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     i *= 0x01010101;                        // horizontal sum of bytes
     return  i >> 24;               // return just that top byte (after truncating to 32-bit even when int is wider than uint32_t)
}

对于 JavaScript：使用 |0 强制转换为整数以提高性能：将第一行更改为 i = (i|0) - ((i >> 1）& 0x55555555);

这具有所讨论的任何算法中最好的最坏情况行为，因此将有效地处理您向其抛出的任何使用模式或值。 （它的性能不依赖于普通 CPU 的数据，其中包括乘法在内的所有整数运算都是恒定时间的。使用“简单”输入它不会变得更快，但它仍然相当不错。）

参考：

• 位旋转黑客
• 低级位黑客简介 了解位黑客基础知识，例如减 1 如何翻转连续的零。
• 汉明权重（维基百科）
• 快速位计数
• 聚合魔法算法

---

这个 SWAR bithack 的工作原理：

i = i - ((i >> 1) & 0x55555555);

第一步是屏蔽的优化版本，以隔离奇数/偶数位，移位以排列它们，然后添加。 这实际上在 2 位累加器中进行了 16 次单独的加法（SWAR = SIMD Within A Register）。 就像(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步采用这些 16x 2 位累加器中的奇数/偶数八个并再次相加，产生 8x 4 位和。 这次不可能进行 i - ... 优化，因此它只是在移位之前/之后进行屏蔽。 当编译需要在寄存器中构造 32 位常量的 ISA 时，在移位之前两次使用相同的 0x33... 常量而不是 0xccc... 是一件好事分别地。

最后的移位加法步骤 (i + (i >> 4)) & 0x0F0F0F0F 加宽至 4x 8 位累加器。 它在加法之后而不是之前进行屏蔽，因为如果设置了相应输入位的所有 4 位，则任何 4 位累加器中的最大值都是 4。 4+4 = 8 仍然适合 4 位，因此在 i + (i >> 4) 中不可能在半字节元素之间进位。

到目前为止，这只是使用 SWAR 技术并进行了一些巧妙优化的相当正常的 SIMD。 继续使用相同的模式再执行 2 个步骤可以扩大到 2x 16 位计数，然后扩大到 1x 32 位计数。 但是，在具有快速硬件乘法的机器上，有一种更有效的方法：

一旦我们有足够少的“元素”，与魔术常量的乘法可以将所有元素求和到顶部元素。 在本例中为字节元素。 乘法是通过左移和加法完成的，因此 x * 0x01010101 的乘法结果为 x + (x<<8) + (x<<16) + (x<<24)。我们的 8 位元素足够宽（并且保持足够小的计数），因此不会在最高 8 位中产生进位 。

此版本的 64 位版本可以使用 0x0101010101010101 乘法器在 64 位整数中执行 8x 8 位元素，并使用 >>56 提取高字节。 所以它不需要任何额外的步骤，只需要更广泛的常数。 这是当未启用硬件 popcnt 指令时，GCC 在 x86 系统上对 __builtin_popcountll 使用的内容。 如果您可以为此使用内置函数或内在函数，请这样做以使编译器有机会进行特定于目标的优化。

---

使用完整的 SIMD 来处理更宽的向量（例如对整个数组进行计数）

这种按位 SWAR 算法可以并行化以同时在多个向量元素中完成，而不是在单个整数寄存器中完成，从而在具有 SIMD 但没有可用的 popcount 指令的 CPU 上实现加速。 （例如，x86-64 代码必须在任何 CPU 上运行，而不仅仅是 Nehalem 或更高版本。）

但是，使用向量指令进行 popcount 的最佳方法通常是使用变量洗牌来执行 4 位的表查找每个字节并行的时间。 （4 位索引向量寄存器中保存的 16 项表）。

在 Intel CPU 上，硬件 64 位 popcnt 指令的性能优于 SSSE3 PSHUFB位并行实现大约为 2 倍，但前提是如果您的编译器正确处理一个>。 否则上证所可能会大幅领先。 较新的编译器版本可以识别 popcnt false 依赖项 英特尔问题。

• 适用于 SSSE3、AVX2、AVX512BW、AVX512VBMI 或 AVX512 的最先进 x86 SIMD popcount VPOPCNT。 在向量之间使用 Harley-Seal 来推迟元素内的 popcount。 （还有 ARM NEON）
• 使用AVX-512或AVX-2对大数据进行1位计数
• 相关：mklarqvist 的位置 popcount - 对多个 8、16、32 或 64 位整数的每个位位置进行单独计数。 （同样，x86 SIMD 包括 AVX-512，它在这方面非常擅长，vpternlogd 使 Harley-Seal 非常出色。）