0029.两数相除

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

方法一：快速幂

除法本质上就是减法，题目要求我们计算出两个数相除之后的取整结果，其实就是计算被除数是多少个除数加上一个小于除数的数构成的。但是一次循环只能做一次减法，效率太低会导致超时，可借助快速幂的思想进行优化。

需要注意的是，由于题目明确要求最大只能使用 32 位有符号整数，所以需要将除数和被除数同时转换为负数进行计算。因为转换正数可能会导致溢出，如当被除数为 INT32_MIN 时，转换为正数时会大于 INT32_MAX。

时间复杂度 $O(\log dividend \times \log divisor)$ ，空间复杂度 $O(1)$ 。


func divide(a int, b int) int {
	sign, ans, INT32_MAX, INT32_MIN, LIMIT := false, 0, 1<<31-1, -1<<31, -1<<31/2
	if (a > 0 && b < 0) || (a < 0 && b > 0) {
		sign = true
	}
	a, b = convert(a), convert(b)
	for a <= b {
		cnt := 0
		// (b<<cnt) >= LIMIT 是为了避免 b<<(cnt+1) 发生溢出
		for (b<<cnt) >= LIMIT && a <= (b<<(cnt+1)) {
			cnt++
		}
		ans = ans + -1<<cnt
		a = a - b<<cnt
	}
	if sign {
		return ans
	}
	if ans == INT32_MIN {
		return INT32_MAX
	}
	return -ans
}

func convert(v int) int {
	if v > 0 {
		return -v
	}
	return v
}