Divide Two Integers

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

If it is overflow, return MAX_INT.

Solution: shift

We can keep subtract divisor from dividend until dividend is smaller than 0, than count the subtract numbers. But it will costs a very long time if the divisor is very small comparing to dividend.

keep multiplying divisor by 2 until divisor is larger than dividend, then divide it by 2
compute the difference between divisor and dividend, set it as the new dividend. In fact, every integer can be represented by a set of base 2 so that shifting can be used.

Shift can be used to solve this problem. We shift the divisor left until it just smaller than dividend but if we keep shifting one more bit, it’s larger than dividend. Than we can add the shifted value to the result and subtract the shifted value from dividend. Keep doing this until dividend is smaller than divisor. 

One thing needs to be mentioned is that we need to convert the integer to long type. Otherwise the Math.abs() value of Integer.MIN_VALUE will be quite strange.

The complexity is O(log n).

public class Solution {
    public int divide(int dividend, int divisor) {
        boolean isNeg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long dv = Math.abs((long) dividend);
        long ds = Math.abs((long) divisor);
        
        long remain = dv;
        int res = 0;
        
        while(remain >= ds) {
            int shift = -1;
            long v = remain;
            while( v >= ds) {
                v = v >> 1;
                shift++;
            }
            remain -= (ds << shift);
            res += (1 << shift);
        }
        
        if(!isNeg && res >= Integer.MAX_VALUE)
            return Integer.MAX_VALUE;
        else if(!isNeg && res <= Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        else if(!isNeg)
            return res;
        else
            return -res;
    }
}

java中有三种移位运算符

<<      :     左移运算符，num << 1,相当于num乘以2

>>      :     右移运算符，num >> 1,相当于num除以2

>>>    :     无符号右移，忽略符号位，空位都以0补齐

43210      位数
--------
 1010      十进制：10     原始数         number
10100      十进制：20     左移一位       number = number << 1;
 1010      十进制：10     右移一位       number = number >> 1;