Binary Division:

DaNYer · Dec 9, 2003, 17:56

Binary Division Restoring Algorithm

// Division is the process of repeated subtraction.
// Binary division algorithm works from the high order digits
// to the low order digits and generates a quotient (division result)
// with each step. The division algorithm is divided into two steps:
//
// 1. Shift the upper bits of the dividend (the number we are dividing into)
// into the remainder.
//
// 2.Subtract the divisor from the value in the remainder. The high order bit
// of the result become a bit of the quotient (division result).

Code:

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

void load(int*, int*, int*);
void display(int*, int*, int*);
void compute(int*, int*, int*);
void adder(int*, int*);
void negate(int*);

void main()
{
	int i;
	int DIVISOR [5];
	int REMAINDER [5];
	int DIV_QUOT [4];	// DIVIDEND - QUOTIENT

//initialising registers with data
	load(DIVISOR, REMAINDER, DIV_QUOT);	
		
	//Decorations.
	printf("  DIVISOR |\t     REMAINDER\t     DIVIDEND/QUOTIENT");
		printf("\n  --------|----------------");
			printf("---------------------------\n");

	display(DIVISOR, REMAINDER, DIV_QUOT);	//general display
		printf("\n  --------|----------------");
			printf("---------------------------\n");
	//Done with decorations.

	//computation
	for (i=0; i<4; i++)
	{
		compute(DIVISOR, REMAINDER, DIV_QUOT);	//compute 1st bit
		printf("\n  --------|----------------");
			printf("---------------------------\n");
	}
}





///////////////////////////////////////////////////////
// Computation
void compute(int DIVISOR[], int REMAINDER[], int DIV_QUOT[])
{
	int DIVISOR_Copy [5];
	bool neg;

	REMAINDER[1] = REMAINDER[2];
	REMAINDER[2] = REMAINDER[3];
	REMAINDER[3] = REMAINDER[4];
	REMAINDER[4] = DIV_QUOT[0];
	DIV_QUOT[0] = DIV_QUOT[1];
	DIV_QUOT[1] = DIV_QUOT[2];
	DIV_QUOT[2] = DIV_QUOT[3];
	DIV_QUOT[3] = 888;			//flag to put "?" sign

	display(DIVISOR, REMAINDER, DIV_QUOT);	//display
	printf("  |  <--- Shifting left...\n");


	// NOW LETS DETERMINE THE STATUS OF DIV_QUOT[3]
	// TO DO SO.... SUBSTRACT. (REMAINDER - DIVISOR) AND SEE
	// IF NEGATIVE, IT IS 0; AND RESTORE REMAINDER
	// IF POSITIVE IT IS 1 AND DO NOT RESTORE REMAINDER.

	///////////////////////// 
	// SUBSTRACT operation HERE. 
	// REMAINDER - DIVISOR  = ?
	//
	// first lets create and negate DIVISOR_Copy 
	// an image of DIVISOR

	DIVISOR_Copy[0] = DIVISOR[0];
	DIVISOR_Copy[1] = DIVISOR[1];
	DIVISOR_Copy[2] = DIVISOR[2];
	DIVISOR_Copy[3] = DIVISOR[3];
	DIVISOR_Copy[4] = DIVISOR[4];
		
	negate(DIVISOR_Copy);

	adder(REMAINDER, DIVISOR_Copy);		// Addition (actually substraction)

	if (REMAINDER[0] == 1)			// Checking control bit. 
							// (overflow or neg)
		neg = 1;  /// Negative 
	else 
		neg = 0;  /// Positive

	display(DIVISOR, REMAINDER, DIV_QUOT);	//display

	if (neg)	// if the number was negative, 
			// restore REMAINDER and assign 0 to D[3]
	{
		adder(REMAINDER, DIVISOR);	//Restoration
		DIV_QUOT[3] = 0;
		printf("  |  NEGATIVE. ? = 0\n");
	}
	else
	{
		DIV_QUOT[3] = 1;
		printf("  |  POSITIVE. ? = 1\n");
	}
	display(DIVISOR, REMAINDER, DIV_QUOT);	//display
}


///////////////////////////////////////////////////////
// Two's compliment.
void negate(int A[])
{
	int i;
	int ONE[5];
	ONE[0] = 0;
	ONE[1] = 0;
	ONE[2] = 0;
	ONE[3] = 0;
	ONE[4] = 1;
	
	for (i=0; i<=4; i++)
	{
		if(A[i] == 1) 
			A[i] = 0;
		else 
			A[i] = 1;
	}
	//ADD 1
	adder(A, ONE);	
}


