Division without multiplication, addition or division

In context of preparing for a coding interview, I gave the division problem a go using Java. This is what I came up with. It's a little bit different to other solutions I've come across the interweb.


Implement integer division without using multiplication or repeated subtraction (i.e. to divide n by d, you man not repeatedly subtract off d from n).

public static int division(int a, int b) {

    // For the basic cases
    if (b == 1) { return  a; }
    if (a == 1) { return  b; }
    if (a == 0 || b== 0) { return  0; }
    if (b > a)  { return  0; }
    if (a == b) { return  1; }

    int result = 0;
    int size = size(a) - 1;
    for (int i = size(a) - size(b); i >= 0; i--) {
        if((a - (b = 0)) {
            a = a - (b  0) {
        a >>= 1;
        depth++;
    }
    return depth;
}

If you run

Random rand = new Random();
for (int i = 0; i < 100; i++) {
    int a = rand.nextInt();
    int b = rand.nextInt();
    System.out.println(a + " / " + b + " == " + division(a, b) + " == " + a / b);
}

You'll see very clearly that the code is buggy. Investigate this yourself, and then come back to this post.

if (a == 1) { return  b; }

Is simply wrong.

if (a == 0 || b== 0) { return  0; }

should throw a java.lang.ArithmeticException: / by zero in the latter case. It should do so before checking a.

if (b > a)  { return 0; }

Covers the case of a == 0, as long as you ignore negatives - so remove the a == 0 check.

You don't even need these checks, though, so remove them.

You don't use

int size = size(a) - 1;

and it's also really bad style to have both an integer and a function of the same name anyway.

a = a - (b << i);
result = result + (1 << i);

should use -= and +=.

a - (b = 0

should be

a >= b << i

One then has

public static int division(int a, int b) {
    if (b == 0) {
        throw new java.lang.ArithmeticException("/ by zero");
    }

    int result = 0;
    for (int i = size(a) - size(b); i >= 0; i--) {
        if (a >= b << i) {
            a -= b << i;
            result += 1 << i;
        }
    }

    return result;
}

One should deal with negative numbers. This looks as simple as

boolean negate = false;
if (a < 0) {
    a = -a;
    negate ^= true;
}
if (b < 0) {
    b = -b;
    negate ^= true;
}

...

if (negate) {
    return -result;
} else {
    return result;
}

However, this fails for INT_MIN since -INT_MIN == INT_MIN!

What to do? It seems like one could flip into the negatives instead, and flip all of the comparisons. I don't think this would work, though, since

a = INT_MIN
b = INT_MIN + 1

would result in i = 1, resulting in running b << 1, which overflows. This doesn't just happen with INT_MIN either.

The simplest thing, then, might be to flip to positive after casting to long. One can also simplify things by removing size, then, in favour of some fiddling with b like:

int i = 1;
while (b  0; i >>= 1, b >>= 1) {
    if (a >= b) {
        a -= b;
        result += i;
    }
}

All in all, one gets the unfortunately long

public static int division(int left, int right) {
    // Prevent overflow on negation
    long a = left;
    long b = right;

    if (b == 0) {
        throw new java.lang.ArithmeticException("/ by zero");
    }

    // Normalize to positive longs.
    boolean negate = false;
    if (a  0; i >>= 1, b >>= 1) {
        if (a >= b) {
            a -= b;
            result += i;
        }
    }

    if (negate) {
        // Should not overflow
        return (int)-result;
    } else {
        // Truncation might overflow if
        // result is -(long)Integer.MIN_VALUE,
        // but this is correct
        return (int)result;
    }
}

StackExchange Code Review Q#94523, answer score: 11