资源来源于 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 ）。这道题需要注意测试用例的全面性，比如，被除数为 -，在 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。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/54374.html