///////////////////////////////////////////////////////
// 4 bit adder.
void adder(int A[], int B[])
{
	int next, i, carry=0;
	
	for (i=4; i>=0; i--)	// 4, because we have sign control bit
	{
		next = 1;
		if (A[i]==0 && B[i]==0)		//00 case
		{
			A[i]= carry;
			carry = 0;
			next = 0;
		} // good.
		
		if (next)
		if (A[i]==0 && B[i]==1)		//01 case	- transfer
		{
			if (carry == 0)
				A[i] =1;
			else
				A[i]=0;
			next = 0;
		}
			
		if(next)
		if (A[i]==1 && B[i]==0)		//10 case	- transfer
		{
			if (carry == 0)
				A[i] =1;
			else
				A[i]=0;
			next = 0;
		}	

		if(next)
		if (A[i]==1 && B[i]==1)		//11 case - generate
		{	
			if (carry == 0)
			{
				A[i] =0;
				carry = 1;
			}
			else
				A[i]=1;
		next = 0;
		}
	}
}



///////////////////////////////////////////////////////
//displaying {OK}
void display(int A[], int B[], int C[])
{
	int i;
	printf(" ");
	for(i=1; i<=4; i++) 
		printf(" %d", A[i]);
	printf(" |          ");

	for(i=1; i<=4; i++) 
		printf(" %d", B[i]);
	printf("            ");

	for(i=0; i<=3; i++) 
		if ((C[i] == 0) || (C[i] == 1))
			printf(" %d", C[i]);
		else 
			printf(" ?");
}

///////////////////////////////////////////////////////
//function to load registers with data.  {OK}
void load(int A[], int B[], int C[])
{

	A[0] = 0;
	A[1] = 1;  //DIVISOR
	A[2] = 0;
	A[3] = 0;
	A[4] = 0;
	
	B[0] = 0;  // !!!!!!SIGN CONTROL BIT!!!!!!
	B[1] = 0;  // ALL ZEROS
	B[2] = 0;  // ALL ZEROS
	B[3] = 0;  // ALL ZEROS
	B[4] = 0;  // ALL ZEROS


	C[0] = 1;  //DIVIDEND / QUOT
	C[1] = 0;
	C[2] = 0;
	C[3] = 0;
}







Outputs:



1) 8 / 8 = 1 (Remainder = 0)

  DIVISOR |          REMAINDER       DIVIDEND/QUOTIENT
  --------|-------------------------------------------
  1 0 0 0 |           0 0 0 0             1 0 0 0
  --------|-------------------------------------------
  1 0 0 0 |           0 0 0 1             0 0 0 ?  |  <--- Shifting left...
  1 0 0 0 |           1 0 0 1             0 0 0 ?  |  NEGATIVE. ? = 0
  1 0 0 0 |           0 0 0 1             0 0 0 0
  --------|-------------------------------------------
  1 0 0 0 |           0 0 1 0             0 0 0 ?  |  <--- Shifting left...
  1 0 0 0 |           1 0 1 0             0 0 0 ?  |  NEGATIVE. ? = 0
  1 0 0 0 |           0 0 1 0             0 0 0 0
  --------|-------------------------------------------
  1 0 0 0 |           0 1 0 0             0 0 0 ?  |  <--- Shifting left...
  1 0 0 0 |           1 1 0 0             0 0 0 ?  |  NEGATIVE. ? = 0
  1 0 0 0 |           0 1 0 0             0 0 0 0
  --------|-------------------------------------------
  1 0 0 0 |           1 0 0 0             0 0 0 ?  |  <--- Shifting left...
  1 0 0 0 |           0 0 0 0             0 0 0 ?  |  POSITIVE. ? = 1
  1 0 0 0 |           0 0 0 0             0 0 0 1
  --------|-------------------------------------------
Press any key to continue



2) 8 / 2 = 4 (Remainder = 0)

  DIVISOR |          REMAINDER       DIVIDEND/QUOTIENT
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 0             1 0 0 0
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 1             0 0 0 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 1             0 0 0 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 1             0 0 0 0
  --------|-------------------------------------------
  0 0 1 0 |           0 0 1 0             0 0 0 ?  |  <--- Shifting left...
  0 0 1 0 |           0 0 0 0             0 0 0 ?  |  POSITIVE. ? = 1
  0 0 1 0 |           0 0 0 0             0 0 0 1
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 0             0 0 1 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 0             0 0 1 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 0             0 0 1 0
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 0             0 1 0 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 0             0 1 0 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 0             0 1 0 0
  --------|-------------------------------------------
Press any key to continue













