https://leetcode.cn/problems/divide-two-integers/

法一：位运算

加法

1. ^ 无进位相加
1. & << 1 进位相加
将第一步和第二步加起来
例子1：

例子2：

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 << 0 , b >> 0
a << 1， b >> 1

a << 2, b>>2

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不是系统最小，怎么算？ 1.先把a+1 ，然后去除b ——> 得到值A
   2. a - (A * b) = 值B    
   3.  B / b  + A

除法：

先把数都转成正的，来除比较稳
所以除的流程是什么呢？
- 比如a/b
- 准备一个变量
- 先让 b往左移动x位，直到不能再移（最接近a）记作T，然后在上面那个变量对象x位置写上1
- 然后 a’ = a - T
- 然后再让b往左移动去够a’ , 继续上面那个流程
为啥是这个流程呢？看下面两个图
- ```java public static int minus(int a, int b) { return add(a, negNum(b)); } // 求相反数 private static int negNum(int n) { return add(~n, 1); }

public static int div(int a, int b) { int x = a < 0 ? negNum(a) : a; int y = b < 0 ? negNum(b) : b; int res = 0; for (int i = 31; i > -1; i = minus(i, 1)) { if (x >> i >= y) { res |= (1 << i); x = minus(x, y << i); } } return (a < 0) ^ (b < 0) ? 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 == -1) { return Integer.MAX_VALUE; } int res = div(add(dividend, 1), divisor); return add(res, div(minus(dividend, multi(res, divisor)), divisor)); } // 两个都不是系统最小 return div(dividend, divisor); }


- 总代码
```java
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 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 int minus(int a, int b) {
    return add(a, negNum(b));
}
private static int negNum(int n) {
    return add(~n, 1);
}
public static int div(int a, int b) {
    int x = a < 0 ? negNum(a) : a;
    int y = b < 0 ? negNum(b) : b;
    int res = 0;
    for (int i = 31; i > -1; i = minus(i, 1)) {
        if (x >> i >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return (a < 0) ^ (b < 0) ? 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 == -1) {
            return Integer.MAX_VALUE;
        }
        int res = div(add(dividend, 1), divisor);
        return add(res, div(minus(dividend, multi(res, divisor)), divisor));
    }
    // 两个都不是系统最小
    return div(dividend, divisor);
}

法二：递归

每次除数翻倍增加，指数级逼近被除数 ```java public static int divide1(int dividend, int divisor) { if (dividend == 0 ) return 0; if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; int isNeg = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
```
  isNeg = -1;
```
} dividend = dividend > 0 ? -dividend : dividend; divisor = divisor > 0 ? -divisor : divisor; return isNeg == -1 ? -div1(dividend, divisor) : div1(dividend, divisor);

}

// a, b都是负数 private static int div1(int a, int b) { if (a >= b) return a > b ? 0 : 1; int count = 1; int res = 0; int tb = b; // 每次除数和结果都翻倍，指数级逼近，比较快 // tb < 0 防止溢出 while (a <= tb && tb < 0) { a -= tb; res += count; tb += tb; count += count; } return res + div1(a, b); }

```

力扣Top_Hot总系列

29.⭐两数相除

法一：位运算

法二：递归