Chinaunix首页 | 论坛 | 博客
  • 博客访问: 21515
  • 博文数量: 2
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 11
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-13 23:33
文章分类
文章存档

2013年(2)

我的朋友
最近访客

分类: C/C++

2013-07-13 23:43:24

今儿在网上看到这样一个似曾相识的算法题,有点儿想法,觉得值得回味,马上记下来:

题目描述:对于一个字节(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的个数”角度去想的,却没有从
“怎么用空间上的开销去换取时间上的开销,在空间允许的情况下达到最快的效率”。

大家如果有什么相似的案例,希望能拿出来分享分享。^_^

阅读(1514) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:Linux系统信息查看命令大全

给主人留下些什么吧!~~