求二进制中的 ‘1’ 的个数

这是我最近看《编程之美》那本书上的一个例子，和大家分享下我的理解。

这个题目其实不难，但是这个题目要求算法的执行效率尽可能高。什么才是高效率的算法呢？很模糊，你的算法也许还是会被更高效的算法给 pass掉。下面是我对这道题算法的总结，不能说是很高效的，但是也算不错了。

解法一：我们都知道，用这个数数以一个 2 ，原来的数字将会减少一个 0 。如果在除的过程中  有余数，那么就表示当前位置有一个 1 。

以 100011010 为例：

第一次除以 2 时，商为 10001101，余数为 0；

第二次除以 2 时，商为 1000110 ，余数为 1；

利用这个特点我们可以编写大概的代码如下：

int Count(BYTE v)
{
    int num = 0;
    while (v)
    {
        if (v % 2 == 1)
        {
            num++;
        }
        v = v / 2;
    }
    return num;
}

这种算法的效率怎么样呢？

解法二：通过上面的算法，我们可以看出，利用向右移位操作也可以实现这个过程，当然了，位运算的效率更高些。代码实现如下：

int Count(BYPE v)
{
    int num = 0;
    while (v)
    {
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

你还能想到更好的算法吗？

解法三：位运算的效率明显高于解法一，但是采用位操作，时间复杂度还是O(logv)  。logv是二进制数的位数。如果有办法让算法的复杂度只与“1”的个数有关，那么时间复杂度应该会降低一些。

为了简化这个问题，我们考虑只有一个“1”的情况，例如：00100000。

如何判断给定的二进制数里面有且只有一个“1”呢？可以通过判断这个数是否是 2 的整数次幂来实现。如果只和这一个“1”进行判断，结果为 0 或者 1 。所以如果进行这个操作后的结果为 0 ，00100000可以和00011111进行“与”操作。     

这个算法又怎样设计呢？

int Count(BYTE v)
{
    int num = 0;
    while (v)
    {
        v &= (v - 1);
        num++;
    }
    return num;
}

这个方法使得仅有一个 1 的情况仅进行一次判断就可得出。所以算是对上面的算法进行了优化，提高了效率。这个算法的复杂度降低到了O(M)，其中 M 是 v 中 1 的个数。       
               

解法四：当然了，如果你要是只针对八位进制的数据我们可以用分支法来实现，具体代码如下：

int Count(BYTE v)
{
    int num = 0;
    switch (v)
    {
        case 0x0:
            num = 0;
            break;
        case 0x1：
        case 0x2：
        case 0x4：
        case 0x8：
        case 0x10：
        case 0x20：
        case 0x40：
        case 0x80:
            num = 1;
            break;
        case 0x3:
        case 0x6:
        case 0xc:
        case 0x18:
        case 0x30:
        case 0x60:
        case 0xc0:
            num = 2;
            break;
            //... (这块还要继续写下去)
    }
    return num;
}

这个算法不算是很好，效率不是很好而且还要写很多东西，但是它给我们了一种思路就是用空间换时间。你可以写一个含有 256个元素的数字，把每个值对应的数中含有 1 的个数都当做它的元素值就好了，这种方法直接就可以得出结果。当然确定是浪费空间，代码量大。

解法五：这个解法效率也很好，是在看了我同学的博客后写的。代码如下：

int bit_count(unsigned int x )
{
  static unsigned int mask[] = { 0x55555555,
                                 0x33333333,
                                 0x0F0F0F0F,
                                 0x00FF00FF,
                                 0x0000FFFF };
  int i;
  int shift; /* number of positions to shift to right */

  for( i=0, shift=1; i < 5; i++, shift *= 2 )
    x = (x & mask[i]) + ( (x >> shift) & mask[i] );
  return x;
}

以上是一个比较小的问题，但是对问题的深入思考可以给我们很多启示。                       
博文链接是：http://blog.csdn.net/sim_szm/article/details/8769717