CODEWITHSUNDEEP
javaalgorithm
Dumbledore
Dumbledore

Reputation: 460

Restoring Division Algorithm Implementation

I'm trying to implement Restoring Division algorithm and things are going terribly wrong. Here is my code:

public static void main(String[] args){

    int num = 10;
    long den = 2;
    long p = num;
    int n = 32;
    den = den << n;
    StringBuilder s = new StringBuilder("");
    long q = 0;
    for(int i = n; n > 0; n--){

        p = (2 * p) - den;
        if(s.length() > 0){
            s.delete(0, s.length() - 1);                
        }
        s.append(Long.toString(q,2));

        if(p >= 0){
            s.setCharAt(i, '1');
        }else{  
            s.setCharAt(i, '0');
        }

        q = Integer.parseInt(s.toString(), 2);
    }
    System.out.println(q);
}

I'm getting java.lang.StringIndexOutOfBoundsException: String index out of range: 32 exception. It's cause I'm trying to set a character(or a bit techincally) at a position that does not exist.

How do I implement this correctly? Can I get binary string with leading zeros?

Upvotes: 2

Views: 1923

Answers (1)

John Bollinger
John Bollinger

Reputation: 180048

It's very odd that you would involve any Strings in such a process. You are working with binary arithmetic, so use integer data types and operators, especially bitwise operators (&, |, ^, <<, >>, >>>). Every integer data type implements a "binary string with leading zeros". Especially so for this case, given the constraint of the restoring division algorithm that the inputs both be positive.

I'd probably write the central part more like this:

q = 0;
for(int i = 32; i > 0; i -= 1){
    q <<= 1;
    p = (2 * p) - den;

    if(p >= 0){
        q += 1;
    } else {
        // implicit: q += 0
        p += den;
    }
}

Note that it is bit 0 that is manipulated at every iteration. The previous partial result (0 at the first iteration) is left-shifted by one to make room, and so that after all 32 iterations, each bit is in the correct position.

Upvotes: 2

Related Questions