/*
题目描述：对于一个字节(8bit)的无符号整形变量，求二进制表示中“1”的个数，要求算法执行效率尽可能地高
*/
#include <windows.h>
#include <iostream>
using namespace std;

int Count(BYTE v);
int main()
{
BYTE v=255;
cout<<Count(v);
return 0;
}

方法一：直接的方法就是除以2向右移位， 逐个统计，但是用到取模和相除，这个很耗资源。
int Count(BYTE v)
{
int num=0;
while (v)
{
   if (v%2==1)
   {
    num++;
   }
   v=v/2;
}
return num;
}
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
方法二：使用位操作，除以2可以直接用位操作右移一位来实现，而且计算做位移操作的效率比除法高。
int Count(BYTE v)
{
int num=0;
while (v)
{
   num+=v & 0x01; //将v与00000001相与如果v的最后一位是1相与的结果是1，反之则是0。
   v>>=1;    //右移一位。
}
return num;
}
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
方法三：使用位操作，但是只会去统计1的个数，循环的次数是BYTE中1的个数，无需遍历。

int Count(BYTE v)
{
int num=0;
while (v)
{
   v &=(v-1); //v=v&(v-1)这个操作可以直接消除掉v中的最右边的1。
   num++;
}
return num;
}

//////////////////////////////////////////////////////////////////////
方法四：查表法，这个的效率应该是最高的了，空间换时间。

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)
{
return countTable[v];
}
这个程序要求效率尽可能的高，这四种方法中显然最后一种的时间复杂度最低了O(1).第一个方法最容易想到确不是最好的答案，第二种有些改进，但还是需要遍历Byte里的所有位，第三种方法只需做n次操作(n是实际Byte中的“1”的个数)。

     空间换时间在某些情况下是个好的选择，比如需要频繁使用这个算法的时候，但也不是尽然，还是得视情况而定。