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

无心人

?

帖子呢？

gxqcn

mathe 的代码体现了一种算法思路，
最终的机器代码当然是可以避免跳转的。

那如果是 64 位呢？

无心人

  我在10#给出了一个思路
  MMX汇编
  如果是64位的，应该还能用SSE
  无跳转，无判断

gxqcn

感觉还是尽量避免用MMX，
用SIMD指令因更高效，
因为这次不比上次的 UInt64x64To128() 那样需要反复拆包了。

无心人

你怎么老排斥MMX啊

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

liangbch

我这里给出一个不是用 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. 
   
6. n=1;
   
7. printf("diglen(%u)=%d\n",n,digLen(n));
   
8. n=7;
   
9. printf("diglen(%u)=%d\n",n,digLen(n));
   
10. 
    
11. n=8;
    
12. printf("diglen(%u)=%d\n",n,digLen(n));
    
13. n=9;
    
14. printf("diglen(%u)=%d\n",n,digLen(n));
    
15. n=10;
    
16. printf("diglen(%u)=%d\n",n,digLen(n));
    
17. n=99;
    
18. printf("diglen(%u)=%d\n",n,digLen(n));
    
19. 
    
20. n=100;
    
21. printf("diglen(%u)=%d\n",n,digLen(n));
    
22. n=1000;
    
23. printf("diglen(%u)=%d\n",n,digLen(n));
    
24. 
    
25. n=9999;
    
26. printf("diglen(%u)=%d\n",n,digLen(n));
    
27. n=10000;
    
28. printf("diglen(%u)=%d\n",n,digLen(n));
    
29. 
    
30. n=99999;
    
31. printf("diglen(%u)=%d\n",n,digLen(n));
    
32. n=100000;
    
33. printf("diglen(%u)=%d\n",n,digLen(n));
    
34. }

复制代码

再给出汇编文件中的代码：

1. 
   
2.         .486P
   
3.         .387
   
4.         OPTION DOTNAME
   
5. _TEXT        SEGMENT DWORD PUBLIC FLAT 'CODE'
   
6.         ALIGN 004H
   
7. _TEXT        ENDS
   
8. 
   
9. _DATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
   
10.         ALIGN 004H
    
11. _DATA        ENDS
    
12. 
    
13. _BSS        SEGMENT DWORD PUBLIC FLAT 'BSS'
    
14.         ALIGN 004H
    
15. _BSS        ENDS
    
16. 
    
17. _RDATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
    
18.         ALIGN 004H
    
19. _RDATA        ENDS
    
20. 
    
21. _TEXT1        SEGMENT DWORD PUBLIC FLAT 'CODE'
    
22.         ALIGN 004H
    
23. _TEXT1        ENDS
    
24. 
    
25. _DATA1        SEGMENT DWORD PUBLIC FLAT 'DATA'
    
26.         ALIGN 004H
    
27. _DATA1        ENDS
    
28. 
    
29.         ASSUME        CS:FLAT,DS:FLAT,SS:FLAT
    
30. _DATA        SEGMENT DWORD PUBLIC FLAT 'DATA'
    
31. _DATA        ENDS
    
32. 
    
33. 
    
34. _TEXT        SEGMENT DWORD PUBLIC FLAT 'CODE'
    
35.     ALIGN     4
    
36.         PUBLIC @digLen@4
    
37. 
    
38. @digLen@4 PROC NEAR
    
39.         test        ecx, ecx
    
40.         jne        SHORT L919
    
41.         xor        eax, eax
    
42.         ret
    
43. 
    
44. L919:
    
45.         bsr eax,ecx
    
46.         jmp        DWORD PTR JTAB_1004[eax*4]
    
47. 
    
48. L_012:
    
49.         mov        eax, 1
    
50.         ret
    
51. 
    
52. L_3:
    
53.         cmp        ecx, 10                                       
    
54.         sbb        eax, eax
    
55.         add        eax, 2
    
56.         ret
    
57. 
    
58. L_45:
    
59.         mov        eax, 2
    
60.         ret
    
61. 
    
62. L_6:
    
63.         cmp        ecx, 100                               
    
64.         sbb        eax, eax
    
65.         add        eax, 3
    
66.         ret
    
67. 
    
68. L_78:
    
69.         mov        eax, 3
    
70.         ret
    
71. 
    
72. L_9:
    
73.         cmp        ecx, 1000                               
    
74.         sbb        eax, eax
    
75.         add        eax, 4
    
76.         ret
    
77. 
    
78. L936:
    
79.         mov        eax, 4
    
80.         ret
    
81. 
    
82. L938:
    
83.         cmp        ecx, 10000
    
84.         sbb        eax, eax
    
85.         add        eax, 5
    
86.         ret
    
87. 
    
88. L940:
    
89.         mov        eax, 5
    
90.         ret
    
91. 
    
92. L942:
    
93.         cmp        ecx, 100000
    
94.         sbb        eax, eax
    
95.         add        eax, 6
    
96.         ret
    
97. 
    
98. L944:
    
99.         mov        eax, 6
    
100.         ret
     
101. 
     
102. L946:
     
103.         cmp        ecx, 1000000
     
104.         sbb        eax, eax
     
105.         add        eax, 7
     
106.         ret
     
107. 
     
108. L948:
     
109.         mov        eax, 7
     
110.         ret
     
111. 
     
112. L950:
     
113.         cmp        ecx, 10000000
     
114.         sbb        eax, eax
     
115.         add        eax, 8
     
116.         ret
     
