学习计算机科学与技术专业，喜欢计算机，喜欢linux，喜欢编程
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： c/c
2013-10-14 18:33:04
这是我最近看《编程之美》那本书上的一个例子，和大家分享下我的理解。
这个题目其实不难，但是这个题目要求算法的执行效率尽可能高。什么才是高效率的算法呢？很模糊，你的算法也许还是会被更高效的算法给 pass掉。下面是我对这道题算法的总结，不能说是很高效的，但是也算不错了。
解法一：我们都知道，用这个数数以一个 2 ，原来的数字将会减少一个 0 。如果在除的过程中 有余数，那么就表示当前位置有一个 1 。
以 100011010 为例：
第一次除以 2 时，商为 10001101，余数为 0；
第二次除以 2 时，商为 1000110 ，余数为 1；
利用这个特点我们可以编写大概的代码如下：
-
int count(byte v)
-
{
-
int num = 0;
-
while (v)
-
{
-
if (v % 2 == 1)
-
{
-
num;
-
}
-
v = v / 2;
-
}
-
return num;
- }
这种算法的效率怎么样呢？
解法二：通过上面的算法，我们可以看出，利用向右移位操作也可以实现这个过程，当然了，位运算的效率更高些。代码实现如下：
-
int count(bype v)
-
{
-
int num = 0;
-
while (v)
-
{
-
num = v & 0x01;
-
v >>= 1;
-
}
-
return num;
- }
解法三：位运算的效率明显高于解法一，但是采用位操作，时间复杂度还是o(logv) 。logv是二进制数的位数。如果有办法让算法的复杂度只与“1”的个数有关，那么时间复杂度应该会降低一些。
为了简化这个问题，我们考虑只有一个“1”的情况，例如：00100000。
如何判断给定的二进制数里面有且只有一个“1”呢？可以通过判断这个数是否是 2 的整数次幂来实现。如果只和这一个“1”进行判断，结果为 0 或者 1 。所以如果进行这个操作后的结果为 0 ，00100000可以和00011111进行“与”操作。
这个算法又怎样设计呢？
-
int count(byte v)
-
{
-
int num = 0;
-
while (v)
-
{
-
v &= (v - 1);
-
num;
-
}
-
return num;
- }
解法四：当然了，如果你要是只针对八位进制的数据我们可以用分支法来实现，具体代码如下：
-
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;
- }
解法五：这个解法效率也很好，是在看了我同学的博客后写的。代码如下：
-
int bit_count(unsigned int x )
-
{
-
static unsigned int mask[] = { 0x55555555,
-
0x33333333,
-
0x0f0f0f0f,
-
0x00ff00ff,
-
0x0000ffff };
-
int i;
-
int shift; /* number of positions to shift to right */
-
-
for( i=0, shift=1; i < 5; i, shift *= 2 )
-
x = (x & mask[i]) ( (x >> shift) & mask[i] );
-
return x;
- }
以上是一个比较小的问题，但是对问题的深入思考可以给我们很多启示。
博文链接是：