数学研发论坛

 找回密码
 欢迎注册
查看: 10476|回复: 62

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

[复制链接]
发表于 2009-2-4 17:53:08 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
一个数 0<=n<=4294967295, 当它表示为10进制数,求它的位数。
例:

n=0:返回0
n=1到9:返回1
n=10到99:返回2
n=100000000到999999999:返回9
n>999999999时,返回10

要求贴出代码,可以为x86汇编或者C语言。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 18:36:55 | 显示全部楼层
fldlg2
    fld1
    fild n
    fyl2x
    fdivp
    fistp m
    mov eax, n
    cmp eax, 0
    jne  exit1:
    inc m
exit1:
    mov eax, m
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 18:47:27 | 显示全部楼层
int DigitCount(unsigned long num)
{
    unsigned int i = 0;
    unsigned long boundary = 1;
   
    for (i = 0; i < 10; i++)
    {
        if (num < boundary) break;
        boundary *= 10;
    }
   
    return i;
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:01:41 | 显示全部楼层

  1. int digits(int n){
  2.    return (n>=1)+(n>=10)+(n>=100)+(n>=1000)+(n>=10000)+...+(n>=1000000000);
  3. }
复制代码

评分

参与人数 1经验 +1 鲜花 +1 收起 理由
无心人 + 1 + 1 精妙

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:13:20 | 显示全部楼层
楼上这个代码比较有意思。。。
不知编译器将会是如何优化它的?

但如果要判断一个UINT64的十进制位数,
就得出现20次判断了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:17:08 | 显示全部楼层
老大

   他这个代码是可以并行执行的
   所以,完全可以用SSE2来实现
   MMX也可以做
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-4 20:18:04 | 显示全部楼层

回复 5# gxqcn 的帖子

的确,判断越多,速度将越慢。对于这个问题,cpu无法对跳转指令进行分支预测。所有要想提高速度,唯一的办法是减少跳转指令。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:26:46 | 显示全部楼层
TO GxQ liangbch
根本用不到判断和跳转啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:36:25 | 显示全部楼层
考虑pcmpgtd
如果n大于10^k,则产生-1
将所有-1加在一起
取反就可以了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:41:39 | 显示全部楼层
初始化一个表
   t[] = {1, 10, 100, ...}
   
    mov eax, n
    mov edx, eax
    mov ecx, t
    movd mm0, eax
    movd mm7, edx
    psllq mm0, 32
    paddd mm0, mm7
    movq mm1, mm0
    movq mm2, mm0
    movq mm3, mm0
    movq mm4, mm0
   
    movq mm5, qword ptr [t]
    movq mm6, qword ptr [t + 8]
    movq mm7, qword ptr [t + 16]
   
    pcmpgtd mm0, mm5
    pcmpgtd mm1, mm6
    pcmpgtd mm2, mm7
   
    movq mm5, qword ptr [t + 24]
    movq mm6, qword ptr [t + 32]
   
    pcmpgtd mm3, mm5
    pcmpgtd mm4, mm6

    paddd mm0, mm1
    paddd mm2, mm3
    paddd mm0, mm4
    paddd mm0, mm2

    movd eax, mm0
    psrlq mm0, 32
    movd edx, mm0
    add eax, edx
    neg eax
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-12 07:03 , Processed in 0.064362 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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