如何只用加号和位移实现两个数的乘法

CSI

递归

第一种情况：第二个因数为偶数（这里只讨论第二个因数的奇偶）

假设我们要计算3*4，相当于计算3+3+3+3。可以看到里面有重复运算，比如先计算3+3=6，再计算6+6=12。这样就省掉了一次运算。
现在推广到计算3×n，第一次先计算a=3<<1,result=a+a然后n=n>>1,第二次计算result=result+a,然后n=n>>1......直到n==1。
接着我发现如果n>>1以后还是偶数，就能继续提高效率。
然后我就想，能不能设计n是偶数就进入第一种情况，n是奇数就进入第二种情况（包括右移后的n）。
n不停除二，除到最后不是二就是三。
假如是二就计算3+3，是三就在计算完毕之后再加3。
然后用递归实现。

int mu(int a,int b){
    return b==1?a:mu(a<<1,b>>1);//如果b是奇数。。。还没想到最后一个怎么加
}

答案

int mu(int a,int b){
    if(b==0)
        return 0;
    if(b==1)
        return a;
    if(b&1)
        return b==1?a:2*mu(a,b>>1)+a;
    else
        return b==1?a:2*mu(a,b>>1);
}

迭代

试图写迭代还是用了乘法
一开始想像递归那样乘，后来发现迭代相当于正序计算，递归相当于反序，所以当然是不行的。
考虑到如果是奇数，除二以后会多出来一个a，那额外计算这个a的数量就好了，其他就和偶数一样了。
然后，这个a的数量还是乘上去的。。。

int mu(int a,int b){
    int t=a;//记录一下a
    int i=1;//记录一下右移了几次了（就是分了几个部分）
    int j=1;//分一次就将这个乘2的平方
    int n=0;//奇数的时候没计入的都放到这里
    if(b==0)
        return 0;
    if(b==1)
        return a;
    do{//
        a+=a;
    if(b&1){//
        n=n+t*j;//这里还是用了乘法。。。
    }
    j<<=i;//相当于乘2的平方
    b>>=1;//相当于除二
    }while(b!=1);
    a=a+n;//加起来就是结果
    return a;
}

11.22

更新答案
所以正确的做法是什么？
把b看成一个二进制数字，用符号记数法将他转化为十进制。我们就会得到$a*b=a*b_{n-1}*2^{n-1}......a*b_{0}$
b的每一位不是0就是1，剩下的只要算a*2就可以了
先是b取每一位

int p=b&1;//存放这一位
b=b>>1;//b右移一位，下一次迭代就可以取下一位

这一位是0啥也不用干(really?)，这一位是1就要计算a×2
是0就不用加，不是0就要加，但是都要对a左移。
结果

int mu(int a,int b){
    int res=0;
    do{
        int p=b&1;//存放这一位
        b=b>>1;//b右移一位，下一次迭代就可以取下一位
        if(p==1)
            res+=a;
        a<<=1;
    }while(b!=0);
    return res;
}