Bitwise signed division algorithm in C

Question

Well, to be honest this is actually my homework where I have to implement an algorithm which has to be able to divide two values without taking the absolute values of them to do the division. It also has to find out the remainder.

The dividend is the one with bigger absolute value and the divider has smaller absolute value.

I have done a lot of Googling but most of the examples only cover unsigned values.

I tried to implement it by the scheme mentioned in the first reply: Implement division with bit-wise operator That didn't get me very far for some reason.

Then I found this: http://www4.wittenberg.edu/academics/mathcomp/shelburne/comp255/notes/BinaryDivision.pdf I got it working when I wrote the code below using the example in the end of the document.

This one gets it right if the first value is positive and the second isn't.

I have worked on it for at least 2 days now. Maybe somebody can say where am I going wrong.

---

Here is the code I managed to put together with the help of @Dysaster. It doesn't work when both values are either negative or positive but I managed to get 20 points out of 25 for it at the protection.

#include <stdio.h>
#include <stdlib.h>

char *bits(char Rg) {

    unsigned char bit = 0x80;
    int i;
    char *bits;
    bits = (char*) malloc(9);
    for (i=0; i < 8; i++) {
        *(bits+i) = Rg & bit ? '1' : '0';
        bit >>= 1;
    }
    *(bits+i) = '\0';
    return bits;
}

int divide(char Rg1, char Rg2) {

    char Rg3, r=0;
    int i;

    printf("Rg1 : %s (%2d)\n", bits(Rg1), Rg1);
    printf("Rg2 : %s (%2d)\n", bits(Rg2), Rg2);
    Rg3 = Rg1;
    printf("Rg3 : %s (%2d)  <- copy of Rg1\n", bits(Rg3), Rg3);
    if (Rg1 < 0) {
        r = 0xff;
    }
    printf("rem : %s (%2d)  <- remainder after sign check\n", bits(r), r);

    for (i = 0; i < 8; i++) {

        printf("\n ------------ %d. ITERATION ------------\n", i+1);


        if (Rg3 & 0x80) {
            printf(" - left shift r and Rg3, carry\n");
            Rg3 <<= 1;
            r <<= 1;
            r += 1;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        } else {
            printf(" - left shift r and Rg3\n");
            Rg3 <<= 1;
            r <<= 1;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        }

        printf(" - add in the divisor\n");
        r += Rg2;
        printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);

        if (Rg1 < 0 && Rg2 > 0 && r >= 0 || Rg1 > 0 && Rg2 < 0 && r < 0) { // real ugly, I know
            printf(" - subtract the divisor and set the lowest bit of Rg3 to 1\n");
            r -= Rg2;
            Rg3 |= 0x01;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        } else {
            printf(" - lowest bit of Rg3 stays 0\n");
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        }

    }

    // post division sign check
    if ((Rg1 < 0 && Rg2 > 0) || (Rg1 > 0 && Rg2 < 0)) {
        Rg3++;
    }

    printf("\n%s (%d) / %s (%d) = %s (%d) r %s (%d)\n\n", bits(Rg1), Rg1, bits(Rg2), Rg2, bits(Rg3), Rg3, bits(r), r);
}


int main(int argc, char *argv[]) {

    divide(-13, -4); // buggy
    divide(-29, 4);  // OK
    divide(19, -8);  // OK
    divide(17, 5);   // buggy

    return 0;
}

Answer 1

Looks like the restriction of not allowing you to take the absolute values is a big one. It is possible to modify the code you have slightly to handle the case there Rg1>0 and Rg2<0.

Instead of taking the absolute value of the negative number, you just change signs in places where Rg2 is used - and also change signs on the output. You seem to have started that way, but forgot the little bit of negating your divisor (what's left over in Rg3 after you are done). You can do that in two ways: keep the algorithm as-is, but set Rg3=(Rg3^0xff + 1) after the eight iterations. Alternatively, instead of shifting in 0 for negative, and 1 for positive, you can revert it in the main loop by shifting in 1 when r is negative, and 0 otherwise (this is the equivalent of calculating Rg3 ^ 0xff implicitly) and add 1 after the eight iterations. To see why you need the plus 1, divide 1 by -2, and see r always staying negative - causing all 1s to be shifted in Rg3. After eight iterations, you'll have 0xff (or -1), but it should have been 0. So you add 1.

By the way, there is a bug in bits function. The line char bit = 0x80 should read unsigned char bit = 0x80, because a signed char of value 0x80 becomes 0xC0 when shifted right - and that messes up your bit values.

In any case. I don't know how to handle the case of Rg1<0 regardless of the sign of Rg2. I will update the answer if I can think of anything. In the end, your division will have to choose one of the four algorithms to do the job depending on the sign of each input parameter.

---

EDIT:

I am not sure how to explain it exactly, but for the case of Rg1<0, Rg2>0, the solution is to simply change initial value of r to 0xff, and change the sign check of r down below to r >= 0. The result for -19/8 is -2*8-3, and for -29/4 is -7*4-1. If you want the remainder to be always positive, you need to subtract 1 from Rg3, and add Rg2 to r.

I chose 0xFF initial value, because r is simply the sign extension of Rg1 to 16 bits. Since r is now always negative, checking whether it becomes zero or positive after adding Rg2 is only natural.

You should be able to handle the case of Rg1<0, Rg2<0 quite easily: simply revert the signs of Rg2 operations again. It may also be possible to combine the four different routines into one that handles all four cases, but I'll leave that up to you as well. :)