3) 9 / 2 = 4 (Remainder = 1)

  DIVISOR |          REMAINDER       DIVIDEND/QUOTIENT
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 0             1 0 0 1
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 1             0 0 1 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 1             0 0 1 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 1             0 0 1 0
  --------|-------------------------------------------
  0 0 1 0 |           0 0 1 0             0 1 0 ?  |  <--- Shifting left...
  0 0 1 0 |           0 0 0 0             0 1 0 ?  |  POSITIVE. ? = 1
  0 0 1 0 |           0 0 0 0             0 1 0 1
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 0             1 0 1 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 0             1 0 1 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 0             1 0 1 0
  --------|-------------------------------------------
  0 0 1 0 |           0 0 0 1             0 1 0 ?  |  <--- Shifting left...
  0 0 1 0 |           1 1 1 1             0 1 0 ?  |  NEGATIVE. ? = 0
  0 0 1 0 |           0 0 0 1             0 1 0 0
  --------|-------------------------------------------
Press any key to continue



4) 8 / 3 = 2 (Remainder = 2)

  DIVISOR |          REMAINDER       DIVIDEND/QUOTIENT
  --------|-------------------------------------------
  0 0 1 1 |           0 0 0 0             1 0 0 0
  --------|-------------------------------------------
  0 0 1 1 |           0 0 0 1             0 0 0 ?  |  <--- Shifting left...
  0 0 1 1 |           1 1 1 0             0 0 0 ?  |  NEGATIVE. ? = 0
  0 0 1 1 |           0 0 0 1             0 0 0 0
  --------|-------------------------------------------
  0 0 1 1 |           0 0 1 0             0 0 0 ?  |  <--- Shifting left...
  0 0 1 1 |           1 1 1 1             0 0 0 ?  |  NEGATIVE. ? = 0
  0 0 1 1 |           0 0 1 0             0 0 0 0
  --------|-------------------------------------------
  0 0 1 1 |           0 1 0 0             0 0 0 ?  |  <--- Shifting left...
  0 0 1 1 |           0 0 0 1             0 0 0 ?  |  POSITIVE. ? = 1
  0 0 1 1 |           0 0 0 1             0 0 0 1
  --------|-------------------------------------------
  0 0 1 1 |           0 0 1 0             0 0 1 ?  |  <--- Shifting left...
  0 0 1 1 |           1 1 1 1             0 0 1 ?  |  NEGATIVE. ? = 0
  0 0 1 1 |           0 0 1 0             0 0 1 0
  --------|-------------------------------------------
Press any key to continue

greka · Dec 10, 2003, 07:55

mojno neskromnyj vopros ?
Ty xot' odin sovet ispol'zoval, ktorye tebe v tvoix topiikax davali ?

DaNYer · Dec 10, 2003, 14:01

Quote:

Originally posted by Greco El
mojno neskromnyj vopros ?

mojno

Quote:

Ty xot' odin sovet ispol'zoval, ktorye tebe v tvoix topiikax davali ?

da

greka · Dec 10, 2003, 15:16

Quote:

Originally posted by DaNYer
mojno

da

a mojno posmotret', gde imenno v privedennom kode ?

DaNYer · Dec 10, 2003, 15:39

void load(int*, int*, int*);

adder ya ispol'zoval svoi

sorry.

shiftat' na moi vzglyad dlya takoi malen'koi cifri effektivnee ne v cikle a topornim metodom...

ostal'noe kajis' ne srabotalo.

DaNYer · Dec 10, 2003, 15:42

no ved' rabotaet je! i neploxo rabotaet skaju ya vam...

kstati Garik, ya podumivaiu web site sdelat' posvyashennii iskluchitel'no algoritmam... tam mojno budet naiti algoritmi, skachat' rabotayushie progi i t.p. takaya naivnaya zateya, ya uveren chto takie web sites uge est' i ix daje bol'she chem u menya volos na golove.. no zato svoi budet

rodnoi tak skazat'. kak posmotrish na etu zateyu? podderjish?

Dec 10, 2003, 07:55	#2
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	mojno neskromnyj vopros ? Ty xot' odin sovet ispol'zoval, ktorye tebe v tvoix topiikax davali ? __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Dec 10, 2003, 15:39	#5
DaNYer Banned Join Date: Oct 2002 Location: Brooklyn, New York Posts: 3,760 Rep Power: 0 Reputation: 10	void load(int, int, int*); adder ya ispol'zoval svoi sorry. shiftat' na moi vzglyad dlya takoi malen'koi cifri effektivnee ne v cikle a topornim metodom... ostal'noe kajis' ne srabotalo.

Dec 10, 2003, 15:42	#6
DaNYer Banned Join Date: Oct 2002 Location: Brooklyn, New York Posts: 3,760 Rep Power: 0 Reputation: 10	no ved' rabotaet je! i neploxo rabotaet skaju ya vam... kstati Garik, ya podumivaiu web site sdelat' posvyashennii iskluchitel'no algoritmam... tam mojno budet naiti algoritmi, skachat' rabotayushie progi i t.p. takaya naivnaya zateya, ya uveren chto takie web sites uge est' i ix daje bol'she chem u menya volos na golove.. no zato svoi budet rodnoi tak skazat'. kak posmotrish na etu zateyu? podderjish?