LeetCode: Divide Two Integers 解题报告

Divide Two Integers

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

SOLUTION 1
1. 基本思想是不断地减掉除数，直到为0为止。但是这样会太慢。

2. 我们可以使用2分法来加速这个过程。不断对除数*2，直到它比被除数还大为止。加倍的同时，也记录下cnt，将被除数减掉加倍后的值，并且结果+cnt。

因为是2倍地加大，所以速度会很快，指数级的速度。

3. 另外要注意的是：最小值的越界问题。对最小的正数取abs，得到的还是它。。。 因为最小的正数的绝对值大于最大的正数（INT）

所以，我们使用Long来接住这个集合就可以了。

 public class Solution {
     public int divide(int dividend, int divisor) {
         long a = Math.abs((long)dividend);

         // ref : http://blog.****.net/kenden23/article/details/16986763
         // Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值
         long b = Math.abs((long)divisor);

         int ret = 0;
         // 这里必须是= 因为相等时也可以减
         while (a >= b) {
             // 判断条件是 >=
             for (long deduce = b, cnt = 1; a >= deduce; deduce <<= 1, cnt <<= 1) {
                 a -= deduce;
                 ret += cnt;
             }
         }

         // 获取符号位。根据除数跟被除数的关系来定
         return (dividend > 0) ^ (divisor > 0) ? -ret: ret;
     }
 }

注意：

1. C,java中的右移运算，是带符号位的，叫算术右移http://www.cppblog.com/tx7do/archive/2006/10/19/13867.html

2015.1.3 redo:

Leetcode又加强了一大堆边界条件运算，所以我们代码也要更改：

1. 返回值的时候，判断是不是越界，越界返回最大值。

例子：

Input: -2147483648, -1
Expected: 2147483647

 public int divide(int dividend, int divisor) {
         if (divisor == 0) {
             return Integer.MAX_VALUE;
         }

         // Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值
         long dividendTmp = Math.abs((long)dividend);
         long divisorTmp = Math.abs((long)divisor);

         // bug 3: ret should use Long to avoid overflow.
         long ret = 0;
         // bug 2: should use dividentTmp > divisor as the while judge.
         while (dividendTmp >= divisorTmp) {
             // bug 1: should use Long for tmp.
             long tmp = divisorTmp;
             int rst = 1;
             while(tmp <= dividendTmp) {
                 // bug 3: the two statement should inside the while LOOP.
                 ret += rst;
                 dividendTmp -= tmp;

                 tmp <<= 1;
                 rst <<= 1;
             }
         }
         // bug 4: out of range:
         /*
         Input:    -2147483648, -1
         Output:    -2147483648
         Expected:    2147483647
         */
         //ret = ((dividend > 0) ^ (divisor > 0)) ? -ret: ret;
         ret = ((((dividend ^ divisor) >> 31) & 1) == 1) ? -ret: ret;

         if (ret > Integer.MAX_VALUE || ret < Integer.MIN_VALUE) {
             return Integer.MAX_VALUE;
         } else {
             return (int)ret;
         }
     }

简化一点：

 public int divide(int dividend, int divisor) {
         long a = Math.abs((long)dividend);
         long b = Math.abs((long)divisor);

         long ret = 0;

         while (a >= b) {
             for (long tmp = b, cnt = 1; a >= tmp; tmp <<= 1, cnt <<= 1) {
                 ret += cnt;
                 a -= tmp;
             }
         }

         ret = (((dividend ^ divisor) >> 31) & 1) == 1 ? -ret: ret;
         if (ret > Integer.MAX_VALUE || ret < Integer.MIN_VALUE) {
             return Integer.MAX_VALUE;
         }

         return (int)ret;
     }

GitHub Code:

divide.java

Ref: http://blog.****.net/fightforyourdream/article/details/16899675