黑马程序员技术交流社区

标题: C语一个面试题 [打印本页]

作者: zhuaihuo1744    时间: 2015-10-20 12:59
标题: C语一个面试题
题目描述:对于一个字节(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).执行时间也是确定的。空间换时间在某些情况下是个好的选择,比如需要频繁使用这个算法的时候,但也不是尽然,还是得视情况而定。


作者: Brisingr    时间: 2015-10-20 13:16
这个是黑马的面试题么?这么没有节操。。。
作者: jy00889669    时间: 2015-10-20 16:47
不懂真不懂
作者: p495416980    时间: 2015-10-20 19:45
我还没有理解字节中杂找二进制中的1,c不是汇编语言么?只要链接后才是指令语言有二进制组成,还是说用函数标识二进制数组,在这个模拟数组中查找
作者: sclea    时间: 2015-10-20 20:14
没有节操的面试题,还要手写,坑爹到无尽头
作者: wwf707542865    时间: 2015-10-20 20:27
首先,我就没看懂BYT是什么东西,
作者: 木亙。    时间: 2015-10-20 21:00
反正我是看不懂
作者: ruoruchujian641    时间: 2015-10-20 22:00
用空间复杂度换时间。。。。。而且  只能到255啊。。。。
作者: LDstruggling    时间: 2015-10-20 23:24
还没学这么深,感觉好难。。。
作者: knight_zfh1288    时间: 2015-10-21 00:06
加点注释就好了,真心看不懂啊
作者: wanglao5    时间: 2015-10-21 12:01
我完全看不懂,因为还没学到
作者: 陈流    时间: 2015-10-21 23:28
这么难吗

作者: 易沛东    时间: 2015-10-22 16:07
看了你的帖子,我与就业班的距离变更加遥远了.请问一次面试当中要面对多少道这样的题目,这个是算低难度还是高难度的?
作者: hulk374    时间: 2015-10-22 17:54
看来我不适合学C语言。。。
作者: hailiqh    时间: 2015-10-22 18:42
hulk374 发表于 2015-10-22 17:54
看来我不适合学C语言。。。

这样的面试题应该不多,先别否定自己
作者: liyang783    时间: 2015-10-22 20:09
不错,技术贴。这真是面试题?顶多能写出来第一种
作者: 孙明海    时间: 2015-10-22 20:38
真是牛  赞一个
作者: 孙明海    时间: 2015-10-22 20:41
空间换时间 我第一次见啊  好牛逼
作者: chensc    时间: 2015-10-22 20:47
学习学习!
作者: 杨奉泊    时间: 2015-10-22 21:15
int count(byte v)
{
  int num = 0;
  while(v)
  {
    if(v&1)
    {
       num++;
     }
    v = v>>1;
   }
  return num;
  }
这个对吗?
作者: 赵飞    时间: 2015-10-23 09:10
加上注释吧,boss看到你的程序会很生气。
作者: 洪吉童    时间: 2015-10-23 09:47
你面试通过了吗
作者: StillSad    时间: 2015-10-23 10:03
空间换时间,赞一个!
作者: 超の    时间: 2015-10-23 10:08
完全没看懂!!!
作者: 529548466    时间: 2015-10-23 21:29
看了 就晕了....................
作者: xu不是许    时间: 2015-10-23 22:06
面试题这么难吗???
作者: 菜鸟adambo    时间: 2015-10-23 22:22
不错要学习学习
作者: hm_pt    时间: 2015-10-24 01:15
看不懂,这个跟编程关系很大吗
作者: chensc    时间: 2015-10-24 10:48
学习学习!
作者: 小Who    时间: 2015-10-24 23:31
这么复杂,
作者: 黑马公公007    时间: 2015-10-31 12:28
已泪奔,,,,
作者: tsc0000    时间: 2015-10-31 12:45
数据结构里面的问题,
作者: p495416980    时间: 2015-10-31 12:48
看不懂,如果这是面试题,这个不会
作者: a578530825    时间: 2015-11-9 23:36
看不懂!!!
作者: 大雕会飞    时间: 2015-11-9 23:39
过来向大神学习{:2_43:}
作者: wh8817221    时间: 2015-11-10 01:19
看到这我瞬间醉了
作者: kongfq    时间: 2015-11-10 10:09
有点难度,看不懂。
作者: 韩三少    时间: 2015-11-10 10:12
学习一下
作者: 许本亮    时间: 2015-11-10 11:53
num += (byt & 0×01);
byt >>= 1;
这句没看懂,求解
作者: 于鸿鹏    时间: 2015-11-10 14:22
要是多来几个这样的题 那直接没戏了
作者: 勇猛的小黑    时间: 2015-11-10 16:36
不明觉厉
作者: 陌忆    时间: 2015-11-10 16:49
没看懂最后的那个表
作者: zhecipinle    时间: 2015-11-10 17:11
这是面试题?黑马的还是应聘公司,有点虚呀!
作者: jeffdy66    时间: 2015-11-10 21:55
这么屌的题目都有吗?  让菜鸟们咋整呢
作者: 李凯666    时间: 2015-11-20 22:53
这是什么啊?怎么这么复杂呢?
作者: 沐小妖mavs    时间: 2015-11-20 23:00
支持 顶下
作者: Newbee_123    时间: 2015-11-30 21:55
加点注释就好。。。
作者: 649685603    时间: 2015-11-30 22:30
反正我是看不懂
作者: fenghun1991    时间: 2015-11-30 22:46
不懂真不懂。。。
作者: 学习黑马精神    时间: 2015-12-1 07:20
难,到时候面试怎么办!
作者: caiyilong1992    时间: 2015-12-1 13:09
只想说  面试题这样的是够变态的。。。。
作者: 453702877    时间: 2015-12-1 13:18
这是面试题???
作者: liruixue    时间: 2015-12-1 15:46
表示只记得按位与这个方法了,受教了
作者: huqianqian    时间: 2015-12-1 17:16
谢谢分享
作者: Newbee_123    时间: 2015-12-1 22:08

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




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2