位操作实现加减乘除和幂运算

位操作在一定程度上加快了计算的速度，上本科的时候实现过位运算的各种运算，时间长了已经忘光了，拿出来重新实现实现。

位操作回顾

与(&)：同真为真，其余为假 0&0=0、0&1=0、1&0=0、1&1=1

或(|)：有真为真，无真为假0|0=0、0|1=1、1|0=1、1|1=1

非(~)：真变假，假变真~0=1、~1=0

异或(^)：不同为真，相同为假0^0=0、0^1=1、1^0=1、1^1=0

加法

各种运算中加法应该算是基础，所以我们先实现加法。

模拟小学加法运算，每位相加，一位存不下则向上进位。0 | 0 = 0、 0 | 1 = 1、1 | 0 = 1、 1 | 1 = 10，只观察最后一位我们发现与异或运算时匹配的，然后需要考虑的是1|1=10进位的问题。

1|1=10进位也只可能实在1|1的情况，因此我们只需要考虑1、1的情况，恰好是与的情况，然后向左移一位变成了进位了。

不考虑进位的加法=异或(^)

进位=与(&)

到这一步大家应该也可以想到了，先把两个数的异或运算拿到，然后获得两个数的进位，接下来的就是把这两个数相加了，那是不是又有问题了！我们是来实现加法运算的，结果又需要调用加法运算！这不是相互矛盾么！

对啊！我们不是实现加法运算么，那就把这两个数再调用一次加法运算呗！那啥时候是个头呢？

0加任何数不都得原值么，进位始终是要进完的，所以进位到不能进位为止，咱们就可以返回这个值了。

int add(int a, int b){
int yihuo, yu;
yihuo = a ^ b;
//不考虑进位的加法操作
yu
= (a & b) << 1;
//进位
if(yu == 0){
return yihuo;
}else{
return add(yihuo, yu);
}
}

减法

有加法了，减法就显而易见了吧(加上相反数)。

不过相反数怎么来？

先逐位取反，再加1。

int get_negetive(int a){
return add(~a, 1);
}

减法就显而易见了。

int minus(int a, int b){
return add(a, get_negetive(b));
}

乘法

刚开始脑子不好使，总想着反复叠加的笨操作。想想咱们被乘数好像做不了什么骚操作，那我们就从乘数下手。

想来任何一个数都可以被2的倍数的和来表示(n=2^x1+2^x2+...+2^xn)，二的倍数不正好是位运算的每一位么，变成加法不就正好可以用乘法分配律么！a*n = a*(2^x1+2^x2+...+2^xn) = a*2^x1 + a*2^x2+...+a*2^xn

那就操练起来吧，咱们按乘数的x1,x2,...,x3来操作吧。

int multiply(int a, int b){
if(b == 0 || a == 0)return 0;
int ans = 0;
int result_flag = is_negetive_result(a, b);
a = get_positive(a);
b = get_positive(b);
while(b){
if(b&1){
ans = add(ans, a);
}
a = a << 1;
b = b >> 1;
}
if(result_flag){
ans = get_negetive(ans);
}
return ans;
}

在最初的操作之前先得判断结果的正负性，因为对于负数来说都是补码，我们移位并不好操作，所以都要转换成正数操作，最后转换为它应有的符号。

除法

除法我是真想不出有什么更骚的操作了，就是按照除数的最大倍数来搞，如果比被除数小那我们就可以做减法了，如果大的话那就把它弄小再来一次。如果大家有什么骚操作可以给我留言。

int divides(int a,int b){
int result_flag = 0;
if(is_negetive_result(a, b)){
result_flag = 1;
}
a = get_positive(a);
b = get_positive(b);
int i = 31;
int ans = 0;
while(i >= 0){
if((a>>i) >= b){
ans = add(ans, 1<<i);
a
= minus(a, b<<i);
}
if(a == 0)break;
i = minus(i, 1);
}
if(result_flag){
ans = get_negetive(ans);
}
return ans;
}

符号问题同乘法。

幂运算

幂运算的思路借鉴乘法运算。n=2^x1+2^x2+...+2^xn，a^n = a^(2^x1+2^x2+...+2^xn) = a^2^x1 * a^2^x2 * ...* a^2^xn。

结果还是按照x1,x2,...,x3来操作。

int power(int a,int b){
int ans = 1;
while(b){
if(b & 1){
ans = multiply(ans, a);
}
a = multiply(a, a);
b = b >> 1;
}
return ans;
}

最后

以上就是安静猎豹为你收集整理的位操作实现加减乘除和幂运算位操作实现加减乘除和幂运算的全部内容，希望文章能够帮你解决位操作实现加减乘除和幂运算位操作实现加减乘除和幂运算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。