只用加法、取模和右移乘法：迭代与递归双倍分解

题目重点：将非负乘数按二进制拆分，避免重复加b次。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

a/b为非负任意精度整数，允许比较、赋值、函数调用及给定+/%/>>；计算过程中不使用乘法。
有符号固定宽整数、溢出及负数右移语义未给，留待核，不默认位技巧对全部int安全。

解题路线

循环维护result+a×b等于原积的数学不变量（实现不执行乘法）。b为奇数时加a，再a变a+a、b右移1；因此剩余贡献与加入部分之和不变。
递归同理solve(a,b)=solve(a+a,b>>1)+(a若b%2否则0)，b0返回0。递归返回后加低位贡献。
递归深度为b位数，极大b应迭代或分治栈。若想支持负数，需要先明确允许取负/减法与范围，不能用未允许的*、abs或−来偷换合同。

手动走一遍

a7,b5（二进制101）：加7，翻倍14、b2；不加，翻倍28、b1；加28，结果35。a0或b0结果0；b1一次加a。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def product(a,b):
    if a<0 or b<0:raise ValueError("nonnegative integers required")
    result=0
    while b:
        if b%2:result+=a
        a+=a;b=b>>1
    return result


def product_recursive(a,b):
    if a<0 or b<0:raise ValueError("nonnegative integers required")
    def solve(x,y):
        if not y:return 0
        half=solve(x+x,y>>1)
        return half+x if y%2 else half
    return solve(a,b)

复杂度

O(logb)轮加法、O(1)迭代状态；大整数每次加法有位长成本，总保守O((bits(a)+bits(b))bits(b))。递归辅助栈O(logb)。

易错点与追问

容易失分的边界

C/C++有符号溢出未定义，不能把Python正确性当固定宽正确性。
负数>>1可能永远到−1，需拒绝或另设计。

继续深挖

若必须支持负数且只允许这些运算，可如何说明缺失合同或逐步符号处理？
模某正数输出时，哪些中间值需减小以避免溢出？