位运算实现加减乘除
加法
思路
思路很简单，首先假设两个数相加，所有位都没进位，那么结果就是所有位直接对应相加即可，比如123+234=357，而如果有一些位有进位的清空，比如456+789，我们先不考虑进位，每一位单独算，得到的结果设为a，这里a=135，再考虑进位，这里每一位都进位了，分别进了十位，百位和千位，所以进位的结果是1110，那很显然，我们可以将456+789的答案转化为不考虑进位的和加上进位的值，在这里也就是135+1110=1245，如果这个加法也出现了进位，那么很明显就采用递归/迭代的思路继续操作下去，直到两个数的加法不出现进位，即为答案。
上面是10进制的情况，2进制的道理是一样的，而且因为2进制我们可以采用位运算来快速计算上面的不进位加法(位异或)和进位和(位与再左移1位)，所以就可以采用位运算的方法来计算两个数的和。
代码
递归版：
int add(int a,int b){
if(b==0){
return a;
}
return add(a^b,(a&b)<<1);
}
非递归版：
int add(int a,int b){
while(b!=0){
int c=a^b;
b=(a&b)<<1;
a=c;
}
return a;
}
减法
思路
减去一个数，就等于加上一个的相反数，所以我们考虑相反数的二进制表示，总所周知，计算机是使用补码来表示一个数，比如我们分别输出-5和5的二进制位如下。
void print(int a){
for(int i=31;i>=0;i--){
printf("%d",(a>>i)&1);
}
printf("\n");
}
//111111111111111111111111111111011
//000000000000000000000000000000101
所以相反数的二进制表示就是按位取反再加1，而不用考虑正数还是负数的问题。
代码
int neg(int a){
return add(~a,1)
}
int sub(int a,int b){
return add(a,neg(b));
}
乘法
思路
乘法的思路是二进制数列竖式计算的思路，首先单独处理符号位(a^b可以判断符号位)，用绝对值来进行计算，对于被乘数乘以乘数，我们从低到高遍历乘数，当乘数当前位为1，答案应该加上被乘数乘以乘数当前位的权重，所以这里可以用一个简单的优化，因为随着乘数的遍历，权重一直都是左移一位的关系(1–>10–>100->…)，所以直接让被乘数左移即可，而另外为了方便计算乘数的当前位，我们可以直接让乘数右移，把当前位固定在最后一位，这样通过(b&1)就能快速得到这一位的值。
代码
int mul(int a,int b){
// 取绝对值
int aa=a<0?neg(a):a;
int bb=b<0?neg(b):b;
int ans=0;
while(bb){
// 如果被乘数当前(最后一位)为1，答案加上被乘数
if((bb&1)==1){
ans=add(ans,aa);
}
// 被乘数左移一位，被乘数左移是因为对应的权重不同
aa<<=1;
// 乘数右移一位，乘数右移是为了方便定位当前计算的位(一直是最后一位)
bb>>=1;
}
// 判断符号位
if((a^b)<0){
ans=neg(ans);
}
return ans;
}
除法
思路
除法是一个贪心的做法，从高位到低位(1«31,1«30,…)依次试除。
代码
int div2(int a,int b){
int aa=a<0?neg(a):a;
int bb=b<0?neg(b):b;
int ans=0;
for(int i=31;i>=0;i--){
if((aa>>i)>=bb){
ans=add(ans,1<<i);
aa=sub(aa,bb<<i);
}
}
if((a^b)<0){
ans=neg(ans);
}
return ans;
}
完整代码
以上加减乘除四种做法其实都没有考虑到溢出的情况，又不是做数电作业题，如果遇到这么刁难的面试题就拒了吧。
#include <bits/stdc++.h>
using namespace std;
void print(int a){
for(int i=31;i>=0;i--){
printf("%d",(a>>i)&1);
}
printf("\n");
}
int add(int a,int b){
if(b==0){
return a;
}
return add(a^b,(a&b)<<1);
}
int add2(int a,int b){
while(b!=0){
int c=a^b;
b=(a&b)<<1;
a=c;
}
return a;
}
int neg(int a){
return add(~a,1);
}
int sub(int a,int b){
return add(a,neg(b));
}
int mul(int a,int b){
// 取绝对值
int aa=a<0?neg(a):a;
int bb=b<0?neg(b):b;
int ans=0;
while(bb){
// 如果被乘数当前(最后一位)为1，答案加上被乘数
if((bb&1)==1){
ans=add(ans,aa);
}
// 被乘数左移一位 被乘数左移是因为对应的权重不同
aa<<=1;
// 乘数右移一位 乘数右移是为了方便定位当前计算的位(一直是最后一位)
bb>>=1;
}
// 判断符号位
if((a^b)<0){
ans=neg(ans);
}
return ans;
}
int div2(int a,int b){
int aa=a<0?neg(a):a;
int bb=b<0?neg(b):b;
int ans=0;
for(int i=31;i>=0;i--){
if((aa>>i)>=bb){
ans=add(ans,1<<i);
aa=sub(aa,bb<<i);
}
}
if((a^b)<0){
ans=neg(ans);
}
return ans;
}
int main(){
printf("%d\n",add(13,58));
printf("%d\n",add2(13,58));
printf("%d\n",sub(13,58));
printf("%d\n",sub(58,13));
printf("%d\n",mul(58,13));
printf("%d\n",mul(-58,13));
printf("%d\n",mul(-58,-13));
printf("%d\n",div2(58,13));
printf("%d\n",div2(-58,-13));
printf("%d\n",div2(-58,13));
printf("%d\n",div2(13,58));
return 0;
}