位操作实现四则运算

参考《程序员面试笔试宝典》实现用位操作进行四则运算：

需要熟练掌握一些常见功能的位操作实现，具体为：

<1> 常用的等式：-n = ~(n-1) = ~n+1

<2> 获取整数n的二进制中最后一个1：n&(-n) 或者 n&~(n-1)，如：n=010100，则-n=101100，n&(-n)=000100

<3> 去掉整数n的二进制中最后一个1：n&(n-1)，如：n=010100，n-1=010011，n&(n-1)=010000

(1)、加法实现

a + b，我们可以用 “异或” 运算来得到抛开进位的加法结果 add = a ^ b，然后用 "与" 和 "左移" 运算得到进位结果 carry = (a & b) << 1，再计算add + carry的值，如此就构成循环，只要carry的值不为0就一直循环下去。

 1 int plus(int a, int b)
 2 {
 3     if ((0 == a) || (0 == b))
 4     {
 5         return ((0 == a) ? b : a);
 6     }
 7 
 8     int add;
 9     int carry;
10 
11     while (0 != b)
12     {
13         add = a ^ b;
14         carry = (a & b) << 1;
15 
16         a = add;
17         b = carry;
18     }
19 
20     return(a);
21 }

(2)、减法实现

可以很容易的将减法运算转换为加法运算，a - b = a + (-b) = a + (~b) + 1。

1 int subtract(int a, int b)
2 {
3     return (plus (a, plus (~b, 1)));
4 }

(3)、乘法实现

我有一篇博文提到二进制乘法的原理，这里将其转换成代码即可：

 1 int multiply(int a, int b)
 2 {
 3     if ((0 == a) || (0 == b))
 4     {
 5         return (0);
 6     }
 7 
 8     bool bFlag = (b < 0);
 9 
10     if (b < 0)
11     {
12         b = -b;
13     }
14 
15     int nAdd = 0;
16     int nLast;
17     int nFlag = 1;
18 
19     while (0 != b)
20     {
21         nLast = b & (-b);
22         nFlag = 1;
23 
24         while (nFlag != nLast)
25         {
26             a <<= 1;
27             nFlag <<= 1;
28         }
29 
30         nAdd = plus (nAdd, a);
31         b &= subtract (b, 1);
32     }
33 
34     return (bFlag ? (-nAdd) : nAdd);
35 }

(4)、除法实现

除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。

 1 int divide(int a,int b)
 2 {
 3     if (0 == b)
 4     {
 5         printf ("除0!\n");
 6         exit(-1);
 7     }
 8 
 9     bool bFlag = (a < 0) ^ (b < 0);
10 
11     if (a < 0)
12     {
13         a = -a;
14     }
15 
16     if (b < 0)
17     {
18         b = -b;
19     }
20 
21     int ans=0;
22     for(int i=31;i>=0;i--)
23     {
24         // 比较x是否大于y的(1<<i)次方，避免将x与(y<<i)比较，因为不确定y的(1<<i)次方是否溢出
25         if((a >> i) >= b)
26         {
27             ans =plus (ans, (1<<i));
28             a = subtract(a, (b << i));
29         }
30     }
31 
32     return (bFlag ? (-ans) : ans);
33 }