两个正整数相乘的非主流算法

假设n和m是两个正整数,计算n*m,现在用n的输入作为实例规模的度量标准。

假设n是偶数,一个规模为原来一半的实例必须要对n/2进行处理,n*m=n/2 * 2m

假设n是奇数,只需要对公式进行简单调整,n*m=(n-1)/2 * 2m

并且使用1*m=m作为终止条件。

我们写下来一个例子就会发现:所有当前n的值是奇数时候,只需要相加对应的m值即可得到n*m的乘积。

例如:50*65=25*130=12*260 (+130)=6*520=3*1040=1*2080===2080+1040+130=3250

下面我们就开始下代码实现:

#include <iostream>
using namespace std;
 
int main()
{
    int n,m,mul=0;
    cin>>n>>m;
    for(int i=n>>1;i>=1;i=i>>1)
    {
        m=m< &lt;1;
        if(i%2==1)
        {
            mul=m+mul;
        }
    }
    cout<<endl<<"mul="<<mul<<endl;
    return 0;
}

原文来自:http://www.cnblogs_com.lebenusa.com/wongyi/p/7736991.html

本文地址:http://www.xoghaye.com/russian-multiplication.html编辑:王毅,审核员:逄增宝