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) |