代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
摘自《黑客的喜悦》第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条指令(依赖于arch),没有分支。黑客的喜悦是令人愉快的!强烈推荐。
其他回答
对于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
这是一个有助于了解您的微架构的问题。我只是在gcc 4.3.3下用-O3编译的两个变量使用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; }
未经修改的黑客喜悦需要122亿周期。我的并行版本(计算的比特数是它的两倍)的运行周期为13.0千兆周期。在2.4GHz的酷睿双核上,两者总共消耗了10.5秒。在这个时钟频率下,25千兆周期= 10秒多一点,所以我相信我的计时是正确的。
这与指令依赖链有关,这对算法非常不利。通过使用一对64位寄存器,我几乎可以再次将速度提高一倍。事实上,如果我聪明一点,早点加上x+y,我就可以减少一些移位。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亿周期/ 14.1亿周期。后面的数字加起来是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上玩内联的把戏,尽管我在一些测试中没有使用内联关键字。当我让gcc玩把戏时,对pop4()的十亿次调用需要12.56 gigacycles,但我确定它是将参数折叠为常量表达式。更实际的数字似乎是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();
2560亿比特加起来在8.17秒内过去了。根据16位表查找的基准测试,3200万比特的计算结果为1.02秒。不能直接比较,因为另一个工作台没有给出时钟速度,但看起来我已经把64KB表版本的鼻涕打出来了,这首先是L1缓存的悲惨使用。
更新:决定做明显的和创建pop6()通过增加四个重复的行。结果是22.8gc, 3840亿比特在9.5秒内加起来。所以还有20%现在是800毫秒,320亿比特。
这不是最快或最好的解决方案,但我以自己的方式发现了同样的问题,我开始反复思考。最后我意识到它可以这样做,如果你从数学方面得到这个问题,画一个图,然后你发现它是一个有周期部分的函数,然后你意识到周期之间的差异……所以你看:
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);
}
}
在我看来,“最好”的解决方案是另一个程序员(或者两年后的原始程序员)可以阅读而不需要大量注释的解决方案。你可能想要最快或最聪明的解决方案,有些人已经提供了,但我更喜欢可读性而不是聪明。
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);
}
这些依赖于特定的数据类型大小,所以它们不是那么可移植的。但是,由于许多性能优化是不可移植的,这可能不是一个问题。如果您想要可移植性,我会坚持使用可读的解决方案。
我认为最快的方法——不使用查找表和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),则产生0b01,否则产生0b00。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
这句话应该很容易理解。在第一个操作之后,我们每两个比特中就有一个set位的计数,现在我们每4个比特中就有一个set位的计数。
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
它为我们提供了一个字节中set位的计数,在第二个nibble 0b01000110中,因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。
0b01000110 & 0x0F = 0b00000110
现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010,它有一个有趣的属性。如果我们的数字有四个字节,A B C D,它将产生一个新的数字,包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位,可以表示为0b00100000。
我们现在需要的是第一个字节,它是所有字节中所有set位的和,我们通过>> 24得到它。该算法是为32位字设计的,但可以很容易地修改为64位字。