不使用算术运算符计算 x * y

Question

我目前正在 python 中完成 "Elements of Programming Interview" 并且在这部分卡住了整整 3 天。下面的代码只是简单地将两个数字相乘，而不使用任何运算符；作者给出的解释如下：

"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 2ky to the result if the kth bit of r 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 apply the grade-school algorithm for addition to the binary case, i.e., compute the sum bit-by-bit, and "rippling" the carry along."

def multiply(x, y):
    def add(a, b):
        running_sum, carryin, k, temp_a, temp_b = 0, 0, 1, a, b

        while temp_a or temp_b:
            ak, bk = a & k, b & k
            carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
            running_sum |= ak ^ bk ^ carryin
            carryin, k, temp_b, temp_b = (
                carryout << 1, k << 1, temp_a >> 1, temp_b >> 1)

        return running_sum | carryin

    running_sum = 0
    while x:  # Examines each bit of x
        if x & 1:
            running_sum = add(running_sum, y)
        x, y = x >> 1, y << 1

    return running_sum


print(multiply(2, 2))

我的问题是：

变量 "ak" 和 "bk"
进位变量发生了什么；为什么我们对 (ab & bk, ak & carrying 和 bk & carryin) 使用按位与运算符然后使用按位或？
变量 "running_sum" 如何使用按位异或和按位或来跟踪总和？
1. 我们为什么要返回 "running_sum | carryin"

如能帮助理解此代码，我们将不胜感激。提前致谢。

Answer 1

在 add 中，我们将两个二进制数逐位相加。

k 是我们正在查看的位。
ak 和 bk 是 a 和 b

k

如果前面的 ak、bk 或前面的进位 (carryin) 中至少有两个为 1，则下一位的进位将为 1。因此，carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
在第 k 个数字中，如果 ak、bk 或 carryin 的奇数为 1，则我们得到 1。因此，ak ^ bk ^ carryin .由于我们只有一位，我们可以通过应用 OR 将其添加到 running_sum。
最后，当 a 和 b 都用完时（我们达到了它们的最高有效位），我们仍然需要处理可能剩余的进位标志。因此，running_sum | carryin.

不使用算术运算符计算 x * y

compute x * y without arithmetical operators

python

algorithm

bit-manipulation

bitwise-operators

python-3.x