使用位运算技巧实现加减乘除
作者：Grey
原文地址：
说明
题目描述见：LeetCode 29. Divide Two Integers
原题目是：要求不使用乘法、除法和 mod 运算符实现除法。
我们把题目要求提高一点，不用加减乘除和 mod 运算符号，只使用位运算实现加减乘除法。
实现加法
异或（^）运算就是两个数对应二进制值的无进位相加，比如a = 13且b = 20，a ^ b的结果如下（用二进制表示)
13 = 8 + 4 + 1
20 = 16 + 4
01101 ^ 10100 -------- 11001 结果就是:25
思路可以转换一下，把加法用异或替换，得到两个数二进制无进位信息相加的结果。然后把这个结果加上进位信息，就是两个数相加的最终结果。
如上例，a ^ b = 25, a和b相加的进位信息是01000（十进制就是 8）。25 + 8 = 32，正好是a + b的结果。
抽象一下:
要计算a + b
先算a ^ b = a'
然后得到 a 和 b 相加的进位信息 b'
则a + b = a' + b'。由于不能用加号，所以，我们只能逐个把进位信息叠加。
何时会产生进位信息？
a 和 b 的二进制对应位置上都是1，则会产生进位
每次处理的进位为(a & b) << 1。
实现代码如下
public static int add(int a, int b) { int sum = a; while (b != 0) { sum = a ^ b; b = ((a&b)<<1); a = sum; } return sum; } 实现减法
a - b = a + (-b)，
由于不能出现减号，所以，可以用加法来模拟一个数的相反数，因为
x的相反数等于~x + 1，即add(~x,1)。
所以，减法实现如下
// 实现减法 public static int minus(int a, int b) { return add(a, negNum(b)); } // 某个数n的相反数就是 ~n + 1，由于不能用+号 // 所以是 add(~n,1) public static int negNum(int n) { return add(~n, 1); } 实现乘法
小学算术计算两个数的乘法用的是如下方法，比如 a = 12，b = 22，a * b通过如下方式计算
19 x 22 ------ 38 38 ------ 418 同样方法也适用于二进制，19 的二进制是 10011，22 的二进制是 10110 ,
10011 x 10110 ------------- 00000 10011 10011 00000 10011 ------------ 110100010 110100010 就是 418。
其本质就是：
b 的二进制值从右往左开始，如果 b 的某一位是 1 ，则把 a 左移一位的值加到结果中，模拟 1 * a，如果 b 的某一位是0，则 a 左移一位的值不加入结果中。 最后累加的结果就是a * b的答案。
位运算实现乘法的完整代码如下
public static 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; } 实现除法
实现除法的时候，为了防止溢出，我们首先把所有数先转换成正数来算。最后在判断两个数的符号决定是否把结果取其相反数。
假设 a / b = c，则 a = b * c，用二进制来说明，假设：
a = b * (2^7) + b * (2^4) + b * (2^1)，则 c 的二进制一定是10010010。
同理，如果
a = b * (2^3) + b * (2^0)，则 c 的二进制一定是1001。
抽象一下，如果a = b * (2 ^ m1) + b * (2 ^ m2) + b * (2 ^ m3)，则 c 的 m1 位置，m2 位置，m3 位置一定是1，其他位置都是0。
所以，我们的思路可以转换成 a 是由几个 (b * 2的某次方)的结果组成，
使用位运算实现除法的核心代码如下：
// 全部转成正数来计算 public static int div(int x, int y) { int a = isNeg(x) ? negNum(x) : x; int b = isNeg(y) ? negNum(y) : y; int res = 0; for (int i = 31; i > negNum(1); i = minus(i, 1)) { if ((a >> i) >= b) { res |= (1 << i); a = minus(a, b << i); } } return isNeg(x) ^ isNeg(y) ? negNum(res) : res; } public static boolean isNeg(int n) { return n < 0; } 其中
if ((a >> i) >= b) { res |= (1 << i); a = minus(a, b << i); } 就是让 a 不断尝试其值是否由(b * 2的某个次方)相加得到。
由于有一些特殊情况，比如在 Java 中，int 类型的系统最小值Integer.MIN_VALUE的相反数依然是Integer.MIN_VALUE。
如果a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE，则a / b应该通过如下方式来计算，先让a + 1
然后算(a + 1) / b = c
接着a - (b * c) = d
然后d / b = e
最后c + e = ((a + 1)/b) + ((a - (b * c)) / b) = a / b
即得到 a / b的值。
根据 LeetCode 题目要求，有如下结论：
Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE。
所以除法的主流程代码如下（主要是根据题目要求和系统最小值的特殊情况进行了一些边界讨论，见注释说明内容）
public static int divide(int dividend, int divisor) { if (divisor == Integer.MIN_VALUE) { // 任何数（除了系统最小）除以系统最小肯定是0 // 系统最小除以系统最小肯定是1 return dividend == Integer.MIN_VALUE ? 1 : 0; } // 除数不是系统最小 if (dividend == Integer.MIN_VALUE) { if (divisor == negNum(1)) { // LeetCode 的题目要求 return Integer.MAX_VALUE; } int res = div(add(dividend, 1), divisor); return add(res, div(minus(dividend, multi(res, divisor)), divisor)); } // dividend不是系统最小，divisor也不是系统最小 return div(dividend, divisor); } 完整代码见
class Solution { public static int add(int a, int b) { int sum = a; while (b != 0) { sum = a ^ b; b = (a & b) << 1; a = sum; } return sum; } public static int negNum(int n) { return add(~n, 1); } public static int minus(int a, int b) { return add(a, negNum(b)); } public static 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; } public static boolean isNeg(int n) { return n < 0; } public static 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 > negNum(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 static int divide(int dividend, int divisor) { if (divisor == Integer.MIN_VALUE) { return dividend == Integer.MIN_VALUE ? 1 : 0; } // 除数不是系统最小 if (dividend == Integer.MIN_VALUE) { if (divisor == negNum(1)) { return Integer.MAX_VALUE; } int res = div(add(dividend, 1), divisor); return add(res, div(minus(dividend, multi(res, divisor)), divisor)); } // dividend不是系统最小，divisor也不是系统最小 return div(dividend, divisor); } // div(a,b) a和b都不能是系统最小 } 
