"Coding Interview Guide" -- 只用位运算不用算术运算实现整数的加减乘除运算

【题目】

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

【要求】

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

加法运算：a + b = (a ^ b) + ((a & b) << 1)

 1 public int add(int a, int b)
 2 {
 3 　　int sum = a;
 4 　　while(b != 0)
 5 　　{
 6        sum = a ^ b;          // 不带进位的加法
 7        b = (a & b) << 1;     // 进位值
 8        a = sum;
 9 　　}
10 
11 　　return sum;
12 }

减法运算：a - b = a + (-b)

1 public int sub(int a, int b)
2 {
3     return add(a, negNum(b));
4 }
5 
6 public int negNum(int num)
7 {
8     return add(~num, 1);
9 }

乘法运算：a * b = a*(2^0)*b0 + a*(2^1)*b1 + a*(2^2)*b2 + ... + a*(2^(31))*b31

 1 public int mul(int a, int b)
 2 {
 3     int res = 0;
 4     while(b != 0)
 5     {
 6         if((b & 1) != 0)
 7         {
 8             res = add(res, a);
 9         }
10         a <<= 1;
11         b >>>= 1;
12     }
13     return res;
14 }

除法运算：a / b = res <==> a = b * res

 1 public int divide(int a, int b)
 2 {
 3     if(b == 0)         // 除数不能为0
 4     {
 5         throw new RuntimeException("divisor is 0");
 6     }
 7     if(a == Integer.MIN_VALUE && b == Integer.MIN_VALUE)   // 当a或b为最小值时需分情况讨论
 8     {
 9         return 1;
10     }
11     else if(b == Integer.MIN_VALUE)
12     {
13         return 0;
14     }
15     else if(a == Integer.MIN_VALUE)
16     {
17         int temp = div(add(a, 1), b);
18         return add(temp, div(sub(a, mul(temp, b)), b));
19     }
20     else
21     {
22         return div(a, b);
23     }
24 }
25 
26 
27 public int div(int a, int b)
28 {
29     int x = isNeg(a) ? negNum(a) : a;     // 不适用于a或b为最小值的情况
30     int y = isNeg(b) ? negNum(b) : b;     // 不适用于a或b为最小值的情况
31     int res = 0;
32     for(int i = 31; i > -1; i = sub(i, 1))
33     {
34         if((x >> i) >= y)
35         {
36             res |= (1 << i);
37             x = sub(x, y << i);
38         }
39     }
40     return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
41 }
42 
43 
44 public boolean isNeg(int n)
45 {
46     return n < 0;
47 }

来源：左程云老师《程序员代码面试指南》