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

liangbch

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

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

要求贴出代码，可以为x86汇编或者C语言。

无心人

fldlg2
    fld1
    fild n
    fyl2x
    fdivp
    fistp m
    mov eax, n
    cmp eax, 0
    jne  exit1:
    inc m
exit1:
    mov eax, m

g99

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

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

复制代码

gxqcn

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

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

无心人

老大

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

liangbch

的确，判断越多，速度将越慢。对于这个问题，cpu无法对跳转指令进行分支预测。所有要想提高速度，唯一的办法是减少跳转指令。

无心人

TO GxQ liangbch
根本用不到判断和跳转啊

无心人

考虑pcmpgtd
如果n大于10^k，则产生-1
将所有-1加在一起
取反就可以了

无心人

初始化一个表
   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