数学研发论坛

 找回密码
 欢迎注册
楼主: liangbch

[擂台] 求一个无符号整数的10进制位数

[复制链接]
发表于 2009-2-5 10:29:47 | 显示全部楼层
18#  liangbch 的程序,最差情况也就执行这么几句,恐怕很难优化了
bsr eax,ecx
jmp  DWORD PTR JTAB_1004[eax*4]
cmp  ecx, 100                              
sbb  eax, eax
add  eax, 3
ret

但是,在平均意义下,4294967295个数中有
3294967296 个返回 10
900000000  个返回 9
90000000   个返回 8
9000000    个返回 7
900000     个返回 6
90000      个返回 5
9000       个返回 4
900        个返回 3
90         个返回 2
9          个返回 1
于是,将19#无心人的顺序倒过来,假设每多判断一层多3条指令,以指令条数计算复杂性有:
平均复杂性 = (3294967296*3+900000000*6+90000000*9+9000000*12+900000*15+90000*18+9000*21+900*24+90*27+9*30)/4294967295=3.8
也不差呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 10:57:43 | 显示全部楼层
呵呵

谁有兴趣比较下时间差异????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 13:45:00 | 显示全部楼层
我不知道怎么算位数
我只知道按计算器int(log10(n))+1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 14:16:50 | 显示全部楼层
呵呵

以后不能和 shshsh_0510以及mathe 一起论问题
什么问题都要计算这么精确
很理智的说
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 13:40:49 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 14:14:25 | 显示全部楼层
呵呵

锅老大提供的连接上面的算法,似乎并不比我们实现的有多好啊

64位的也能用我提供的查表法(根据宝宝的算法)解决,不过要用SSE2了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 14:22:21 | 显示全部楼层
呵呵
   不过64位的不跳转的可就难了啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 14:29:40 | 显示全部楼层
呵呵

    不知道VC2008支持跳转表么?
    马上测试去
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 14:37:08 | 显示全部楼层
#include "stdafx.h"

int JmpTest(void)
{
  __asm
  {
   mov eax, 1
   mov edx, jmp1
   jmp edx
jmp1:
   mov ecx, 2
   jmp exit1
jmp2:
   mov ecx, 3
   jmp exit1
exit1:
   mov eax, ecx
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
printf("%d\n", JmpTest());
return 0;
}
===================================
可以通过编译,也能执行!!!!
现在去做真正的跳转表!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-6 14:48:17 | 显示全部楼层
/ JmpTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

int JmpTest(void)
{
  __asm
  {
   mov eax, 1
   mov edx, jmpTable
   mov ecx, 2
   add edx, ecx
   jmp edx
jmpTable:
   jmp jmp1
   jmp jmp2
jmp1:
   mov ecx, 2
   jmp exit1
jmp2:
   mov ecx, 3
   jmp exit1
exit1:
   mov eax, ecx
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
printf("%d\n", JmpTest());
return 0;
}

================================
VC2008, 真正的跳转表, 也可编译,可执行
但现在问题是当前的标号都是短标号(偏移在-128 -- 127内)
所以jmp表指令都是2字节的
不知道,长汇编是否有差异
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-23 21:08 , Processed in 0.055002 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表