数学研发论坛

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

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

[复制链接]
发表于 2009-2-4 20:42:34 | 显示全部楼层
?

帖子呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:44:06 | 显示全部楼层
mathe 的代码体现了一种算法思路,
最终的机器代码当然是可以避免跳转的。

那如果是 64 位呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 20:53:32 | 显示全部楼层


  我在10#给出了一个思路
  MMX汇编
  如果是64位的,应该还能用SSE
  无跳转,无判断
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 21:00:47 | 显示全部楼层
感觉还是尽量避免用MMX,
用SIMD指令因更高效,
因为这次不比上次的 UInt64x64To128() 那样需要反复拆包了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 21:04:26 | 显示全部楼层
你怎么老排斥MMX啊

不支持 MMX的机器已经不存在了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-4 21:06:06 | 显示全部楼层
我这里给出一个不是用 MMX和XMM指令的版本,使用跳表实现。因为VC中不可以定义标号的地址。故不得不使用汇编文件。
   在VC6.0,对于汇编文件,可以自定义build命令,在编译期间同时编译asm文件,为此,你需要
  1。安装masm32
    2.  在VC 中,设置 executable files 目录,指向ml.exe, 比如我的masm32 安装在 c:\masm32,因此executable files目录中添加 C:\masm32\BIN
   3. 在VC中,将asm文件添加到project.并选中那个asm文件,设置Custom Build
Commands 框填入:  ml /coff /c $(InputPath)
outputs 框填入: $(InputName).obj
下面先给出cpp文件中的测试代码:
  1. extern "C" _fastcall  int digLen(int n);
  2. void digLenTest()
  3. {
  4. unsigned long n;

  5. n=1;
  6. printf("diglen(%u)=%d\n",n,digLen(n));
  7. n=7;
  8. printf("diglen(%u)=%d\n",n,digLen(n));

  9. n=8;
  10. printf("diglen(%u)=%d\n",n,digLen(n));
  11. n=9;
  12. printf("diglen(%u)=%d\n",n,digLen(n));
  13. n=10;
  14. printf("diglen(%u)=%d\n",n,digLen(n));
  15. n=99;
  16. printf("diglen(%u)=%d\n",n,digLen(n));

  17. n=100;
  18. printf("diglen(%u)=%d\n",n,digLen(n));
  19. n=1000;
  20. printf("diglen(%u)=%d\n",n,digLen(n));

  21. n=9999;
  22. printf("diglen(%u)=%d\n",n,digLen(n));
  23. n=10000;
  24. printf("diglen(%u)=%d\n",n,digLen(n));

  25. n=99999;
  26. printf("diglen(%u)=%d\n",n,digLen(n));
  27. n=100000;
  28. printf("diglen(%u)=%d\n",n,digLen(n));
  29. }
复制代码
再给出汇编文件中的代码:

  1.         .486P
  2.         .387
  3.         OPTION DOTNAME
  4. _TEXT        SEGMENT DWORD PUBLIC FLAT 'CODE'
  5.         ALIGN 004H
  6. _TEXT        ENDS

  7. _DATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
  8.         ALIGN 004H
  9. _DATA        ENDS

  10. _BSS        SEGMENT DWORD PUBLIC FLAT 'BSS'
  11.         ALIGN 004H
  12. _BSS        ENDS

  13. _RDATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
  14.         ALIGN 004H
  15. _RDATA        ENDS

  16. _TEXT1        SEGMENT DWORD PUBLIC FLAT 'CODE'
  17.         ALIGN 004H
  18. _TEXT1        ENDS

  19. _DATA1        SEGMENT DWORD PUBLIC FLAT 'DATA'
  20.         ALIGN 004H
  21. _DATA1        ENDS

  22.         ASSUME        CS:FLAT,DS:FLAT,SS:FLAT
  23. _DATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
  24. _DATA        ENDS


  25. _TEXT        SEGMENT DWORD PUBLIC FLAT 'CODE'
  26.     ALIGN     4
  27.         PUBLIC @digLen@4

  28. @digLen@4 PROC NEAR
  29.         test        ecx, ecx
  30.         jne        SHORT L919
  31.         xor        eax, eax
  32.         ret

  33. L919:
  34.         bsr eax,ecx
  35.         jmp        DWORD PTR JTAB_1004[eax*4]

  36. L_012:
  37.         mov        eax, 1
  38.         ret

  39. L_3:
  40.         cmp        ecx, 10                                       
  41.         sbb        eax, eax
  42.         add        eax, 2
  43.         ret

  44. L_45:
  45.         mov        eax, 2
  46.         ret

  47. L_6:
  48.         cmp        ecx, 100                               
  49.         sbb        eax, eax
  50.         add        eax, 3
  51.         ret

  52. L_78:
  53.         mov        eax, 3
  54.         ret

  55. L_9:
  56.         cmp        ecx, 1000                               
  57.         sbb        eax, eax
  58.         add        eax, 4
  59.         ret

  60. L936:
  61.         mov        eax, 4
  62.         ret

  63. L938:
  64.         cmp        ecx, 10000
  65.         sbb        eax, eax
  66.         add        eax, 5
  67.         ret

  68. L940:
  69.         mov        eax, 5
  70.         ret

  71. L942:
  72.         cmp        ecx, 100000
  73.         sbb        eax, eax
  74.         add        eax, 6
  75.         ret

  76. L944:
  77.         mov        eax, 6
  78.         ret

  79. L946:
  80.         cmp        ecx, 1000000
  81.         sbb        eax, eax
  82.         add        eax, 7
  83.         ret

  84. L948:
  85.         mov        eax, 7
  86.         ret

  87. L950:
  88.         cmp        ecx, 10000000
  89.         sbb        eax, eax
  90.         add        eax, 8
  91.         ret
  92. L952:
  93.         mov        eax, 8
  94.         ret

  95. L954:
  96.         cmp        ecx, 100000000                               
  97.         sbb        eax, eax
  98.         add        eax, 9
  99.         ret

  100. L956:
  101.         mov        eax, 9
  102.         ret

  103. L958:
  104.         cmp        ecx, 1000000000
  105.         sbb        eax, eax
  106.         add        eax, 10                                       
  107.         ret

  108. L960:
  109.         mov        eax, 10                                       
  110.         ret
  111.        
  112.         align 4
  113. JTAB_1004:
  114.         DD         L_012 ;0
  115.         DD         L_012 ;1
  116.         DD         L_012 ;2
  117.        
  118.         DD         L_3        ;3
  119.        
  120.         DD        L_45        ;4
  121.         DD        L_45        ;5
  122.        
  123.         DD        L_6        ;6
  124.                
  125.         DD        L_78        ;7
  126.         DD        L_78        ;8
  127.        
  128.         DD        L_9        ;9
  129.        
  130.         DD        L936        ;10
  131.         DD        L936        ;11
  132.         DD        L936        ;12
  133.        
  134.         DD        L938        ;13
  135.        
  136.         DD        L940        ;14
  137.         DD        L940        ;15
  138.        
  139.         DD        L942        ;16
  140.        
  141.         DD        L944        ;17
  142.         DD        L944        ;18
  143.        
  144.         DD        L946        ;19
  145.        
  146.         DD        L948        ;20
  147.         DD        L948        ;21
  148.         DD        L948        ;22
  149.        
  150.        
  151.         DD        L950        ;23
  152.        
  153.         DD        L952        ;24
  154.         DD        L952        ;25
  155.        
  156.         DD        L954        ;26
  157.                        
  158.         DD        L956        ;27
  159.         DD        L956        ;28
  160.        
  161.         DD        L958        ;29
  162.        
  163.         DD        L960        ;30
  164.         DD        L960        ;31
  165.         ret        0

  166. @digLen@4 ENDP
  167. _TEXT        ENDS
  168. END
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 21:11:21 | 显示全部楼层


   不懂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-4 21:15:39 | 显示全部楼层
