10^n的二进制表示

无心人 · 发表于 2009-1-12 09:39:36

您需要登录才可以下载或查看，没有账号？欢迎注册

×

对所有的n <= 20的
10^n寻找小于n项的二进制幂的加减表示

比如1000正常的是9, 8, 7, 6, 5, 3共6个2的方幂加在一起
可以表示为9+8+7+6+5+3
但存在1000=2^10-2^4-2^3的结果
即最短表示是10-4-3

求出满足题目的最短表示

medie2005 · 发表于 2009-1-12 09:44:53

动态规划.

无心人 · 发表于 2009-1-12 10:21:56

给出结果
我想知道结果
为了快速的乘以10^n用

admin · 发表于 2009-1-12 10:31:03

一次乘法可能比三次“移位+加减”还快吧？

gxqcn · 发表于 2009-1-12 10:32:34

对不起，忘了脱马甲了。

无心人 · 发表于 2009-1-12 10:33:46

一次乘法是9个时钟
三次移位加减是1.5时钟
乘法吞吐量是2
加减移位是0.5
你说谁快？

无心人 · 发表于 2009-1-12 10:34:57

不过谢谢你提醒
我要重新评估下
大于10000的10的方幂的乘法了

gxqcn · 发表于 2009-1-12 10:39:07

原帖由 无心人 于 2009-1-12 10:33 发表
一次乘法是9个时钟
三次移位加减是1.5时钟
乘法吞吐量是2
加减移位是0.5
你说谁快？

你说的是老型号的CPU，
新的CPU中MUL指令的时钟数很小了。

无心人 · 发表于 2009-1-12 11:19:09

呵呵

需要测试下么？

tprime · 发表于 2009-1-12 11:33:17

主流CPU 32位整数乘法要4个时钟左右

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 10^n的二进制表示