整数除法的原理

xiaoxiao2021-02-28  16

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

这道题让我们求两数相除,而且规定我们不能用乘法,除法和取余操作,比较直接的方法是用被除数一直减去除数,直到为0。这种方法有极端情况,比如除数为1,被除数接近 INT_MAX,则此时复杂度为 O(n) . 除此之外,我们还可以用另一神器位操作 Bit Operation,思路是,如果被除数大于或等于除数,则进行如下循环,定义变量 t 等于除数,定义计数 p,当 t 的两倍小于等于被除数时,进行如下循环,t 扩大一倍,p 扩大一倍,然后更新 result 和被除数 m (我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合,即 num=a020+a121+a222+...+an2n )。这道题需要注意测试用例的全面性,比如,被除数为 -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。

转载请注明原文地址: https://www.6miu.com/read-2800107.html

最新回复(0)