给你一段等价的C代码,你就明白了。

以上的汇编代码即为在编译器编译后的汇编代码的基础上优化(精简)而成.
  1. int log2(int n)
  2. {
  3.         _asm
  4.         {
  5.                 mov ecx,n
  6.                 bsr eax,ecx
  7.         }
  8. }

  9. extern "C"
  10. _fastcall
  11. int digLen(int n)
  12. {
  13.         if (n==0)
  14.                 return 0;

  15.         int c=log2(n);
  16.         switch (c)
  17.         {
  18.         case 0:
  19.         case 1:
  20.         case 2:
  21.                 return 1;
  22.         case 3:
  23.                 if (n>=10)
  24.                         return 2;
  25.                 else
  26.                         return 1;
  27.         case 4:
  28.         case 5:
  29.                 return 2;
  30.         case 6:
  31.                 if (n>=100)
  32.                         return 3;
  33.                 else
  34.                         return 2;
  35.         case 7:
  36.         case 8:
  37.                 return 3;
  38.         case 9:
  39.                 if (n>=1000)
  40.                         return 4;
  41.                 else
  42.                         return 3;
  43.         case 10:
  44.         case 11:
  45.         case 12:
  46.                 return 4;
  47.        
  48.         case 13:
  49.                 if (n>=10000)
  50.                         return 5;
  51.                 else
  52.                         return 4;

  53.         case 14:
  54.         case 15:
  55.                 return 5;

  56.         case 16:
  57.                 if (n>=100000)
  58.                         return 6;
  59.                 else
  60.                         return 5;
  61.         case 17:
  62.         case 18:
  63.                 return 6;
  64.         case 19:
  65.                 if (n>=1000000)
  66.                         return 7;
  67.                 else
  68.                         return 6;
  69.         case 20:
  70.         case 21:
  71.         case 22:
  72.                 return 7;

  73.         case 23:
  74.                 if (n>=10000000)
  75.                         return 8;
  76.                 else
  77.                         return 7;
  78.         case 24:
  79.         case 25:
  80.                 return 8;
  81.         case 26:
  82.                 if (n>=100000000)
  83.                         return 9;
  84.                 else
  85.                         return 8;
  86.         case 27:
  87.         case 28:
  88.                         return 9;
  89.         case 29:
  90.                         if (n>=1000000000)
  91.                         return 10;
  92.                 else
  93.                         return 9;
  94.         case 30:
  95.         case 31:
  96.                 return 10;
  97.         }
  98. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 21:17:13 | 显示全部楼层
这么做也可以啊
    mov edx, n
    xor eax, eax
    cmp edx, 1   //1
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 10  //2
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 100 //3
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 1000 //4
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 10000 //5
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 100000 //6
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 1000000 //7
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 10000000 //8
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 100000000 //9
    sbb ecx, ecx
    sub eax, ecx
    cmp edx, 1000000000 //10
    sbb ecx, ecx
    sub eax, ecx
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-4 21:23:13 | 显示全部楼层
原帖由 无心人 于 2009-2-4 21:04 发表
你怎么老排斥MMX啊

不支持 MMX的机器已经不存在了


我不是排斥它,而是反感它需要 emms 来擦屁股。
另外用 SIMD 指令一次就可进行4组32位的比较,多么爽啊。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-25 23:16 , Processed in 0.081769 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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