Chinaunix首页 | 论坛 | 博客
  • 博客访问: 792769
  • 博文数量: 155
  • 博客积分: 4056
  • 博客等级: 上校
  • 技术积分: 1531
  • 用 户 组: 普通用户
  • 注册时间: 2005-11-04 14:46
文章分类

全部博文(155)

文章存档

2011年(4)

2010年(4)

2009年(44)

2008年(36)

2007年(34)

2006年(28)

2005年(5)

我的朋友

分类: C/C++

2008-09-04 01:03:11

CU上看到,趁开会无聊,做了一下,随便写写,应该还有很大优化的余地。代码如下:

#include <stdio.h>

int get_step( unsigned long num )
{
    int i, j, step, high, count;
    for (step = high = count = i = 0, j = sizeof(num) << 3; i < j; i++) {
        if (num & (1 << i)) {
            high = i;
            count++;
        } else {
            if (count > 2) {
                high = i;
                step++;
                count = 1;
            } else {
                step += count;
                count = 0;
            }
        }
    }
    if (count > 2) {
        high++;
        step++;
    } else {
        step += count - 1;
    }
    return high + step;
}

int main( int argc, char* argv[] )
{
    unsigned long num;

    if (1 == argc || !(num = strtoul (argv[1], NULL, 10))) {
        fprintf (stderr, "Usage: %s number(>0)\n", argv[0]);
        return -1;
    }

    printf ("Number %u need %d steps to get 1\n", num, get_step (num));

    return 0;
}



修正:

第一位留言的网友指出上述算法存在问题,确实,主要是忽视了对011这种模式的处理,修改后的代码如下:

#include <stdio.h>

int get_step( unsigned long num )

{

int i, j, step, high, count, tag;

for (tag = step = high = count = i = 0, j = sizeof(num) << 3; i < j; i++) {

if (num & (1 << i)) {

high = i;

count++;

if (tag) {

tag = 0;

}

} else {

if (count > 1) {

high = i;

step++;

if (2 == count) {

tag = 1;

}

count = 1;

} else if (count) {

step++;

count = 0;

}

}

}

if (count > 2) {

high++;

step++;

} else {

step += count - 1;

}

return high + step - tag;

}


int main( int argc, char* argv[] )
{
    unsigned long num;

    if (1 == argc) {
        fprintf (stderr, "Usage: %s number\n", argv[0]);
        return -1;
    }

    num = strtoul (argv[1], NULL, 10);
    printf ("Number %u need %d steps to get 1\n", num, get_step (num));

    return 0;
}


注:
1)遍历了一遍0到0xFFFFFFFF,和留言一的算法结果一致(除了0和0xFFFFFFFF,留言一的算法不能正确处理这两个边界值:))
2)性能比留言一的算法要高不少:)
3)想了一下,暂时没什么优化的思路
4)有些同学可能比较关注证明,其实只要理解了get_step()的代码,证明就是平凡的。主要就是分类讨论。

再注:
我在测试(通过程序跑遍全部32位的正整数)中得到了上述注2的结论,一直在奇怪原因何在,因为从算法本身看这两个算法不应有本质差别,但没时间细究原因。今天论坛里有人贴了个算法B,我测了一下比我的效率略差些,但基本一致,但刚才发现下面又有人跟贴说算法B比某个算法慢20%左右。因为之前在原帖子里来看到的唯一正确算法就是留言一的算法,故我有理由相信该跟贴者指的就是留言一算法,显然这和上述注2的结果完全不同,这终于让我忍不住疑惑了。于是花时间反汇编看了一下我的测试程序,发现原来是VC编译优化捣的鬼,有兴趣的请看下篇帖子
阅读(2563) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~