大一计算机的自学总结：位运算实现加减乘除

前言

位运算当然可以用来实现加减乘除。

一、加法

#include<bits/stdc++.h>
using namespace std;int add(int a,int b)
{int ans=a;while(b!=0){ans=a^b;b=(a&b)<<1;a=ans;}return ans;
}int main()
{int a,b;cout<<"a,b:"<<endl;cin>>a>>b;cout<<add(a,b);return 0;
}

 加法的原理就是利用了异或运算的本质：无进位加法再加上进位信息所得。

先让ans=a，然后只要b不等于0，先取两数的异或，即无进位加法；之后取两数进位信息，若两数在相同数位上都为1，所以该位进位，就是a&b。然后为了将进位信息加到ans中，要将a&b的的结果左移一位，直到两数没有进位信息。

二、减法

#include<bits/stdc++.h>
using namespace std;int add(int a,int b)
{int ans=a;while(b!=0){ans=a^b;b=(a&b)<<1;a=ans;}return ans;
}int neg(int n)
{return add(~n,1);
}int sub(int a,int b)
{return add(a,neg(b));
}int main()
{int a,b;cout<<"a,b:"<<endl;cin>>a>>b;cout<<sub(a,b);return 0;
}

 减法就很简单了，转化成a+(-b)即可，而-b就是~b+1。

三、乘法

#include<bits/stdc++.h>
using namespace std;int add(int a,int b)
{int ans=a;while(b!=0){ans=a^b;b=(a&b)<<1;a=ans;}return ans;
}int mult(int a,int b)
{int ans=0;while(b!=0){if((b&1)!=0){ans=add(ans,a);}a<<=1;b>>=1;}return ans;
}int main()
{int a,b;cout<<"a,b:"<<endl;cin>>a>>b;cout<<mult(a,b);return 0;
}

 乘法依旧借助了竖式运算的原理，只不过这里是按二进制数位进行的。

若b的最后一位是1，就让ans再加上一个a，之后，要将a左移1位，并且为了取b的下一个数位，要让b右移一位。

四、除法

#include<bits/stdc++.h>
using namespace std;int add(int a,int b)
{int ans=a;while(b!=0){ans=a^b;b=(a&b)<<1;a=ans;}return ans;
}int neg(int n)
{return add(~n,1);
}int sub(int a,int b)
{return add(a,neg(b));
}int divide(int a,int b)
{int x=a<0?neg(a):a;int y=b<0?neg(b):b;int ans=0;for(int i=30;i>=0;i--){if((x>>i)>=y){ans|=(1<<i);x=sub(x,y<<i);}}return (a<0)^(b<0)?neg(ans):ans;
}int main()
{int a,b;cout<<"a,b:"<<endl;cin>>a>>b;cout<<divide(a,b);return 0;
}

除法借助的原理是，例如280除以25，只保留商，可以将280转化成25*2^3+25*2^1+25*2^0。

首先先将负数转为正数，然后从第30位开始到第0位，若x右移i位比y大，即x还包含2^i个y，所以往ans的第i位里或进去一个1，之后让x减去2^i个y即可。最后这个判断很妙，只有a和b异号时才返回-ans。

总结

感觉位运算实现加减乘除在做题上没什么用，就当训练位运算了。（）

END