c++ - 被间接乘法算法困扰

Question

当我准备考试时，我发现了一个要求间接乘法算法的问题。

问题:

Two integers p and q can be indirectly multiplied by the following method.

If the product expected is r (initially 0) then, if q is odd p is added to r and q is reduced by 1, If q is even p is doubled and q is halved(i.e. q becomes q/2) If q is even p is doubled and added to r and q is halved(i.e. q becomes q/2)

进一步指出，间接乘法用于数字计算机，其中直接乘法的成本较高

通过尝试几个小时，我设法找到了迭代和递归算法，但它们并不完美。

迭代

int multiply(int p, int q){
    int r=0;
    while(q!=0){
        if(q%2==1){
            r += p;
            q--;
        }
        else{
            r += 2*p;
            q = q/2;
        }
    }
    return r;
}

递归

int multiplyRec(int p, int q){
    if(q==1)
        return p;
    if(q%2==1){
        return (p + multiplyRec(p, q-1));
    }
    else{
        return (2*p + multiplyRec(p, q/2));
    }
}

例如，当我将 6 乘以 5 时，两种算法的答案都是 36，而它必须是 30。但是如果我以某种方式更改它以获得 30，那么乘以 1 就会失败。

我正在网上冲浪，但找不到匹配的内容。 有人可以解释一下上述算法有什么问题吗，或者是否有错误，或者是否有更好的方法来做到这一点。

Answer 1

您的报价框中的算法是错误的。应该是:

If the product expected is r (initially 0) then, if q is odd p is added to r and q is reduced by 1, If q is even p is doubled and q is halved(i.e. q becomes q/2)

也就是说，当 q 是偶数时，您只需将 p 加倍，而不是将其添加到 r。

它还缺少 q == 0 的隐式终止条件

这对应于简单的二进制长乘法——对于 q 中的每 1 位，您添加左移 1 位位置的 p；对于 q 中的每个 0 位，您什么也不做。

这通常写为

while (q != 0) {
    if (q & 1)  // q is odd
        r += p;
    p *= 2;
    q /= 2;
}

这是因为当q是奇数时，减1就会变成偶数，所以你可以立即进行下一步，将p加倍并将q减半。由于整数除法会向下舍入，因此奇数除以 2 也会隐式得到 -1。