10^n的二进制表示

无心人

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

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <sys/time.h>
6. int d[1000000];
8. int main(void)
9. {
10. int i, j, k;
11. double t;
12. struct timeval start, end;
14. for (i = 0; i < 1000000; i ++)
15. d[i] = i << 8;
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);
25. t = (end.tv_sec - start.tv_sec) * 1.0 + (end.tv_usec - start.tv_usec) / 100000000.0;
26. printf("* : %4.6f\n", t);
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);
36. t = (end.tv_sec - start.tv_sec) * 1.0 + (end.tv_usec - start.tv_usec) / 100000000.0;
37. printf("<< %4.6f\n", t);
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); 或许会快点