Multiply two numbers without using * operator, and with minimum number of additions
例如:如果输入为5*8,则可以使用以下方法之一添加较大数量的较小次数,这将是答案.但是,如何最大限度地减少添加次数？
我喜欢 Codor 使用轮班和零添加的建议！
但如果你真的只能使用加法而不使用其他操作，如移位、对数、减法等，我相信计算 a * b 的最小加法次数将是：
min{int[log2(a+1)] + numbits(a), int[log2(b+1)] + numbits(b)} - 2
在哪里
numbits(n) 是整数 n 的二进制表示形式中 1 的数量
int[x] 是 float x 的整数部分
现在，我们是如何到达那里的？首先看一下你原来的例子。您至少可以将添加的内容分组在一起。例如
8+8=16
16+16=32
32+8=40
概括来说，如果您需要仅使用使用 a 的加法或已计算的加法结果来乘以 ab 次，则需要：
int[log2(b+1)]-1 加法来计算您需要的所有 2^na 中间数。
numbits(b)-1 加法将所有中间结果加在一起，其中 numbits(b) 是 b 的二进制表示形式中 1 的数量。
有趣的是，这意味着你的陈述
add the bigger number smaller number of times
并不总是最小化添加数量的方法。
例如，如果您需要计算 2^9 * (2^9 - 1)，则基于 (2^9-1) 计算加法比基于 2^9 计算加法更好，即使 2^9 更大。最快的方法是：
x = (2^9-1) + (2^9-1)
进而
x = x+x
8次，总共9次添加。
如果您将 2^9 添加到自身，则需要先进行 8 次加法才能得到所有 2^k*2^9，然后再进行 8 次加法将所有这些数字加在一起，总共需要 16 次加法。