Implementing unsigned integer recovery division algorithm in C++

Discusses dividing unsigned integers using division algorithms. Some division algorithms are implemented on paper, others are implemented on digital circuits. There are two division algorithms: slow division algorithm and fast division algorithm. Slow division algorithms include recovery algorithms, non-execution recovery algorithms, SRT and non-recovery algorithms.

In this tutorial, we will discuss the recovery algorithm assuming 0 Solution method

Here, we will use register Q to store the quotient, register A to store the remainder, and M to store the divisor. The initial value of A remains at 0, and its value is restored, which is why the method resumes division.

• Initialize register with value,

  • Initialize register with value, p>

    • Q = Dividend,

    • A = 0,

    • M = divisor,

    • N = number of dividend digits.

  • #Shifting AQ left means treating registers A and Q as one unit.

  • A is subtracted from M and stored in A.

  • Check the most significant bit of A:

    • If it is 0, set the least significant bit to 1.

    • Otherwise, set the least significant bit to 0.

  • #Restore the value of A and decrement the value of counter N.

  • If N = 0, break the loop; otherwise, go to step 2.

  • The quotient is stored in register Q.

  Flow chart

  

  Example

  C code for the above method

  #include <iostream>
  using namespace std;
  int main(){
     // initializing all the variables with Dividend = 9, Divisor = 2.
     int Q = 8,q=1,M=3;
     short N = 4;
     int A = Q;
     M <<= N;
     // loop for division by bit operation.
     for(int i=N-1; i>=0; i--) {
        A = (A << 1)- M;
        // checking MSB of A.
        if(A < 0) {
           q &= ~(1 << i);  // set i-th bit to 0
           A = A + M;
        } else {
           q |= 1 << i;     // set i-th bit to 1
        }
     }
     cout << "Quotient: "<< q;
     return 0;
  }

  Output

  Quotient: 2

  Conclusion

  In this tutorial, we discussed the recovery division algorithm for unsigned integers. We discussed a simple way to solve this problem with the help of flowcharts and applying bit operations. We also discussed a C program to solve this problem and we can implement it using programming languages ​​like C, Java, Python etc. We hope you found this tutorial helpful.

The above is the detailed content of Implementing unsigned integer recovery division algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!