【编程之美】2.1 - 求二进制数中1的个数

• 问题描述：对于一个字节（8bit）的无符号整形变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能高。

• 解法一：利用整形数据除法的特点，通过相除和判断余数的值来分析

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

• 解法二：利用向右移位操作来达到上面的相处的效果

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

• 解法三：在每次判断中，仅与1来进行判断【不易想到，较为巧妙】

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

• 解法四：使用分支操作：因为只有8位数据，直接把0~255的情况都进行罗列【使用了空间换时间的方法】

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;     
}

• 解法五：查表法【时间复杂度为O(1)】，在一个需要频繁使用这个算法的应用中，通过“空间换时间”来获取高的时间效率是一个常用的方法。

/* 预定义的结果表 */
int countTable[256] =
{
     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
        3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
        4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
        3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
        4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
        6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
        5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
        4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
        4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
        7, 6, 7, 7, 8
};
int Count(BYTE v))
{
     //check parameter
     return countTable[v];
}