package com.fishercoder.solutions;

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

 If it is overflow, return MAX_INT.
 */
public class _29 {

    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {
            return Integer.MAX_VALUE;
        }
        if (dividend != Integer.MIN_VALUE
                && Math.abs(dividend) < Math.abs(divisor)) {
            return 0;
        }
        if (divisor == Integer.MIN_VALUE) {
            return (dividend == Integer.MIN_VALUE) ? 1 : 0;
        }
        //
        boolean flag = (dividend < 0) ^ (divisor < 0);
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);
        int[] num = new int[40];
        int[] multiple = new int[40];
        num[1] = divisor;
        multiple[1] = 1;
        for (int i = 2; i < 32 && num[i - 1] < 0; ++i) {
            num[i] = num[i - 1] << 1;
            System.out.print("num[" + i + "]:" + num[i]);
            multiple[i] = multiple[i - 1] << 1;
            System.out.println("\tmultiple[" + i + "]" + multiple[i]);
        }
        int result = 0;
        int index = 1;
        while (num[index] < 0) {
            ++index;
        }
        index -= 1;
        while (dividend <= divisor) {
            while (dividend <= num[index]) {
                result += multiple[index];
                dividend -= num[index];
            }
            --index;
        }
        return !flag ? result : -result;
    }
}

@@ -33,16 +33,46 @@
 s;%0A%0A/**%0A
+ * 29. Divide Two Integers%0A *%0A
  * Divid
@@ -143,17 +143,18 @@
 erator.%0A
-%0A
+ *
  If it i
@@ -205,16 +205,50 @@
  _29 %7B%0A%0A
+  public static class Solution1 %7B%0A
     publ
@@ -286,26 +286,24 @@
  divisor) %7B%0A
-  
       if (di
@@ -372,28 +372,24 @@
 ) %7B%0A        
- 
-   
 return Integ
@@ -402,18 +402,16 @@
 _VALUE;%0A
-  
       %7D%0A
@@ -408,34 +408,32 @@
 ;%0A      %7D%0A      
-  
 if (dividend != 
@@ -460,22 +460,16 @@
         
-  
-    
 && Math.
@@ -509,28 +509,24 @@
 ) %7B%0A        
-    
 return 0;%0A  
@@ -519,26 +519,24 @@
   return 0;%0A
-  
       %7D%0A    
@@ -533,26 +533,24 @@
     %7D%0A      
-  
 if (divisor 
@@ -569,28 +569,24 @@
 IN_VALUE) %7B%0A
-    
         retu
@@ -639,25 +639,11 @@
     
-  %7D%0A        //%0A  
+%7D%0A%0A
     
@@ -693,26 +693,24 @@
 %3C 0);%0A      
-  
 dividend = -
@@ -731,26 +731,24 @@
 end);%0A      
-  
 divisor = -M
@@ -767,26 +767,24 @@
 sor);%0A      
- 
- 
 int%5B%5D num = 
@@ -792,26 +792,24 @@
 ew int%5B40%5D;%0A
-  
       int%5B%5D 
@@ -834,26 +834,24 @@
 %5B40%5D;%0A      
- 
- 
 num%5B1%5D = div
@@ -858,26 +858,24 @@
 isor;%0A      
-  
 multiple%5B1%5D 
@@ -875,26 +875,25 @@
 ple%5B1%5D = 1;%0A
-  
+%0A
       for (i
@@ -931,28 +931,24 @@
 %3C 0; ++i) %7B%0A
-    
         num%5B
@@ -981,195 +981,59 @@
     
-    System.out.print(%22num%5B%22 + i + %22%5D:%22 + num%5Bi%5D);%0A            multiple%5Bi%5D = multiple%5Bi - 1%5D %3C%3C 1;%0A            System.out.println(%22%5Ctmultiple%5B%22 + i + %22%5D%22 + multiple%5Bi%5D);%0A        %7D%0A 
+multiple%5Bi%5D = multiple%5Bi - 1%5D %3C%3C 1;%0A      %7D%0A%0A
       
- 
 int 
@@ -1046,26 +1046,24 @@
  = 0;%0A      
-  
 int index = 
@@ -1061,26 +1061,24 @@
  index = 1;%0A
-  
       while 
@@ -1092,28 +1092,24 @@
 dex%5D %3C 0) %7B%0A
-    
         ++in
@@ -1115,30 +1115,26 @@
 ndex;%0A      
-  %7D%0A  
+%7D%0A
       index 
@@ -1135,26 +1135,25 @@
 index -= 1;%0A
-  
+%0A
       while 
@@ -1184,20 +1184,16 @@
         
-   
- 
 while (d
@@ -1227,22 +1227,16 @@
         
-      
 result +
@@ -1264,22 +1264,16 @@
         
-   
-   
 dividend
@@ -1300,25 +1300,18 @@
     
-    %7D%0A   
+%7D%0A
         
  --i
@@ -1306,17 +1306,16 @@
         
- 
 --index;
@@ -1317,30 +1317,26 @@
 ndex;%0A      
-  %7D%0A  
+%7D%0A
       return
@@ -1368,10 +1368,14 @@
 ;%0A    %7D%0A
+  %7D%0A
 %7D%0A

refactor 29