首页 > 代码库 > Leetcode#29 Divide Two Integers
Leetcode#29 Divide Two Integers
原题地址
不用除运算和模运算的除法就退化成最基本的减法
如果除数是1，被除数超大，这做减法还不得累死，所以，用位运算加快速度。
对于被除数和除数都是正数的情况，除法流程为：用位运算生成小于等于当前被除数一半的数字，然后一口气减掉，如此循环往复，直到被除数小于除数。
对于其他被除数和除数当中有负数的情况，为了简便处理可以先将他们求绝对值转化成正数，最后算出结果后再添加符号。
最重要的是考虑溢出问题，32位有符号数字的表示范围是[INT_MIN, INT_MAX]=[-2^32, 2^32-1]=[-2147483648, 2147483647]，注意：INT_MAX比INT_MIN的绝对值少1
如果数字超过这个范围，就会发生溢出。上面的除法算法涉及到两处溢出的地方：
1. 相除的结果恰好是2147483648，发生溢出。
好在这种溢出的情况只有当被除数=INT_MIN，除数=-1的情况下才会发生，所以可以在运算之前通过条件判断直接处理。
2. 被除数或除数=INT_MIN，且将他们转化成正数，发生溢出。
同样地，应尽可能通过条件判断处理这种特殊情况。
如果除数=INT_MIN，只要被除数不等于INT_MIN，相除结果就是0，否则结果是1
如果被除数=INT_MIN，可以先减一个除数，之后再转化成正数就不会溢出了
代码：
1 int divide(int dividend, int divisor) { 2 if (dividend == INT_MIN) { 3 if (divisor == 1 || divisor == -1) 4 return divisor < 0 ? INT_MAX : INT_MIN; 5 if (divisor == INT_MIN) 6 return 1; 7 } 8 else if (divisor == INT_MIN) 9 return 0;10 11 int quotient = 0;12 int degree = 1; 13 bool negative = (dividend >> 31) ^ (divisor >> 31);14 if (dividend == INT_MIN) {15 dividend += divisor > 0 ? divisor : -divisor;16 quotient = 1;17 }18 dividend = dividend > 0 ? dividend : -dividend;19 divisor = divisor > 0 ? divisor : -divisor;20 int nextDivisor = divisor;21 22 for (int d = divisor << 1; d > nextDivisor && d <= dividend; d <<= 1) {23 nextDivisor = d;24 degree <<= 1;25 }26 27 while (dividend >= divisor) {28 if (dividend >= nextDivisor) {29 dividend -= nextDivisor;30 quotient += degree;31 }32 else {33 nextDivisor >>= 1;34 degree >>= 1;35 }36 }37 38 return negative ? -quotient : quotient;39 }
Leetcode#29 Divide Two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。