8
\$\begingroup\$

This is a follow-up to this question:

Division without using addition, multiplication or division

Could you please tell me if there is better way of performing division without +,-, * or /?

I've tested this code for different values of a and b. I've also tested working for:

  1. divide(8,3)
  2. divide(5,10)
  3. divide(9,6)
  4. divide(42,6)

Could you please tell me if there is a cleaner solution?

private static int divide(int a , int b){

    boolean isNeg=false;
    boolean sign=true;
    boolean bothNegative=false;
    int quotient=1;


    if(a<0 && b<0){
        bothNegative=true;
    }
    else if(a<0 || b<0) {

        isNeg=true;
        sign=true;

    }

    a=Math.abs(a);
    b=Math.abs(b);


    if(a<b) return 0;
    else{

        int s=add(a,-b);
        int divisor =b;

        while(Math.abs(s)>=Math.abs(divisor)){
            b=add(b,divisor);
            s=add(a,-b);
            quotient=add(quotient,1);
             if(isNeg){
                sign=!sign;
            }
        }

        if(bothNegative){
            return quotient;

        }else if(isNeg && !sign){
            quotient=add(0,-quotient);
         }

        return quotient;
    }

}


private static int add(int a , int b){

    do{

        a^=b;
        b&=(a^b);
        b<<=1;

     }while(Math.abs(b)!=0);

    return a;
}
\$\endgroup\$
1
  • \$\begingroup\$ You seem to be using the - operator in it's unary form. Is this a specific exception in the question or a bug? It should be possible enough to implement two's compliment using bitwise operators. \$\endgroup\$ Commented Jun 30, 2014 at 12:02

2 Answers 2

Reset to default
12
\$\begingroup\$

Seems like the approach you've taken is to implement the + operator yourself. And when using the + operator on negative numbers, you've implemented your own - operator.

I have to congratulate you for being able to implement these operators from scratch. Good job.

A slight bug is that your code returns incorrect result for divide(-42, 6)

I believe the source of this bug is that this code is inside the while:

if (isNeg) {
    sign=!sign;
}

Put it outside the while and it seems to work (at least for my test case)

if (a < b) return 0;
else{

You can save yourself some trouble indentation by removing that else. As you return, you can keep on going without adding indentation. (Which is why I love early returns)

Your spacing is a bit off, the easiest way to fix this is to press Ctrl + Shift + F if you're using Eclipse, or Alt + Shift + F if you're using Netbeans.

For example, this line:

while(Math.abs(s)>=Math.abs(divisor)){

Would look better like this:

while (Math.abs(s) >= Math.abs(divisor)) {

quotient = add(0, -quotient);

As you're using a - sign there already, why not replace all this with -quotient?

You have three boolean values related to the positive/negative issue:

boolean isNeg = false;
boolean sign = true;
boolean bothNegative = false;

Only one would be enough:

boolean swapSign = a < 0 ^ b < 0;

This is using the boolean XOR operator (^), so this will be true if a is negative or b is negative, but not if both are negative.

int quotient = 1;
if (a < b) {
    return 0;
}

You're using a < b as a special case, but that's not necessary.

int s;

That's not a readable name.

You can get rid of several unnecessary variables by directly operating on the a and b values. As they're ints, they're value-typed and therefore copied and not sent by reference, which means that you can modify them however you'd like inside your method. They can be used just like normal local variables.

The main part of your method can be simply this:

a = Math.abs(a);
b = Math.abs(b);

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

Your logic for what to return is a bit bloated:

if (bothNegative) {
    return quotient;
}
else if (isNeg && !sign) {
    quotient = add(0, -quotient);
}
return quotient;

This can be replaced with, by using the single swapSign variable:

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

Or even simpler, using the ternary operator:

return swapSign ? -result : result;

End result:

private static int divide(int a, int b) {
    boolean swapSign = a < 0 ^ b < 0;
    a = Math.abs(a);
    b = Math.abs(b);
    int result = 0;
    while (a >= b) {
        a = add(a, -b);
        result = add(result, 1);
    }
    return swapSign ? -result : result;
}
\$\endgroup\$
11
\$\begingroup\$

Yes, there's a better way to do this.

Ignoring, for the moment, the minor details about not using addition and subtraction, the algorithm you're using right now is basically just repeated subtraction, roughly equivalent to:

while (a >= b) {
     a -= b;
     ++result;
}

This can (and will) be pretty slow if a is a lot larger than b. For example, to divide one million by two, it executes half a million iterations of the loop. Even though each iteration is pretty fast, that's still going to take a while.

What you normally want to use is a shift and subtract algorithm, pretty much like long decimal division the way we (at least used to) learn it in in school. Much like decimal division, this produces one digit per iteration (though when you do it in binary, that's one binary digit per iteration instead of one decimal digit).

This looks more like this:

int divide(int dividend, int divisor) { 

    int denom=divisor;
    int current = 1;
    int answer=0;

    if ( denom > dividend) 
        return 0;

    if ( denom == dividend)
        return 1;

    while (denom < dividend) {
        denom = denom << 1;
        current = current << 1;
    }

    while (current!=0) {
        if ( dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current = current >> 1;
        denom = denom >> 1;
    }
    return answer;
}

For the moment, I've just implemented this for positive numbers--Simon's answer already covers the logic for dealing with negative numbers pretty well. Obviously, I'm also leaving it up to you to convert the place it uses subtraction into a call to your hand-rolled subtraction function.

In any case, this produces one bit per iteration, so it's basically \$O(b)\$ where b is the number of bits in the numbers you're working with. In the worst case, you'd be looking at a total of 62 iterations to divide two (signed) 32-bit ints.

Also note that I haven't worked very hard at testing every possibility with this code. I wouldn't be particularly surprised if it blew up for some possible values (e.g., dividing the largest possible int by 1).

Looking past the basic algorithm for the moment, I think I'd prefer to see somewhat more descriptive names that a and b. The names I've chosen aren't graven in stone, but names that at least mean something are generally extremely helpful.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.