383，不使用“+”,“-”,“×”,“÷”实现四则运算
Youth, even in its sorrows, always has a brilliancy of its own.
青春，即使在它的悲哀时也是辉煌的。
基础知识
从我们开始上学的时候就知道，如果要实现加法运算就要使用“+”符号，如果要实现减法运算就要使用“-”符号……，甚至在今天的计算机中也是一样的，我们只知道怎么使用，但很少去关注他的底层是怎么实现的。如果突然哪天给你一道面试题，让你不使用"+"来实现两个数相加，你该怎么做呢，今天我们就来看一下该怎么实现。
一：不使用“+”实现两个数相加
我们先来看一道非常简单的题，在计算机中数字是由二进制位表示的，也就是说是由0和1组成的，如果我们要实现0和1之间的加法该怎么实现呢，他会有4种组合方式
1，0+0=00
2，0+1=01
3，1+0=01
4，1+1=10
我们发现一个很重要的规律，就是只有1+1有进位，其他的都没进位。所以我们判断有没有进位只需要判断a&b是否等于1即可，而a+b的值（不考虑进位）只需要计算a|b即可，看明白了这点，代码就呼之欲出了
1private static int add1(int a, int b) {
2 int c = (a & b) << 1;//进位的值
3 int d = a ^ b;//不考虑进位，相加的值
4 return c | d;//或者 return c ^ d;
5}
a和b要么是1要么是0，所以这里最多也只有一个进位，很好理解。但我们计算二进制的加减法不光只有1个0或1，可能会有好多个1或0，那我们该怎么实现呢。比如a=13（1101），b=9（1001），我们该怎么计算a+b的结果。首先如果我们不考虑进位问题，那么a+b的运算会是下面这样
但实际上最前面和最后面的1都有了进位。
1，我们看到如果不考虑进位，那么a+b的结果其实就是a^b的结果，我们该怎么把进位问题也考虑在内呢，实际上只有1+1的时候才会出现进位，1+0或者0+0都不会出现进位，所以我们首先想到的是&运算
2，这里我们计算一下a&b的结果是1001，我们知道当&运算的结果为1的时候，说明参与&运算的两个都是1，既然两个都是1，那么相加的时候就肯定会有进位，所以他们进位的值实际上是10010（（a&b）<<1），然后在和0100相加就是我们要求的结果，10010+00100=10110，10110实际上就是22，也就是13+9的结果
3，但我们好像忽略了一个问题，就是这道题要求不能使用加减乘除符号，而上面我们分析的时候使用了加号，所以明显不行。通过上面的分析实际上我们已经发现了一个规律，就是a+b通过^和&运算之后又再执行相加操作，所以我们首先想到的是递归，我们来看下代码
1private static int add2(int a, int b) {
2 if (a == 0 || b == 0)
3 return a ^ b;
4 return add2(a ^ b, (a & b) << 1);
5}
第3行表示的是如果a==0就返回b，如果b==0就返回a，这种写法少了一个if语句的判断会更简洁。为了验证代码的准确性我们随便找几个数据测试一下
1 int[] array = {1, 1, 1, 0, 0, 1, 0, 0, 13, 9, 1, -1, -Integer.MAX_VALUE, Integer.MAX_VALUE, -8, -9};
2 for (int i = 0; i < array.length / 2; i++) {
3 System.out.println(array[i << 1] + "+" + array[(i << 1) + 1] + "=" + add2(array[i << 1], array[(i << 1) + 1]));
4 }
上面的代码可以不用看，我们来看一下运行结果
经过测试，发现我们的代码完全正确，没有使用“+”实现了两个数相加。上面的递归我们还可以改为非递归的方式
1private static int add3(int a, int b) {
2 while (b != 0) {
3 int temp = a ^ b;
4 b = (a & b) << 1;
5 a = temp;
6 }
7 return a;
8}
这个也很好理解，每次计算的时候要对a和b进行重新赋值，然后再不断的循环，直到b等于0的时候停止循环，我们知道这里在运算的时候b表示的是进位的值，当b等于0的时候就表示没有进位，没有进位就退出循环，这就是使用位运算来实现加法。我们假设a=13，b=9来画个图加深一下理解
二：不使用“-”实现两个数相减
既然加法都实现了，那么减法就更容易了，a-b，直接改为a+(-b)即可，那么请等一下，我们不是说不能使用“-”吗，这里明显有了“-”符号，肯定不符合规则，那么别着急，在计算机中一个数的相反数还可以用另一种方式来表示，那就是
a的相反数是~a+1
上面“+”我们已经实现了，“~”不属于四则运算符，所以代码也很容易写出
1private static int subtraction(int a, int b) {
2 return add3(a, add3(~b, 1));
3}
这种实现就更简洁了，直接一行代码搞定，代码中add3(~b,1)表示的是-b。如果不使用加法是否能实现两个数相减呢，其实也是可以的，我们这样来思考一下，比如a-b
1，如果b等于0，我们直接返回a即可。如果b不等于0，我们可以先把a和b上同为1的数字给去掉，那么怎么去掉呢，其实很简单，我们先要计算c=a&b，那么c中为1的位置在a和b中相对应的位置上也是1，然后再通过异或运算就可以把它给移除。
2，在经过第一步执行之后，a和b在相同的位置上要么都是0，要么一个0一个1，不可能全是1了，那么下面就要会分为3种情况了（我们先不考虑因不够减而借位的问题）
(1)，如果a和b对应的位置上都是0，那么结果对应的位置上也是0。
(2)，如果a对应的位置是1，b对应的位置是0，结果对应的位置是1。
(3)，如果a对应的位置是0，b对应的位置是1，结果对应的位置是1。（向前借一位1）
所以在不考虑借位的情况下，对应位置上的结果其实就是a|b（对应位置都为1的在第一步就已经被踢出了），那么实际计算的时候我们不可能不考虑借位的问题，所以实际结果是(a|b)-(b<<1)，但这里又出现了“-”符号，所以不符合要求，这时我们可以使用递归的方式来解决，代码如下
1private static int subtraction2(int a, int b) {
2 if (b == 0)
3 return a;
4 int c = a & b;
5 //下面两行是把a和b中相同位置为1的都消去
6 a ^= c;
7 b ^= c;
8 return subtraction2(a | b, b << 1);
9}
当然我们还可以把它改为非递归的方式，像下面这样
1private static int subtraction3(int a, int b) {
2 while (b != 0) {
3 int c = a & b;
4 a ^= c;
5 b ^= c;
6 a |= b;
7 b <<= 1;
8 }
9 return a;
10}
我们还是找几组数据来测试一下吧
1 int[] array = {1, 1, 1, 0, 0, 1, 0, 0, 13, 9, 1, -1, Integer.MAX_VALUE, Integer.MAX_VALUE, -8, -9, 100, Integer.MAX_VALUE};
2 for (int i = 0; i < array.length / 2; i++) {
3 System.out.println(array[i << 1] + "-" + array[(i << 1) + 1] + "=" + subtraction2(array[i << 1], array[(i << 1) + 1]));
4 }
上面的我们可以不用看，直接看运行结果就行了
我们以a=13，b=10来画个图加深一下理解
三：不使用“×”实现两个数相乘
我们先来看个例子，比如13*9，计算方式如下
由上面公式我们可以看出只有b的某一位是1的时候和a相乘才有意义，如果b的某一位是0，那么和a相乘则永远都是0，所以我们计算的时候逐步遍历b的每一位，只有当他为1的时候才进行运算，我们来看下代码
1//求一个数的相反数
2private static int negative(int a) {
3 return add3(~a, 1);
4}
5
6private static int mult(int a, int b) {
7 int x = a < 0 ? negative(a) : a;//如果是负数，先转为正数再参与计算
8 int y = b < 0 ? negative(b) : b;
9 int res = 0;
10 while (y != 0) {
11 if ((y & 1) == 1)
12 res = add3(res, x);
13 x <<= 1;
14 y >>= 1;
15 }
16 return (a ^ b) >= 0 ? res : negative(res);
17}
我们还是来找一组数据测试一下，验证我们代码的正确性
1 int[] array = {1, 1, 1, 0, 0, 1, 0, 0, 13, 9, 1, -1, -8, -9, 100, 99};
2 for (int i = 0; i < array.length / 2; i++) {
3 System.out.println(array[i << 1] + "×" + array[(i << 1) + 1] + "=" + mult(array[i << 1], array[(i << 1) + 1]));
4 }
上面代码不用看，我们直接来看一下打印的数据，结果丝毫不差
四：不使用“÷”实现两个数相除
a÷b的含义是a中包含多少个b，比如6÷3=2，7÷3=2，这里我们实现的除法和计算机中两个int类型相除结果是一样的，只记录商的值，余数会被舍去，所以我们想到的一种解法是用a不断的减去b，并记录减了多少次，所以代码很容易想到，我们来看下
1private static int div1(int a, int b) {
2 int x = a < 0 ? negative(a) : a;
3 int y = b < 0 ? negative(b) : b;
4 if (x < y)
5 return 0;
6 return (a ^ b) >= 0 ? div1(subtraction(a, b), b) + 1 : div1(add3(a, b), b) - 1;
7}
上面的+1，-1直接改为上面的加法和减法即可，这里我为了方便阅读代码就没写。这种递归的实现效率不是很高，如果a非常大，b又比较小，很容易出现堆栈溢出异常，所以我们还可以把它改为非递归
1private static int div2(int a, int b) {
2 int x = a < 0 ? negative(a) : a;
3 int y = b < 0 ? negative(b) : b;
4 int ocunt = 0;
5 while (x >= y) {
6 x = subtraction3(x, y);
7 ocunt++;
8 }
9 return (a ^ b) >= 0 ? ocunt : -ocunt;
10}
这种虽然不会出现堆栈溢出异常了，但如果b是1，a是一个非常非常大的数，这样一直减下去也是非常慢的，我们还可以换种思路，每次减去的不是b，而是b的倍数，我们来看下代码
1private static int div3(int a, int b) {
2 if (a == 0 || b == 0)
3 return 0;//b不能为0，如果b是0我们应该抛异常的，这里简单处理就没抛
4 int x = a < 0 ? negative(a) : a;
5 int y = b < 0 ? negative(b) : b;
6 int result = 0;
7 for (int i = 31; i >= 0; i--) {
8 if ((x >> i) >= y) {
9 result = add3(result, 1 << i);
10 x = subtraction3(x, y << i);
11 }
12 }
13 return (a ^ b) >= 0 ? result : -result;
14}
我们找一组非常极端的数据来测一下上面两种方法，看一下效率到底相差多少倍
1 int a = Integer.MAX_VALUE;
2 int b = 1;
3 long time = System.nanoTime();
4 System.out.println(a + "÷" + b + "=" + div2(a, b));
5 System.out.println("优化之前的时间：" + (System.nanoTime() - time));
6 time = System.nanoTime();
7 System.out.println(a + "÷" + b + "=" + div3(a, b));
8 System.out.println("优化之后的时间：" + (System.nanoTime() - time));
我们来看一下结果
这个时间相差还是非常大的，一个30多亿纳秒，一个两万多纳秒，相差十几万倍。最后我们再找一组数据测试一下我们的代码是否正确
1 int[] array = {1, 1, 0, 1, 13, 9, 40, 3, 1, -1, -8, -9, 100, 99};
2 for (int i = 0; i < array.length / 2; i++) {
3 System.out.println("div2方法测试：" + array[i << 1] + "÷" + array[(i << 1) + 1] + "=" + div2(array[i << 1], array[(i << 1) + 1]));
4 }
5 System.out.println("----------------------------------------");
6 for (int i = 0; i < array.length / 2; i++) {
7 System.out.println("div3方法测试：" + array[i << 1] + "÷" + array[(i << 1) + 1] + "=" + div3(array[i << 1], array[(i << 1) + 1]));
8 }
我们来看下运行结果
结果和我们预想的完全一致。
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