如何不用循环与任何控制语句得到一个二进制数中１的个数
在做CSAPP的Datalab的过程中，有一道题目让你在不用循环与任何控制语句的情况下得到一个二进制数中１的个数。乍一看这好像是不可能完成的，但是又联想到了int类型的大小是有限的，于是可以用如下的方法来解决。
int bitcount(int x){
int mask = 0x01;
int sum = 0;
sum = sum + (x & mask);
sum = sum + (x >> 1 & mask);
sum = sum + (x >> 2 & mask);
sum = sum + (x >> 3 & mask);
sum = sum + (x >> 4 & mask);
sum = sum + (x >> 5 & mask);
sum = sum + (x >> 6 & mask);
sum = sum + (x >> 7 & mask);
sum = sum + (x >> 8 & mask);
sum = sum + (x >> 9 & mask);
sum = sum + (x >> 10 & mask);
sum = sum + (x >> 11 & mask);
sum = sum + (x >> 12 & mask);
sum = sum + (x >> 13 & mask);
sum = sum + (x >> 14 & mask);
sum = sum + (x >> 15 & mask);
sum = sum + (x >> 16 & mask);
sum = sum + (x >> 17 & mask);
sum = sum + (x >> 18 & mask);
sum = sum + (x >> 19 & mask);
sum = sum + (x >> 20 & mask);
sum = sum + (x >> 21 & mask);
sum = sum + (x >> 22 & mask);
sum = sum + (x >> 23 & mask);
sum = sum + (x >> 24 & mask);
sum = sum + (x >> 25 & mask);
sum = sum + (x >> 26 & mask);
sum = sum + (x >> 27 & mask);
sum = sum + (x >> 28 & mask);
sum = sum + (x >> 29 & mask);
sum = sum + (x >> 30 & mask);
sum = sum + (x >> 31 & mask);
return(sum);
}
注:此示例为３２位，６４位方法完全相同.(使用循环的克尼汉算法与此原理完全相同)
但这样的朴素方法有点太愚笨了，而且也不符合题目给出的操作符数量限制。经过查阅资料，我发现了如下的一种算法
int swar(uint32_t i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
| i | j | i-j |
|---|---|---|
| 00 | 00 | 00 |
| 01 | 00 | 01 |
| 10 | 01 | 01 |
| 11 | 01 | 10 |
emmmmm这是什么鬼???=.=
接下来我就找到了一篇讲解此算法的文章
magic
经过一番研究，算是弄明白了这个奇妙的算法。
我们接下来一行一行地看这个算法。
首先，第一行，我们令j = (i >> 1) & 0x55555555.接下来，我们看一下为什么要设这个0x55555555. 0x55555555写成二进制为0b01010101010101010101010101010101,接下来我们我们记i的前几位为$ i_1i_2i_3i_4i_5i_6i_7i_8 $, 那么ｊ的结果为$0i_10i_30i_50i_7$.这个算法的巧妙之处便在于此中非常重要的一点。我们两位两位地去看i-j这个数，可能有以下几种情况
| i | j | i-j |
|---|---|---|
| 00 | 00 | 00 |
| 01 | 00 | 01 |
| 10 | 01 | 01 |
| 11 | 01 | 10 |
也就是说，i-j的结果的值就是i中１的数量.于是，我们把整个int分成数个2bit的块，在每个块内我们已经完成了此问题，接下来就是要把整个结果聚合起来.
第二行与第三行的前半部分完成的就是这个工作。i = (i & 0x33333333) + ((i >> 2) & 0x33333333);(i + (i >> 4)) & 0x0F0F0F0F)这两部分代码分别把两位的结果聚合到了四位与八位。再接下来我们去乘的这个数0x01010101,相当于做了这样一件事:$k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k$这样一来最高位的字节就是结果了，我们只需把它移动到最低位就得到了答案。
