整数除法的原理

资源来源于 LeetCode29 —— Divide Two Integers. 题目描述如下所示：

这道题让我们求两数相除，而且规定我们不能用乘法，除法和取余操作，比较直接的方法是用被除数一直减去除数，直到为0。这种方法有极端情况，比如除数为1，被除数接近 INT_MAX，则此时复杂度为 O(n) . 除此之外，我们还可以用另一神器位操作 Bit Operation，思路是，如果被除数大于或等于除数，则进行如下循环，定义变量 t 等于除数，定义计数 p，当 t 的两倍小于等于被除数时，进行如下循环，t 扩大一倍，p 扩大一倍，然后更新 result 和被除数 m （我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即 num=a0∗20+a1∗21+a2∗22+...+an∗2n ）。这道题需要注意测试用例的全面性，比如，被除数为 -2147483648，在 int 范围内，当除数是-1时，结果就超出了 int 范围，需要返回 INT_MAX。然后我们还要根据被除数和除数的正负来确定返回值的正负，这里我们采用长整型 long long 来完成所有的计算，最后返回值乘以符号即可。

C++代码示例：

int divide(int dividend, int divisor) { long long m = abs((long long)dividend); long long n = abs((long long)divisor); long long result = 0; if (m < n) { return 0; } if (n == 0) { return INT_MAX; } while (m >= n) { long long t = n, p = 1; // 再次进入循环时，重置 t 和 p 的值 while (m >= (t << 1)) { t <<= 1; p <<= 1; } m -= t; result += p; } if ((dividend < 0) ^ (divisor < 0)) { // 异或运算 result = - result; } return result > INT_MAX ? INT_MAX : (int)result; }

这里对异或运算做一个回顾：

异或运算符（^） 参加运算的两个数据，按二进制位进行“异或”运算。 运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0； 即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。