计算二进制位有几多位1

计算二进制位有多少位1
  最近着迷于位运算，有这样一个问题如何算出一个数的二进制有多位1呢？
比较好的有下面两种方法
第一种：

unsigned int countBit(unsigned int n){unsigned int count = 0;while(n){count++;n&=n-1;}return count;}

原理比较简单每次执行 n&=n-1 时n的二进制都会少一个1.
第二种方法稍微有点复杂

unsigned int countBit2(unsigned int nValue){nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);return nValue;}

咋一看的确有点超出了一般人的想象力，
看一看输入0xFFFF后每一步的结果你就会明白点

1111111111111111（输入值）
1010101010101010（每两位数一组表示上一个数相应位有几个1）
0100010001000100（每四位数一组表示上一个数相应位两个数之和）
0000100000001000（每八位数一组表示上一个数相应位两个数之和）
0000000000010000（每十六位数一组表示上一个数相应位两个数之和）
0000000000010000（每三十二数一组表示上一个数相应位两个数之和）
很有技巧性，位数多的时候性能更好，不过它的缺陷就是只适合在32位的机器上，
前面一种算法在64位机器上也有效

查看更多 下一篇