![]() |
![]() | #1 |
Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() 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 Last edited by DaNYer; 09.12.2003 at 19:49. |
![]() |
![]() | #5 |
Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
void load(int*, int*, int*); adder ya ispol'zoval svoi ![]() shiftat' na moi vzglyad dlya takoi malen'koi cifri effektivnee ne v cikle a topornim metodom... ostal'noe kajis' ne srabotalo. |
![]() |
![]() | #6 |
Banned Join Date: 10 2002 Location: Brooklyn, New York Age: 42
Posts: 3,760
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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 ![]() |
![]() |
Sponsored Links |
![]() |
Thread Tools | |
|
На правах рекламы: | |
![]() |
Полиграфия. Лучшая цифровая печать меню для ресторана
|