算法题一道,欢迎讨论(修订版)

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编译优化捣的鬼，有兴趣的请看下篇帖子。