代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我觉得很无聊,于是对三种方法进行了十亿次迭代。编译器是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,那么可以使用第二种方法。否则,请使用可读的(但速度较慢)一次一位的方法。
很难想象在什么情况下你会想要使用比特旋转方法。
编辑:这里也有类似的结果。
其他回答
public class BinaryCounter {
private int N;
public BinaryCounter(int N) {
this.N = N;
}
public static void main(String[] args) {
BinaryCounter counter=new BinaryCounter(7);
System.out.println("Number of ones is "+ counter.count());
}
public int count(){
if(N<=0) return 0;
int counter=0;
int K = 0;
do{
K = biggestPowerOfTwoSmallerThan(N);
N = N-K;
counter++;
}while (N != 0);
return counter;
}
private int biggestPowerOfTwoSmallerThan(int N) {
if(N==1) return 1;
for(int i=0;i<N;i++){
if(Math.pow(2, i) > N){
int power = i-1;
return (int) Math.pow(2, power);
}
}
return 0;
}
}
大约在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行布尔表来检查它。
不吉利
#!/user/local/bin/perl
$c=0x11BBBBAB;
$count=0;
$m=0x00000001;
for($i=0;$i<32;$i++)
{
$f=$c & $m;
if($f == 1)
{
$count++;
}
$c=$c >> 1;
}
printf("%d",$count);
ive done it through a perl script. the number taken is $c=0x11BBBBAB
B=3 1s
A=2 1s
so in total
1+1+3+3+3+2+3+3=19
这是一个有助于了解您的微架构的问题。我只是在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亿比特。
我个人使用这个:
public static int myBitCount(long L){
int count = 0;
while (L != 0) {
count++;
L ^= L & -L;
}
return count;
}