我写了一个算法（取自“C编程语言”），可以非常快地计算1位的数量：
我不明白为什么有人会说你的方法“非常快”。它有点聪明，平均来说应该比幼稚的替代方案更快。它也不依赖于int的表示的宽度，这是一个加号。我观察到它对负参数有未定义的行为，但这是按位运算符和函数的常见主题。
让我们分析一下，假设一个非否定的论点：

int c = 0;
for (; n; ++c)
    n &= n - 1;

字符串

• 执行了多少次循环迭代？

对于值的二进制表示中的每1位为1，而不管每个位在值中的 * 位置

• 每次迭代执行多少工作
• c的一个增量
• n与零的一次比较（在跳出循环时再加上一次）
• n减1
• 一位“与”

这忽略了读和存储，通过将操作数保留在寄存器中，读和存储很可能是免费的或特别便宜的。如果我们假设每一个都有相同的成本，那就是每次迭代四次操作。对于随机32位整数，平均将有16次迭代，平均总共65次操作。（最好的情况是一个操作，但最坏的情况是129，这并不比一个天真的实现更好）。
另一方面，__builtin_popcount()使用单个指令，而不管支持它的平台上的输入如何，比如你的平台很可能就是这样。然而，即使在那些没有目的指令的情况下，它也可以做得更快（平均而言）。
@dbush已经提出了一个这样的机制，它与您提出的机制具有类似的优点。特别是，它不依赖于预先选择的整数宽度，尽管它确实依赖于1位所在的表示中的 where，但它确实对某些参数（较小的参数）比其他参数运行得更快。如果我算对了，那一个将在随机32位输入上平均大约20次操作：四次循环迭代中的每一次中有五次（只有0.4%的随机输入将需要少于四次迭代）。我计算了每次迭代的一次表读取，我假设可以从缓存中提供，但这可能仍然不如对寄存器中已经保存的值进行算术运算那么快。
严格计算的一个是：

int countBit1Fast(uint32_t n) {
    n = (n & 0x55555555u) + ((n >> 1) & 0x55555555u);
    n = (n & 0x33333333u) + ((n >> 2) & 0x33333333u);
    n = (n & 0x0f0f0f0fu) + ((n >> 4) & 0x0f0f0f0fu);
    n = (n & 0x00ff00ffu) + ((n >> 8) & 0x00ff00ffu);
    n = (n & 0x0000ffffu) + ((n >>16) & 0x0000ffffu);
    return n;
}

型
这很容易计算：5次加法、5次移位、10次按位“与”运算，以及5次常量加载，每个输入总共25次运算（对于64位输入，它只上升到30次，尽管这些现在是64位运算而不是32位运算）。然而，该版本本质上依赖于输入数据类型的特定大小。

正如其他人所提到的，__buildin__popcount()速度很快，因为它使用单个x86指令。
如果你想要比你现有的更快的东西，不使用任何特定的处理器或编译器，你可以创建一个有256个条目的查找表：

int bitcount[] = {
    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,
};

字符串
然后使用它来获得每个字节的位数：

int countBit1Fast(int n) 
{
    int i, count = 0;
    unsigned char *ptr = (unsigned char *)&n;
    for (i=0;i<sizeof(int);i++) {
        count += bitcount[ptr[i]];
    }
    return count;
}

型

正如其他人所提到的，在x86_64上，你有一个popcount CPU指令，它将彻底击败任何软件实现。
在没有CPU popcount指令的情况下，哪种方法最快取决于字大小、查找速度（其可能取决于CPU高速缓存行为）和超标量流水线的有效性。
获取每个字节，在表中查找它，然后将这些值加在一起的简单方法非常快，大约需要ceil(num_bits/8)*3-1)操作，这取决于“数组获取”的工作方式。
还有另一种不太为人所知的方法，它通过将位分组为运行，然后重复创建一半的运行，其大小是以前的两倍，其中每个运行包含前两个运行的总和。
该算法需要4×log 2（num_bits））-1步，这意味着它对于小整数大小的性能相对较差，但对于较大的整数大小有所改善：
| 操作（查找）|操作（运行-添加）| ops (run-add) |
| --|--| ------------ |
| 二个|十一个| 11 |
| 五个|十五个| 15 |
| 十一个|十九岁| 19 |
| 二十三|二十三| 23 |
| 四十七|二十七| 27 |
| 九十五|三十一| 31 |
最初，你开始与每一位在其自己的运行;然后你取几对集合并把它们加在一起，所以每个集合都是一个从0到2的数字，这很方便地适合一个2位的无符号整数：

