只用位运算不用算术运算实现

题目

　　给定两个32位整数a和b，可正、可负、可0.不能使用算术运算符，分别实现a和b的加减乘除。

要求

　　如果给定的a和b执行加减乘除的某些结果本来就会导致数据的溢出，那么你实现的函数不必对那些结果负责。

基本思路

　加法运算

　　使用位运算实现加法运算主要分为两个部分。先计算完全不考虑进位进行相加的结果，再计算只考虑进位的产生值。将两个结果相加就是最终的结果。

　　例如： 
　　a:　　　　001010101 
　　b:　　　　000101111

首先不考虑进位进行相加，结果为001111010，该结果其实就是a ^ b。

再考虑进位的产生值，结果为000001010，该结果其实就是(a & b)<< 1。

将1、2产生的结果再相加，此时依然要考虑两部分：不考虑进位和只考虑进位。

一直重复上述步骤，直到进位产生的值全部消失。
 

private int add(int a,int b){int sum = a;while(b!=0){sum = a^bb = (a&b) << 1a = sum}return sum}

减法运算

实现a - b只要实现a + (-b)即可。所以只要将a和b的相反数调用add函数就行。根据二进制数在机器中表达的规则，得到一个数的相反数，就是这个数的二进制数表达取反加1（补码）的结果

public int negNum(int n){return add(~n,1) }public int minus(int a,int b){return add(a,negNum(b)) }

乘法运算

用位运算实现乘法运算。a × b的结果可以写成 a∗20∗b0+a∗21∗b1+...a∗2i∗bi+...a∗231∗b31a∗20∗b0+a∗21∗b1+...a∗2i∗bi+...a∗231∗b31. 其中bibi为0或1表示整数b的二进制表达中第i位的值（从右往左数）。该过程有点类似于求整数的N次方问题。具体实现参照如下代码
 

public int multi(int a,int b){int res = 0;while(b!=0){if((b&1)!=0){res = add(res,a);}a <<= 1;b >>= 1;}return res; }

除法运算

　　用位运算实现除法运算其实就是乘法的逆运算。定义 res 表示除法的结果。首先将a向右移位31位，然后看能不能容下b，如果能，说明a/231a/231可以包含一个b，等价于a可以包含一个b∗231b∗231，令res的第31位为1，此时a的值应该为a−b∗231a−b∗231；如果不能容下b，令res的第31位为0，a的值不变；接下来将a向右移位30位是否能容下b……重复步骤直到a−b∗2i=0a−b∗2i=0。 
　　以上过程只适用于a和b都不是负数的情况下，当a或b为负数时，可以先将a和b转成正数，计算完之后再判断res的真实符号就行。 
　　除法实现到这一步已经可以解决绝大多数情况了。但是我们知道，32位最小整数的绝对值要比最大整数大，所以如果a或b等于最小值，是不能转换成相对应的正数的。这时候需要分情况考虑：

如果a和b都为最小值，直接返回1

如果a不为最小值，而b为最小值，那么a/b = 0，直接返回0

如果a为最小值，而b不为最小值。这时我们对a无能为力，但是我们可以让a增大一点点，计算出一个结果然后再修正一下就可以得到最终的结果。处理过程如下：

　　<1>计算(a+1)/b(a+1)/b，结果记为c 
　　<2>计算c∗bc∗b 
　　<3>计算(a−c∗b)/b(a−c∗b)/b，结果记为rest 
　　<4>计算c+rest
 

public boolean isNeg(int n){return n<0; }public int div(int a,int b){int x = isNeg(a) ? negNum(a):a;int y = isNeg(b) ? negNum(b):b;int res = 0;for (int i = 31;i>-1;i=minus(i,1)){if ((x>>i)>=y){res |= (1<<i);x = minus(x,y<<i);}}return isNeg(a)^isNeg(b) ? negNum(res):res; }public int divide(int a,int b){if(b==0){throw new RuntimeException("divisor is 0");}if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE){return 1;}else if (b == Integer.MIN_VALUE){return 0;}else if (a == Integer.MIN_VALUE){int res = div(add(a,1),b);return add(res,div(minus(a,multi(res,b)),b));}else{return div(a,b);} }

 

总结

以上是生活随笔为你收集整理的只用位运算不用算术运算实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。