Bitwise signed division algorithm in C

Question

Well, to be honest, this is actually my homework, where I have to implement an algorithm that should be able to separate the two values ​​without accepting their absolute values ​​for division. He must also find the rest.

A dividend is a unit with a large absolute value, and a separator has a lower absolute value.

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

I tried to implement it according to the scheme mentioned in the first answer: Introduce separation with a bitwise operator. For some reason, this did not really hurt me.

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

This is correct if the first value is positive and the second is not.

I have been working on this for at least 2 days. Maybe someone can tell where I am going wrong.

---

Here is the code I managed to build using @Dysaster. It does not work when both values ​​are negative or positive, but I managed to get 20 points out of 25 for this while protecting.

#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

It seems like the restriction of not allowing you to accept absolute values ​​is big. You can change the code that you have to process the register there Rg1> 0 and Rg2 <0.

Instead of accepting the absolute value of a negative number, you simply change the signs in places where Rg2 is used, and also change the signs at the output. It seems you started like that, but you forgot to deny your divisor a bit (what remains in Rg3 after you are done). You can do this in two ways: save the algorithm as is, but set Rg3=(Rg3^0xff + 1) after eight iterations. Alternatively, instead of shifting to 0 for negative and 1 for positive, you can return it to the main loop by shifting to 1 when r is negative and 0 otherwise (this is equivalent to calculating Rg3 ^ 0xff implicitly) and add 1 after eight iterations . To find out why you need plus 1, divide 1 by -2 and you will see that r always remains negative, which leads to a shift of all 1 in Rg3 . After eight iterations you will have 0xff (or -1), but that should have been 0. So, you add 1.

By the way, there is an error in bits . The string char bit = 0x80 should read unsigned char bit = 0x80 , since the signed char of the value 0x80 becomes 0xC0 when shifted to the right - and this will ruin your bit values.

Anyway. I do not know how to handle the case of Rg1<0 , regardless of the sign of Rg2 . I will update the answer if I can come up with something. In the end, your unit will have to choose one of four algorithms for the task, depending on the sign of each input parameter.

---

EDIT:

I'm not sure how to explain this, but for the case of Rg1<0 , Rg2>0 solution is to simply change the initial value of r to 0xff and change the verification of the sign of r 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 always be positive, you need to subtract 1 from Rg3 and add Rg2 to r.

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

You can easily deal with the situation Rg1<0 , Rg2<0 : just return the signs of the operations Rg2 again. It is also possible to combine four different procedures into one, which handles all four cases, but I will leave it to you. :)