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;
}
The Bitwise right shift operator The right shift operator shifts the bits towards the right. This means it does the exact opposite of the left shift operator i.e. every time we shift a number towards the right by 1 bit it divides that number by 2.
The Bitwise Algorithms is used to perform operations at the bit-level or to manipulate bits in different ways. The bitwise operations are found to be much faster and are sometimes used to improve the efficiency of a program. For example: To check if a number is even or odd.
The Division Algorithm for Integers Examples: If a = 9 and b = 2, then q = 4 and r = 1. If a = 12 and b = 17, then q = 0 and r = 12. If a = -17 and b = 3, then q = -6 and r = 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 1
s 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. :)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With