Division without multiplication, addition or division

Question

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 << i) >= 0)) {
            a = a - (b << i);
            result = result + (1 << i);
        }
    }

    return result;
}


public static int size(int a) {
    // The index of the most left 1 in the binary structure
    int temp = new Integer(a);
    int depth = 0;
    while (a > 0) {
        a >>= 1;
        depth++;
    }
    return depth;
}

Answer 1

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 << i) >= 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 < a) {
    b <<= 1;
    i <<= 1;
}

long result = 0;
for (; i > 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) {
        a = -a;
        negate ^= true;
    }
    if (b < 0) {
        b = -b;
        negate ^= true;
    }

    int i = 1;
    while (b < a) {
        b <<= 1;
        i <<= 1;
    }

    long result = 0;
    for (; i > 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;
    }
}

Answer 2

A few things:

Why not

  int temp = a;

instead of:

  int temp = new Integer(a);

In regard to input validation, I see three things:

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; }

1. Don't put it all on one line, even for 1-liners (Official style guide recommendations from Oracle/Sun, as well as Google, etc.)

2. a = -1 and b = -2 is OK?

3. Division-by-zero should not return 0, it should throw an exception.

Finally, the size() method .... is slow (and does not handle negative inputs). Just replace it with:

public static int size(int a) {
    return 31 - Integer.numberOfLeadingZeros(a);
}

Other issues

These lines have addition:

        result = result + (1 << i);

and

    depth++;