[LeetCode]Divide Two Integers

题目链接

数值的问题很多时候我们都要考虑二分和位运算的解法，这道题也是一样的。既然我们要implement除法并且不能用*, /, %，那么显而易见我们应该用减法。那么我们不能每一次用被除数减去除数直到被除数小于除数，因为太慢了。首先我们可以考虑二分，比如 12 / 4，我们就可以考虑先计算12 / 8，然后12 / 4 = 2 * 12 / 8 + (12 % 8) / 4。也就是说每一次n / d，我们考虑n / 2d直到商为1为止，然后回溯看下一层回来的余数还能不能给结果加1，假设被除数是n，时间复杂度O(log n)，代码如下：

另一种方法，假设被除数为n，除数为m，那么我很需要求d，使得n = d * m。d可以表示为a0 * 2^0 + a1 * 2^1 + a2 * 2^2 + ... + ak * 2 ^ k, where ai = [0, 1]，我们只需要把ai都求出来即可。 根据之前的等式，我们有n = (a0 * 2^0 + a1 * 2^1 + a2 * 2^2 + ... + ak * 2 ^ k) * m = a0 * 1m  + a1 * 2m + a2 * 4m + ... + ak * 2^k * m，我们可以每次对除数乘以2，直到其正好再乘一次就大于除数了，假设当前除数为2^i * m，当前的d加上2^i即可，代表对应的ai为1。每次减去除数直到除数小于被除数，乘以2的操作我们用位运算就可以完成，时间复杂度O((log n)^2)，代码如下：