Divide Two Integers

So no multiplication, no division, nor mod. What is the only option? Bitwise operation!

For any integer, or long, "<< n" means multiply by 2 ^ n. And ">> n" means divide by 2 ^ n.


dividend = 45, divisor = 7
shift = 3, 7 * 2 * 2 * 2 = 56 > 45, the number of 7 that add up to be larger than 56 is 2 * 2 * 2 = 8
ans = 2 * 2 = 4,  a = 45 - 7 * 2 * 2= 17
shift = 2, 7 * 2 * 2 = 28 > 17,
ans = 4 + 2 = 6,  a = 17 - 7 * 2 = 3 < divisor

Note that since it is possible to overflow, we need to convert both dividend and divisor to long. ans should also be long type.


Update 2016-05-23:
45 ~ 7 * 6 = 7 * (2^2 + 2 ^ 1).

public int divide(int dividend, int divisor) {
        if (divisor == 0)
            return Integer.MAX_VALUE;
        boolean isNegative = (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 ans = 0;
        while (a >= b) {
            int shift = 0;
            while ((b << shift) <= a) 
                shift++;
            ans += ((long)1 << (shift - 1));
            a = a - (b << (shift - 1));
        }
        if (!isNegative && ans > (long)Integer.MAX_VALUE)
            return Integer.MAX_VALUE;
        return isNegative ? (int)-ans : (int)ans;
    }