两个数无操作数相乘背后的理论

Question

我一直在阅读编程基础访谈，但很难理解下面的段落：

"The algorithm taught in grade-school for decimal multiplication does not use repeated addition- it uses shift and add to achieve a much better time complexity. We can do the same with binary numbers- to multiply x and y we initialize the result to 0 and iterate through the bits of x, adding (2^k)y to the result if the kth bit of x is 1.

The value (2^k)y can be computed by left-shifting y by k. Since we cannot use add directly, we must implement it. We can apply the grade-school algorithm for addition to the binary case, i.e, compute the sum bit-by-bit and "rippling" the carry along.

As an example, we show how to multiply 13 = (1101) and 9 = (1001) using the algorithm described above. In the first iteration, since the LSB of 13 is 1, we set the result to (1001). The second bit of (1101) is 0, so we move on the third bit. The bit is 1, so we shift (1001) to the left by 2 to obtain (1001001), which we add to (1001) to get (101101). The forth and final bit of (1101) is 1, so we shift (1001) to the left by 3 to obtain (1001000), which we add to (101101) to get (1110101) = 117.

我的问题是：

这背后的总体思路是什么，它是如何 "bit-by-bit" 添加
(2^k)y从何而来
"left-shifting y by k"是什么意思
例子中，为什么13的LSB为1，结果就设置为(1001)？

Answer 1

该算法依赖于数字的二进制编码方式。

设A为无符号数。 A由一组位编码a_n-1a_{n- 2}...a₀ 这样 A=∑_{_i=0}^{^n-1}a_i×2ⁱ

现在，假设你有两个二进制编码的数字 A 和 B，你想计算 A×B

B×A=B×∑_{_i=0}^{^n-1}a_i×2ⁱ
=∑_{_i=0}^{^n-1}B× a_i×2ⁱ

a_i等于0或1。如果a_i=0，不修改和。如果a_i=1，我们需要加上B×a_我
所以，我们可以简单推导出乘法算法

result=0
for i in 0 to n-1
  if a[i]=1 // assumes a[i] is the ith bit
    result = result + B * 2^i
  end
end

What is the overall idea behind this, how is it a "bit-by-bit" addition

它只是前一种方法的应用，您依次处理乘法器的每一位

where does (2^k)y come from

从二进制数的编码方式上面已经提到了。如果设置了第i位，那么在数的分解中就有2ⁱ

what does it mean by "left-shifting y by k"

左移意味着"pushing"位向左移动并用零填充"holes"。因此，如果数字是 1101 并且它左移三位，它就变成 1101000.
这是将数字乘以 2ⁱ 的方法（就像 "left shifting" 乘以 2 一个十进制数并在正确的位置放零是乘以 100= 的方法10²)

In the example, why do we set result to (1001) just because the LSB of 13 is 1?

因为最右边有个1，对应2⁰。所以我们左移0位，加到初始化为0的结果中。

两个数无操作数相乘背后的理论

Theory behind multiplying two numbers without operands

binary

bit-manipulation

bit-shift

bitwise-operators