leetcode: Divide Two Integers

问题描述：

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

原问题链接：https://leetcode.com/problems/divide-two-integers/

 

问题分析

    这个问题和之前做过的一些问题有类似的地方。就是在程序里会碰到很多溢出的情况。一种典型的方法就是将当前类型的数值转换成long类型。既然这里不让用乘、除等运算。所以最简单的一种运算就是用循环减法。但是如果dividend很大而divisor很小的情况下，这里执行的速度会非常慢。

　　所以在这一点上也有一个可以改进的地方，就是移位运算。首先将divisor向左移位，移动一位相当于乘以２。通过判断dividend > (divisor << shift)这样可以得到一个值 1<<shift。这样通过循环可以更快的得出结果。

　　还有一个要注意的细节就是除数和被除数的符号。如果它们两个的符号不同，我们需要记录下来。具体的实现代码如下：

 

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        boolean neg = (dividend < 0) ^ (divisor < 0);
        long m = Math.abs((long)dividend), n = Math.abs((long)divisor);
        long result = 0;
        while (m >= n) {
            int shift = 0;
            while (m > (n << shift + 1)) {
                shift++;
            }
            m -= n << shift;
            result += (1 << shift);
        }
        result = (neg) ? ~(result - 1) : result;
        result = Math.min(Integer.MAX_VALUE, result);
        result = Math.max(Integer.MIN_VALUE, result);
        return (int)result;
    }
}

  

 

评论

2 楼 frank-liu 2017-06-20  

shihengli2010 写道

boolean neg = (dividend < 0) ^ (divisor < 0);  //判断符号是否相同，值得学习。

result = (neg) ? ~(result - 1) : result;  //疑惑为什么不是-result，而是~(result - 1)

因为这里是对result的值取负，实现result * (-1)的效果，直接用二进制的~得到的只是原来数字二进制的反码，但不是真正的数值上的取负。你试试输出Integer.toBinaryString(1)和Integer.toBinaryString(-1)的值就会发现。

1 楼 shihengli2010 2017-06-20  

boolean neg = (dividend < 0) ^ (divisor < 0);  //判断符号是否相同，值得学习。

result = (neg) ? ~(result - 1) : result;  //疑惑为什么不是-result，而是~(result - 1)