论坛 › 编程擂台 › 求一个无符号整数的10进制位数

liangbch 发表于 2009-2-4 17:53:08

求一个无符号整数的10进制位数

一个数 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
    jneexit1:
    inc m
exit1:
    mov eax, m

g99 发表于 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;
}

mathe 发表于 2009-2-4 20:01:41

int digits(int n){
   return (n>=1)+(n>=10)+(n>=100)+(n>=1000)+(n>=10000)+...+(n>=1000000000);
}

gxqcn 发表于 2009-2-4 20:13:20

楼上这个代码比较有意思。。。:)
不知编译器将会是如何优化它的？:Q:

但如果要判断一个UINT64的十进制位数，
就得出现20次判断了。

无心人 发表于 2009-2-4 20:17:08

老大

   他这个代码是可以并行执行的
   所以，完全可以用SSE2来实现
   MMX也可以做

liangbch 发表于 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
    movq mm6, qword ptr
    movq mm7, qword ptr
   
    pcmpgtd mm0, mm5
    pcmpgtd mm1, mm6
    pcmpgtd mm2, mm7
   
    movq mm5, qword ptr
    movq mm6, qword ptr
   
    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

查看完整版本: 求一个无符号整数的10进制位数