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编译优化捣的鬼，有兴趣的请看
下篇帖子。
阅读(2772) | 评论(8) | 转发(0) |
