python - 无需乘法运算符即可进行数字相乘的更好解决方案

Question

我针对“破解编码面试”中的以下问题提出了这个解决方案，我认为从我在他们的解决方案中看到的情况来看，它更快、更优雅，但不确定它适用于所有情况。谁能告诉我是否有一些边缘情况我错过了？

CTCI 的原始问题是(关于递归和动态规划的问题 8.5):

Write a recursive function to multiply two positive integers without using the * operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

我的解决方案是:

def foo(a, b, mult = 0):
    if a == 0 or b == 0:
        return 0

    if (a & 1) == 1:
        return (b << mult) + foo(a >> 1, b, mult + 1)

    return foo(a >> 1, b, mult + 1)

谁能告诉我我是否错过了什么？

Answer 1

您可以使用位移位来执行以 2 为基数的乘法:

def multiply(A,B):
    result = 0
    while A:
        if A&1: result = result + B # Add shifted B if last bit of A is 1
        A >>= 1 # next bit of A
        B <<= 1 # shift B to next bit position
    return result

print(multiply(7,13)) # 91

如果您不被允许使用&运算符(operator)if (A>>1)<<1 != A:会做与 if A&1: 相同的事情(即测试最后一位)。

如果您查看乘法的位组成，您可以看到位移的作用:

#  bitPosition   A=13 (1101)   B=7 (111)  A*B=91 (1011011)
#
#       0        1                  111         111     7
#       1        0                 1110          
#       2        1                11100       11100    28
#       3        1               111000      111000    56
#                                            ------    --
#                                           1011011    91

由此，编写递归版本相对容易:

def multiply(A,B):
    if A == 0: return 0
    result = multiply(A>>1,B)<<1  # get the higher bit product
    if A&1: result = result + B   # add the last bit multiplier (B)
    return result