@chawuciren
2018-11-22 12:04
字数 1265
阅读 1007
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;
}
更新答案
所以正确的做法是什么?
把b看成一个二进制数字,用符号记数法将他转化为十进制。我们就会得到
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;
}