x = (x >> 1 & 0x55555555555555555555555555555555)
   +(x      & 0x55555555555555555555555555555555);

字符串
现在，每一对位都包含一个从0到2的数字，表示该对中曾经设置了多少位。随后的步骤相当简单：将相邻管路合并为宽度为两倍的新管路：

x = (x >> 2 & 0x33333333333333333333333333333333)
   +(x      & 0x33333333333333333333333333333333);

型
现在，每个4位的游程包含从0到4的数字。由于这些数字适合3位，因此每次运行的最高位将始终为0，并且不需要包含在掩码中。

x = (x >> 4 & 0x07070707070707070707070707070707)
   +(x      & 0x07070707070707070707070707070707);

型
现在，每个8位的游程包含从0到8的数字。由于这些数字适合4位，因此每次运行的前12位将始终为0，并且不需要包含在掩码中。

x = (x >> 8 & 0x000f000f000f000f000f000f000f000f)
   +(x      & 0x000f000f000f000f000f000f000f000f);

型
现在，每个16位的游程包含从0到16的数字。由于这些数字适合5位，因此每次运行的前27位将始终为0，并且不需要包含在掩码中。

x = (x >>16 & 0x0000001f0000001f0000001f0000001f)
   +(x      & 0x0000001f0000001f0000001f0000001f);

型
现在，每个32位的游程包含从0到32的数字。由于这些数字适合6位，因此每次运行的前58位将始终为0，并且不需要包含在掩码中。

x = (x >>32 & 0x000000000000003f000000000000003f)
   +(x      & 0x000000000000003f000000000000003f);

型
现在，每个64位的游程包含从0到64的数字。由于这些数字适合7位，因此每次运行的前121位将始终为0，并且不需要包含在掩码中。

x = (x >>64 & 0x0000000000000000000000000000007f)
   +(x      & 0x0000000000000000000000000000007f);

型
通常，对于步骤i，预先计算

w0 = 1<<i;      /* number of bits per run for THIS cycle */
w1 = 1<<i+1;    /* number of bits per run for NEXT cycle */
r1 = w1-1;      /* mask for a number from 0 .. w0 inclusive */
/* Create a pattern of bits with a 1 every w1 bits: */
m1 = 1 << w1;
m3 = UINTMAX / (m1 - 1);
m4 = m3 * r1;
shift[i] = w0;
mask[i] = m4;
/* for the variant below */
m0 = 1 << w0;
s_mult[i] = m0 - 1;

型
然后对于每个步骤用途：

x = (x >> shift[i] & mask[i])
   +(x             & mask[i]);

型
根据CPU执行乘法的速度，这可能会更好地利用流水线：

x -=  x >> 1 & 0x55555555555555555555555555555555;
x -= (x >> 2 & 0x33333333333333333333333333333333) * 3;
x -= (x >> 4 & 0x07070707070707070707070707070707) * 0xf;
x -= (x >> 8 & 0x000f000f000f000f000f000f000f000f) * 0xff;
x -= (x >>16 & 0x0000001f0000001f0000001f0000001f) * 0xffff;
x -= (x >>32 & 0x000000000000003f000000000000003f) * 0xffffffff;
x -= (x >>64 & 0x0000000000000000000000000000007f) * 0xffffffffffffffff;
y -= (x >> shift[i] & mask[i]) * s_mult[i];

型

__builtin__popcount(unsigned int)之所以这么快，是因为它是一个使用内置硬件指令的gcc扩展。如果你愿意用架构的可移植性来换取编译器的可移植性，那么看看同样快的intel内部函数，特别是：

_mm_popcnt_u32(unsigned __int32);
_mm_popcnt_u64(unsigned __int64);

字符串
然后，您必须包含<mmintrin.h>头文件才能使用这些内部函数，但是它们将与非gcc编译器一起工作。您可能还必须提供一个目标体系结构，以使函数内联（这是严格要求的），使用类似-march=native的东西。