4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Isn't depth++ addition? \$\endgroup\$ – OldCurmudgeon Jun 24 '15 at 14:57
  • \$\begingroup\$ First thing I'd do: int add(int a, int b) { return - (-a - b); } \$\endgroup\$ – NovaDenizen Jun 24 '15 at 23:25
  • \$\begingroup\$ I've clarified the question in my edit. \$\endgroup\$ – Paul Jun 25 '15 at 0:28
11
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I am a bit embarrassed now looking back at my code. Should have reviewed in myself more thoroughly before submitting. Thanks for all the great advice. \$\endgroup\$ – Paul Jun 25 '15 at 0:33
8
\$\begingroup\$

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++;
\$\endgroup\$
  • 1
    \$\begingroup\$ I wouldn't see a reason to do this in Java, but in VHDL (and possibly ASM) there can be advantages to dividing by bit-shifting and comparison. \$\endgroup\$ – Mast Jun 24 '15 at 10:49
  • 2
    \$\begingroup\$ @rolfl Why is it not okay to put the if statement on 1-line? When the block of the if-statement just contains 1 line, I find it easier to read when it's just on the same line. \$\endgroup\$ – DSF Jun 24 '15 at 13:01
  • \$\begingroup\$ int temp = new Integer(a);: temp isn't used so eliminate it completely. \$\endgroup\$ – wallyk Jun 24 '15 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.