C语⾔统计整数⼆进制表⽰中1的个数
这是⼀个很有意思的问题，也是在⾯试中最容易被问到的问题之⼀。这个问题有个正式的名字叫，⽽且wikipedia上也提供了很好的位运算解决的⽅法，这个下⾯也会提到。
解决这个问题的第⼀想法是⼀位⼀位的观察，判断是否为1，是则计数器加⼀，否则跳到下⼀位，于是很容易有这样的程序。
1 2 3 4 5 6 7 8 9 10int test(int n)
{
int count=0;    while(n != 0){        if(n%2 ==1)            count++;        n /= 2;
}
return count; }
或者和其等价的位运算版本：
1 2 3 4 5 6 7 8 9int test(int n)
{
int count=0;
while(n != 0){
count += n&1;        n >>= 1;
}
return count;
}
这样的⽅法复杂度为⼆进制的位数，即，于是可是想⼀下，有没有只与⼆进制中1的位数相关的算法呢。
可以考虑每次到从最低位开始遇到的第⼀个1，计数，再把它清零，清零的位运算操作是与⼀个零，但是在有1的这⼀位与零的操作要同时不影响未统计过的位数和已经统计过的位数，于是可以有这样⼀个操作 n&(n-1) ，这个操作对⽐当前操作位⾼的位没有影响，对低位则完全清零。拿6（110）来做例⼦，
第⼀次 110&101=100，这次操作成功的把从低位起第⼀个1消掉了，同时计数器加1，第⼆次100&011=000，同理⼜统计了⾼位的⼀个1，此时n已变为0，不需要再继续了，于是110中有2个1。
代码如下：
1 2 3 4 5 6 7 8 9int test(int n) {
int count=0;    while(n != 0){        n &= n-1;        count ++;    }
return count; }
这⼏个⽅法虽然也⽤到了位运算，但是并没有体现其神奇之处，下⾯这个版本则彰显位运算的强⼤能⼒，若不告诉这个函数的功能，⼀般⼀眼看上去是想不到这是做什么的，这也是wikipedia上给出的计算hamming_weight⽅法。
1 2 3 4 5 6 7 8 9 10int test(int n)
{
n = (n&0x55555555) + ((n>>1)&0x55555555);    n = (n&0x33333333) + ((n>>2)&0x33333333);    n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);    return n;
}
没有循环，5个位运算语句，⼀次搞定。
⽐如这个例⼦，143的⼆进制表⽰是10001111，这⾥只有8位，⾼位的0怎么进⾏与的位运算也是0，所以只考虑低位的运算，按照这个算法⾛⼀次
+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |  <---143
return在c语言中是什么意思+---+---+---+---+---+---+---+---+
|  0 1  |  0 0  |  1 0  |  1 0  |  <---第⼀次运算后
+-------+-------+-------+-------+
|    0 0 0 1    |    0 1 0 0    |  <---第⼆次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |  <---第三次运算后，得数为5
+-------------------------------+
这⾥运⽤了分治的思想，先计算每对相邻的2位中有⼏个1，再计算每相邻的4位中有⼏个1，下来8位，16位，32位，因为2^5＝32，所以对于32位的机器，5条位运算语句就够了。
像这⾥第⼆⾏第⼀个格⼦中，01就表⽰前两位有1个1，00表⽰下来的两位中没有1，其实同理。再下来01+00=0001表⽰前四位中有1个1，同样的10+10=0100表⽰低四位中有4个1，最后⼀步0001+0100=00000101表⽰整个8位中有5个1。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。