117. L952:
     
118.         mov        eax, 8
     
119.         ret
     
120. 
     
121. L954:
     
122.         cmp        ecx, 100000000                               
     
123.         sbb        eax, eax
     
124.         add        eax, 9
     
125.         ret
     
126. 
     
127. L956:
     
128.         mov        eax, 9
     
129.         ret
     
130. 
     
131. L958:
     
132.         cmp        ecx, 1000000000
     
133.         sbb        eax, eax
     
134.         add        eax, 10                                       
     
135.         ret
     
136. 
     
137. L960:
     
138.         mov        eax, 10                                       
     
139.         ret
     
140.        
     
141.         align 4
     
142. JTAB_1004:
     
143.         DD         L_012 ;0
     
144.         DD         L_012 ;1
     
145.         DD         L_012 ;2
     
146.        
     
147.         DD         L_3        ;3
     
148.        
     
149.         DD        L_45        ;4
     
150.         DD        L_45        ;5
     
151.        
     
152.         DD        L_6        ;6
     
153.                
     
154.         DD        L_78        ;7
     
155.         DD        L_78        ;8
     
156.        
     
157.         DD        L_9        ;9
     
158.        
     
159.         DD        L936        ;10
     
160.         DD        L936        ;11
     
161.         DD        L936        ;12
     
162.        
     
163.         DD        L938        ;13
     
164.        
     
165.         DD        L940        ;14
     
166.         DD        L940        ;15
     
167.        
     
168.         DD        L942        ;16
     
169.        
     
170.         DD        L944        ;17
     
171.         DD        L944        ;18
     
172.        
     
173.         DD        L946        ;19
     
174.        
     
175.         DD        L948        ;20
     
176.         DD        L948        ;21
     
177.         DD        L948        ;22
     
178.        
     
179.        
     
180.         DD        L950        ;23
     
181.        
     
182.         DD        L952        ;24
     
183.         DD        L952        ;25
     
184.        
     
185.         DD        L954        ;26
     
186.                        
     
187.         DD        L956        ;27
     
188.         DD        L956        ;28
     
189.        
     
190.         DD        L958        ;29
     
191.        
     
192.         DD        L960        ;30
     
193.         DD        L960        ;31
     
194.         ret        0
     
195. 
     
196. @digLen@4 ENDP
     
197. _TEXT        ENDS
     
198. END
     

复制代码

无心人

   不懂

liangbch

给你一段等价的C代码，你就明白了。

以上的汇编代码即为在编译器编译后的汇编代码的基础上优化(精简)而成.

1. int log2(int n)
   
2. {
   
3.         _asm
   
4.         {
   
5.                 mov ecx,n
   
6.                 bsr eax,ecx
   
7.         }
   
8. }
   
9. 
   
10. extern "C"
    
11. _fastcall
    
12. int digLen(int n)
    
13. {
    
14.         if (n==0)
    
15.                 return 0;
    
16. 
    
17.         int c=log2(n);
    
18.         switch (c)
    
19.         {
    
20.         case 0:
    
21.         case 1:
    
22.         case 2:
    
23.                 return 1;
    
24.         case 3:
    
25.                 if (n>=10)
    
26.                         return 2;
    
27.                 else
    
28.                         return 1;
    
29.         case 4:
    
30.         case 5:
    
31.                 return 2;
    
32.         case 6:
    
33.                 if (n>=100)
    
34.                         return 3;
    
35.                 else
    
36.                         return 2;
    
37.         case 7:
    
38.         case 8:
    
39.                 return 3;
    
40.         case 9:
    
41.                 if (n>=1000)
    
42.                         return 4;
    
43.                 else
    
44.                         return 3;
    
45.         case 10:
    
46.         case 11:
    
47.         case 12:
    
48.                 return 4;
    
49.        
    
50.         case 13:
    
51.                 if (n>=10000)
    
52.                         return 5;
    
53.                 else
    
54.                         return 4;
    
55. 
    
56.         case 14:
    
57.         case 15:
    
58.                 return 5;
    
59. 
    
60.         case 16:
    
61.                 if (n>=100000)
    
62.                         return 6;
    
63.                 else
    
64.                         return 5;
    
65.         case 17:
    
66.         case 18:
    
67.                 return 6;
    
68.         case 19:
    
69.                 if (n>=1000000)
    
70.                         return 7;
    
71.                 else
    
72.                         return 6;
    
73.         case 20:
    
74.         case 21:
    
75.         case 22:
    
76.                 return 7;
    
77. 
    
78.         case 23:
    
79.                 if (n>=10000000)
    
80.                         return 8;
    
81.                 else
    
82.                         return 7;
    
83.         case 24:
    
84.         case 25:
    
85.                 return 8;
    
86.         case 26:
    
87.                 if (n>=100000000)
    
88.                         return 9;
    
89.                 else
    
90.                         return 8;
    
91.         case 27:
    
92.         case 28:
    
93.                         return 9;
    
94.         case 29:
    
95.                         if (n>=1000000000)
    
96.                         return 10;
    
97.                 else
    
98.                         return 9;
    
99.         case 30:
    
100.         case 31:
     
101.                 return 10;
     
102.         }
     
103. }

复制代码

无心人

这么做也可以啊
    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

gxqcn

原帖由 无心人 于 2009-2-4 21:04 发表
你怎么老排斥MMX啊

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

我不是排斥它，而是反感它需要 emms 来擦屁股。
另外用 SIMD 指令一次就可进行4组32位的比较，多么爽啊。