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

• Isn't depth++ addition? Commented Jun 24, 2015 at 14:57
• First thing I'd do: int add(int a, int b) { return - (-a - b); } Commented Jun 24, 2015 at 23:25
• I've clarified the question in my edit.
– Paul
Commented Jun 25, 2015 at 0:28

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

• 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.
– Paul
Commented Jun 25, 2015 at 0:33

A few things:

Why not

  int temp = a;


  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) {
}


## Other issues

        result = result + (1 << i);

    depth++;

• int temp = new Integer(a);: temp isn't used so eliminate it completely. Commented Jun 24, 2015 at 17:23