python - 没有乘法运算符的乘法数字的更好解决方案
问题描述
我为“破解编码面试”中的以下问题提出了这个解决方案,我认为它比我在他们的解决方案中看到的更快、更优雅,但不确定它是否适用于所有情况。谁能告诉我是否有一些边缘案例我错过了?
CTCI 的原始问题是(关于递归和动态规划的问题 8.5):
编写一个递归函数以在不使用 * 运算符的情况下将两个正整数相乘。您可以使用加法、减法和位移,但应尽量减少这些操作的数量。
我的解决方案是:
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)
谁能告诉我是否错过了什么?
解决方案
您可以使用位移来执行以 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
如果你不被允许使用&
操作符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
推荐阅读
- java - 为什么我不能直接将 for-each 循环用于泛型类型列表?
- java - 当我在 Xamarin 中构建解决方案时,我看到错误:“javac.exe”以代码 3 退出
- c - 如何在c中控制二维字符数组?
- html - 在给定任意颜色范围的情况下均匀分布画布渐变颜色
- vuejs2 - 有没有办法仅在开发期间将数据加载到商店中?
- python - 如何有效地在一个上限宽度水平写入 6 行卦?
- python - 如何在 tkinter 中禁用绑定到自己框架的其他两个单选按钮
- javascript - 我怎样才能访问从这个承诺返回的数据?
- html - 使用 Laravel 为 foreach 循环中的每个复选框创建一个表单
- php - 一种获取单个数组的简单方法,该数组包含 PHP 中嵌套对象中包含的所有整数