不用除号乘号完成除法（C++）

这个问题是再力扣剑指offer上看到的，题目是：给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’
第一印象看到这道题标注的是简单题，但我感觉他不简单，看了讲解之后感觉也不是很难。解题开始：
首先一个思想就是不能用乘法，求余，咱们就用减法。
比如29/5=5…4
这个可以看成
29-5=24
24-5=19
19-5=14
14-5=9
9-5=4
所以结果可以是商5余4
大致的思想就有了

  int divide(int a, int b) {
while (a >= b) {
        a -= b;
        res++;
    }
    return res;
    }

这一部分代码也就解决了。
接下来考虑正负数的问题，都是负数的结果没有影响，一整一负对结果有影响，所以开始解决。

 int divide(int a, int b) {
    int sign = 1;
    if((a>0&&b<0) || (a<0&&b>0)){
    		sign = -1;
    }
    //可优化成    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
.
.
.
    }
    return sign*res;
    }

通过一个判断解决正负数问题。
然后就要考虑他的边界问题了，最大值和最小值。定义一个头文件
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
关于INT_MAX和INT_MIN（转载）
代码如下：

int divide(int a, int b) {
    if (a == INT_MIN && b == -1) return INT_MAX;

    int sign = (a > 0) ^ (b > 0) ? -1 : 1;

    if (a > 0) a = -a;
    if (b > 0) b = -b;
    
    unsigned int res = 0;
    while (a <= b) {
        a -= b;
        res++;
    }
    return sign == 1 ? res : -res;
    //用三目运算符解决返回结果需要用到乘号的问题
}

时复杂度：O(n)
空间复杂度：O(1)

这样看来基本上是不是完成了，但是还没有，这样运行在力扣是运行会超时，进行优化，把上面的例子拿下来。
a=29, b=5
29-5=24
24-5=19
19-5=14
14-5=9
9-5=4
优化
a=29, b=5 k=1
29-(5+5） k=k+k=2
29-(10+10)=9 k=k+k=4
29-(20+20)<0
a =9, b=5 k=1
9-(5+5)<0
a=4 ,b=5

从一个一个的减变成两个再变成四个，到零减不了了就停止。关于k的值就是上一个k加上一个k等于新k，成倍增长就优化，降低了时间复杂度。

int divide(int a, int b) {
    if (a == INT_MIN && b == -1) return INT_MAX;
    int sign = (a > 0) ^ (b > 0) ? -1 : 1
    if (a > 0) a = -a;
    if (b > 0) b = -b;
    unsigned int res = 0;
    while (a <= b) {
        int value = b;
        // 如果不用 unsigned 的话，那么当 a = -2147483648, b = 1 的时候，k 会越界
        unsigned int k = 1;
        // 0xc0000000 是十进制 -2^30 的十六进制的表示
        // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
        // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
        // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
        while (value >= 0xc0000000 && a <= value + value) {
            k += k;
            value += value;
        }
        a -= value;
        res += k;
    }
    return sign == 1 ? res : -res;
}

时间复杂度：O(logn * logn)
空间复杂度：O(1)