位操作实现加减乘除四则运算
1 先来掌握一些常用的位运算操作：
（1）等式：-n = ~(n - 1) = ~n + 1（-n等于其各位取反加1）；
（2）获取整数n的二进制中最后一个1：-n&n 或(~n+1)&n或 ~(n - 1)&n；
如：n = 010100，则 -n = 101100, n&(n - 1)=000100；
（3）去掉整数n的二进制中最后一个1：n&(n - 1)。如：n = 010100, n -1 = 010011, n&(n - 1) = 010000。
2 四则运算实现
（1）加法（a + b）
用^、&和<<即可实现，a^b可得到对应位没有进位时的和，a&b可得到各位产生的进位值。
如：a=010010, b=100111，计算过程如下：
第一轮：a^b=110101，(a&b)<<1=000100（进位）。由于进位大于0，进入下一轮：a=110101,b=000100；
第二轮：a^b=110001，(a&b)<<1=001000（进位）。进位大于0，进入下一轮：a=110001,b=001000；
第二轮：a^b=111001，(a&b)<<1=000000（进位）。进位等于0，终止；
结果为：111001。
非递归代码如下：
int add(int a, int b)
{
int carry; // 进位
while (b)
{
carry = (a & b) << 1; // a & b取各位的进位，进位作用于对应位的高1位
a = a ^ b;
b = carry;
}
return a;
}
递归代码如下：
int add_recursion(int a, int b)
{
if (0 == b) return a;
else
{
int carry = (a & b) << 1;
a = a ^ b;
return add_recursion(a, carry);
}
}
（2）减法（a - b）
减法可以转化成加法：a - b = a + (-b) = a + (~b + 1)
因此代码如下：
int sub(int a, int b)
{
return add(a, add(~b, 1));
}
（3）乘法（a * b）
先看一个乘法算法：1011 * 1010
1011 * 1010 -------- 10110 (1011<<1,相当于乘以0010) 1011000 (1011<<3,相当于乘以1000) -------- 1101110
因此乘法可以通过系列的移位和加法实现。
代码如下：
int mul(int a, int b)
{
int ans = 0;
while (b)
{
if (b & 1) ans = add(ans, a);
a <<= 1;
b >>= 1;
}
return ans;
}
（4）除法（a / b）
除法就是由乘法的过程逆推，依次减掉（如果a够减的）b ^ (2 ^ 31), b ^ (2 ^ 30), ...b ^ 8, b ^ 4, b ^ 2, b ^ 1。减掉相应数量的b就在结果加上相应的数量。
1011 / 1010的部分步骤：
10110000 / 1010
10110100
-10100000 (1010<<4)
----------
10100
- 10100 (1010<<1)
----------
0
代码如下：
int div(int a, int b)
{
int ans = 0;
for (int i = 31; i >= 0; i--)
{
//比较a是否大于b的(1<<i)次方，避免将a与(b<<i)比较，因为不确定b的(1<<i)次方是否溢出
if (b <= (a >> i))
{
ans += (1 << i);
a -= (b << i);
}
}
return ans;
}