使用间接乘法算法
当我准备考试时，我发现了一个问题，要求使用间接乘法的算法。
问题：
两个整数p和q可以通过以下方法间接相乘。
如果期望的乘积是r(最初是0)，那么如果q是奇数，p被加到r上，q被减1，如果q是偶数，p被加倍，q被减半(即q变成q/2)，如果q是偶数，p被加倍并被加到r上，q被减半(即q变成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就失败了。
我在网上冲浪，但找不到匹配的。有没有人可以解释一下上面的算法有什么问题，或者是否有错误，或者有没有更好的方法来做它们。
回答 2
Stack Overflow用户
发布于 2018-12-19 14:33:01
您报价框中的算法是错误的。它应该是：
如果期望乘积是r(最初是0)，那么如果q是奇数，则p被加到r上，q被减1，如果q是偶数，p被加倍，q被减半(即q变成q/2)
也就是说，当q是偶数时，你只需将p加倍，而不是将它加到r上。
它还缺少Q == 0的隐式终止条件
这相当于简单的二进制长乘法--对于q中的每1位，添加p左移1位的位置；对于q中的每0位，什么都不做。
这通常被写成
while (q != 0) {
if (q & 1) // q is odd
r += p;
p *= 2;
q /= 2;
}这是因为当q是奇数时，减去1会使其成为偶数，因此您可以立即执行下一步，将p加倍并将q减半。由于整数除法会向下舍入，因此将奇数除以2也会隐式地执行-1。
Stack Overflow用户
发布于 2018-12-19 15:09:21
如果你遵循下面的规则，而不是你所说的规则，算法将会工作得很好：
如果期望乘积是r(最初是0)，那么如果q是奇数，则p被加到r，如果q是偶数，p被加倍，q被减半(即q变成q/2)
示例代码：
int mult(int p,int q){
int r=0;
if(q%2==1)
{
if(q!=1)
{
r+=p;
//q--;
return r*q;
}
r+=p;
return r*q;
}
else if(q%2==0)
{
if(q!=0)
{
p=p*2;
r+=p;
q=q/2;
return r*q;
}
return 0;
}}https://stackoverflow.com/questions/53843647
复制相似问题