代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这里有一个到目前为止还没有提到的解决方案，使用位字段。下面的程序使用4种不同的方法对100000000个16位整数数组中的设置位进行计数。计时结果在括号中给出(在MacOSX上，使用gcc -O3):
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 100000000
typedef struct {
unsigned char bit0 : 1;
unsigned char bit1 : 1;
unsigned char bit2 : 1;
unsigned char bit3 : 1;
unsigned char bit4 : 1;
unsigned char bit5 : 1;
unsigned char bit6 : 1;
unsigned char bit7 : 1;
} bits;
unsigned char sum_bits(const unsigned char x) {
const bits *b = (const bits*) &x;
return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
+ b->bit4 + b->bit5 + b->bit6 + b->bit7;
}
int NumberOfSetBits(int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
#define out(s) \
printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);
int main(int argc, char **argv) {
unsigned long i, s;
unsigned short *x = malloc(LENGTH*sizeof(short));
unsigned char lut[65536], *p;
unsigned short *ps;
int *pi;
/* set 3/4 of the bits */
for (i=0; i<LENGTH; ++i)
x[i] = 0xFFF0;
/* sum_bits (1.772s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
out(s);
/* NumberOfSetBits (0.404s) */
for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
out(s);
/* populate lookup table */
for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
lut[i] = sum_bits(p[0]) + sum_bits(p[1]);
/* 256-bytes lookup table (0.317s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
out(s);
/* 65536-bytes lookup table (0.250s) */
for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
out(s);
free(x);
return 0;
}
虽然位域版本非常可读，但计时结果显示它比NumberOfSetBits()慢了4倍以上。基于查找表的实现仍然要快得多，特别是对于一个65 kB的表。
其他回答
大约在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行布尔表来检查它。
不吉利
这里有一个到目前为止还没有提到的解决方案，使用位字段。下面的程序使用4种不同的方法对100000000个16位整数数组中的设置位进行计数。计时结果在括号中给出(在MacOSX上，使用gcc -O3):
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 100000000
typedef struct {
unsigned char bit0 : 1;
unsigned char bit1 : 1;
unsigned char bit2 : 1;
unsigned char bit3 : 1;
unsigned char bit4 : 1;
unsigned char bit5 : 1;
unsigned char bit6 : 1;
unsigned char bit7 : 1;
} bits;
unsigned char sum_bits(const unsigned char x) {
const bits *b = (const bits*) &x;
return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
+ b->bit4 + b->bit5 + b->bit6 + b->bit7;
}
int NumberOfSetBits(int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
#define out(s) \
printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);
int main(int argc, char **argv) {
unsigned long i, s;
unsigned short *x = malloc(LENGTH*sizeof(short));
unsigned char lut[65536], *p;
unsigned short *ps;
int *pi;
/* set 3/4 of the bits */
for (i=0; i<LENGTH; ++i)
x[i] = 0xFFF0;
/* sum_bits (1.772s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
out(s);
/* NumberOfSetBits (0.404s) */
for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
out(s);
/* populate lookup table */
for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
lut[i] = sum_bits(p[0]) + sum_bits(p[1]);
/* 256-bytes lookup table (0.317s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
out(s);
/* 65536-bytes lookup table (0.250s) */
for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
out(s);
free(x);
return 0;
}
虽然位域版本非常可读，但计时结果显示它比NumberOfSetBits()慢了4倍以上。基于查找表的实现仍然要快得多，特别是对于一个65 kB的表。
在我看来，“最好”的解决方案是另一个程序员(或者两年后的原始程序员)可以阅读而不需要大量注释的解决方案。你可能想要最快或最聪明的解决方案，有些人已经提供了，但我更喜欢可读性而不是聪明。
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);
}
这些依赖于特定的数据类型大小，所以它们不是那么可移植的。但是，由于许多性能优化是不可移植的，这可能不是一个问题。如果您想要可移植性，我会坚持使用可读的解决方案。
对于232查找表和逐个遍历每个位之间的折中方法:
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
下面是PHP中的一些东西(所有PHP整数都是32位符号，因此是31位):
function bits_population($nInteger)
{
$nPop=0;
while($nInteger)
{
$nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
$nPop++;
}
return $nPop;
}
