Divide Two Integers 解答

Question

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

If it is overflow, return MAX_INT.

Solution

dividend = divisor * quotient + remainder

而我们知道对于任何一个数可以表示为Σi * 2^x 其中i为0或1。所以我们可以用加法实现乘法。

a = a + a 等同于 a = a * 2

因此我们可以通过对divisor乘以2，求出最大的x，然后继续求出第二大，第三大的x', x''..

注意到可能有溢出问题，解决方法是将要计算的所有数先转为long。

 public class Solution {

     public int divide(int dividend, int divisor) {

         boolean negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);

         long a = Math.abs((long)dividend);

         long b = Math.abs((long)divisor);

         if (a < b) {

             return 0;

         }

         long step, sum, result = 0;

         while (a >= b) {

             step = b;

             sum = 1;

             while (step + step <= a) {

                 step += step;

                 sum += sum;

             }

             a = a - step;

             result += sum;

         }

         result = negative == true ? -result : result;

         if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {

             return Integer.MAX_VALUE;

         }

         return (int)result;

     }

 }

巴特西

Divide Two Integers 解答

Question

Solution

最新文章

热门文章