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



（方法一）：
unsigned char Count(unsigned char byt)
{
unsigned char num=0;
while (byt)
{
num += (byt & 0×01);
byt >>= 1;
}
return num;
}
不管有多少个1都要循环8次，执行效率不高，但是执行该函数的时间每次都是确定的。

方法二：
直接的方法就是除以2向右移位， 逐个统计，但是用到取模和相除，这个很耗资源。
int Count(BYTE v)
{
int num=0;
while (v)
{
if (v%2==1)
{
num++;
}
v=v/2;
}
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;
}
循环次数与Byte中1的个数有关，但是函数执行时间不确定，不过效率比前面的要提高了很多，是不是以为这就是最佳答案了吧，告诉你：NO。


方法四：

查表法，这个的效率应该是最高的了——空间换时间。将0~255各个数中所含的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)
{
return countTable[v];
}
这个程序要求效率尽可能的高，显然最后一种的时间复杂度最低了O(1).执行时间也是确定的。空间换时间在某些情况下是个好的选择，比如需要频繁使用这个算法的时候，但也不是尽然，还是得视情况而定。

这个是黑马的面试题么？这么没有节操。。。

不懂真不懂

我还没有理解字节中杂找二进制中的1，c不是汇编语言么？只要链接后才是指令语言有二进制组成，还是说用函数标识二进制数组，在这个模拟数组中查找

没有节操的面试题,还要手写,坑爹到无尽头

首先,我就没看懂BYT是什么东西,

反正我是看不懂

用空间复杂度换时间。。。。。而且  只能到255啊。。。。

还没学这么深，感觉好难。。。

加点注释就好了，真心看不懂啊

我完全看不懂，因为还没学到

这么难吗

看了你的帖子,我与就业班的距离变更加遥远了.请问一次面试当中要面对多少道这样的题目,这个是算低难度还是高难度的？

看来我不适合学C语言。。。

hulk374 发表于 2015-10-22 17:54
看来我不适合学C语言。。。

这样的面试题应该不多，先别否定自己

不错，技术贴。这真是面试题？顶多能写出来第一种

真是牛  赞一个

空间换时间 我第一次见啊  好牛逼

学习学习！

int count(byte v)
{
  int num = 0;
  while(v)
  {
    if(v&1)
    {
       num++;
     }
    v = v>>1;
   }
  return num;
  }
这个对吗？