判断无符号整数二进制中1的个数(外一则)

三种算法。

算法1：
比较容易想到的算法，逐位比较，最多需要32次。

int count_ones_01(unsigned int n)
{
    int i;
    for(i = 0;n > 0;n >>= 1)
         i += (n&1);
    return i;
}

算法二：
Monster级算法。比较次数比算法1少，最多需要32次(如果int长度为32位的话)。

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

算法三：
二分法。遗憾的是不具有跨平台性。运算次数为5次(\(\log_{2}{32}\))

int count_ones(unsigned 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;
}

算法的思路是这样的：2位为一组，相加，看看有几个1。再4位为一组，相加，看看有几个1，
以此类推。
为了简单说明，先看看8位的情形。

x = (x & 0x55) + ((x >> 1) & 0x55);    (1)
x = (x & 0x33) + ((x >> 2) & 0x33);    (2)
x = (x & 0x0f) + ((x >> 4) & 0x0f);    (3)
return x;

对于语句(1)

当x=11111111

x= (x & 0x55) + ((x >> 1) & 0x55);

之后x=10101010。你2位2位地看，10=2, 就是2 2 2
2, 就是说各组都是2个1。

当x=00101001

x= (x & 0x55) + ((x >> 1) & 0x55);

之后x=00010101。你2位2位地看，就是0 1 1 1, 前
1组只有0个1，后面的组都是1个1。

接着看语句(2)

当x=abcdefgh

x=(x & 0x33)+((x >> 2)&0x33);

相当于 00cd00gh +　00ab00ef。

因为语句(1)之后，每两位表示该两位有几个１，相加就指示每4位有多少个1。这样就是4位
4位为一组。注意这样的分组，组与组之间永远都不会产生进位的。正因为不会产生进位，才
可以分开来看。

8位，16位，32位依上类推。

外一则：
利用算法三类似的思想，进行反转一个字节的二进制次序。

unsigned char reverse8( unsigned char c )
{
     c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
     c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
     c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
     return c;
}