10^n的二进制表示

无心人

对乘以10的测试表明
在Core 2 XEON /1.6上重复10^9次
两者均是5s， 移位操作稍微多点

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <sys/time.h>
   
5. 
   
6. int d[1000000];
   
7. 
   
8. int main(void)
   
9. {
   
10.   int i, j, k;
    
11.   double t;
    
12.   struct timeval start, end;
    
13. 
    
14.   for (i = 0; i < 1000000; i ++)
    
15.     d[i] = i << 8;
    
16.   
    
17.   gettimeofday(&start, NULL);
    
18.   for (j = 0; j < 1000; j ++)
    
19.   for (i = 0; i < 1000000; i ++)
    
20.   {
    
21.     d[i] = d[i] * 10;
    
22.   }
    
23.   gettimeofday(&end, NULL);  
    
24.   
    
25.   t = (end.tv_sec - start.tv_sec) * 1.0 + (end.tv_usec - start.tv_usec) / 100000000.0;
    
26.   printf("* : %4.6f\n", t);
    
27. 
    
28.   gettimeofday(&start, NULL);
    
29.   for (j = 0; j < 1000; j ++)
    
30.   for (i = 0; i < 1000000; i ++)
    
31.   {
    
32.     d[i] = d[i] << 3 + d[i] << 1;
    
33.   }
    
34.   gettimeofday(&end, NULL);  
    
35.   
    
36.   t = (end.tv_sec - start.tv_sec) * 1.0 + (end.tv_usec - start.tv_usec) / 100000000.0;
    
37.   printf("<< %4.6f\n", t);
    
38. 
    
39. }
    

复制代码

E:\MinGW\MSYS\math>mul10
* : 5.006406
<< 6.000781

E:\MinGW\MSYS\math>mul10
* : 5.995781
<< 6.000625

E:\MinGW\MSYS\math>mul10
* : 5.995938
<< 6.001250

E:\MinGW\MSYS\math>mul10
* : 5.996094
<< 6.001406

无心人

* 100和 << 6 + << 5 + << 2比较
E:\MinGW\MSYS\math>mul10
* : 6.002344
<< 6.997813

E:\MinGW\MSYS\math>mul10
* : 6.002500
<< 6.997813

E:\MinGW\MSYS\math>mul10
* : 6.002500
<< 6.997813

mathe

编译器也可能将乘法进行优化的

无心人

* 1000
<< 10 - << 4 - << 3
E:\MinGW\MSYS\math>mul10
* : 6.996250
<< 6.007813

E:\MinGW\MSYS\math>mul10
* : 6.006250
<< 6.997813

E:\MinGW\MSYS\math>mul10
* : 6.006406
<< 6.997656

无心人

在*10000   <<13 + <<11 -<<8 + <<4时
移位开始超越乘法
E:\MinGW\MSYS\math>mul10
* : 9.000156
<< 8.996250

E:\MinGW\MSYS\math>mul10
* : 9.000937
<< 8.006562

E:\MinGW\MSYS\math>mul10
* : 9.000312
<< 8.996250

E:\MinGW\MSYS\math>mul10
* : 9.000312
<< 8.996562

gxqcn

编译器对于常数的乘除法确实可能智能优化，
但对于大整数的整体优化应该不会。
（我的意思是 M*10 <-- (M<<3)+(M<<1)，M 为大整数）

无心人

是关闭优化设置的
而且，你看程序
编译器很难优化掉乘法的

mathe

原帖由 无心人 于 2009-1-12 11:48 发表
在*10000   

这个结果不说明任何问题。测量结果应该完全由误差引起（注意Windows下通常时钟精度也就是20毫秒），甚至有可能两端代码编译器优化后完全类似

kofeffect

10^n的二进制表示

看0和1出现次数？

1的出现次数大于0的出现次数，使用 减
否则使用加

10=1010
+2^3+2^1
100=1100100
+2^6+2^5+2^2
1000=1111101000
-2^3-2^4+2^10
10000=10011100010000
+2^13+2^10+2^9+2^8+2^4
100000=11000011010100000
+2^16+2^15+2^10+2^9+2^7+2^5
.................

tprime

d[i] = d[i] << 3 + d[i] << 1;
需要括号吧？这段代码改成
int di = d[i];
d[i] = (di << 3) + (di << 1);
或许会快点