Division of numbers, Algorithms for dividing binary numbers - Computer science

Division of numbers

Algorithms for dividing binary numbers

Let's consider algorithms of operation of division of the whole positive binary numbers on , where A is 2n-bit dividend; B is the i-bit divisor; . We assume that the quotient is an integer-to-bit number , with

The algorithm of division with the restitution of the remainder. The values ​​of the bits are determined by analyzing the residuals obtained after subtracting the divisor B on the first step of the algorithm from the highest digits of the dividend Dst, and at the next steps - from the highest digits of the current remainder.

For positive and bullet values ​​of the remainder, the digit of the private c is k = 1. In this case, to get the next remainder, the current balance is shifted by one bit to the left and from it the divisor B

is subtracted.

For the negative value of the remainder, the current bit of the private c is k = 0. A deadlock occurs. To exit from it, the previous remainder is restored by adding the divider B to the negative remainder. The restored residue is shifted one bit to the left and the divisor B is subtracted from it. The operations of recovery and shifting allow to increase the previous remainder twice and continue the division operation.

Example 2.30. Let's illustrate the algorithm with restoring the remainder for the case n = 3, when the dividend A = 100011 (35 | 0), the divisor B = 111 (710). To subtract the divisor B , we use the operation of algebraic addition in the supplementary code. The negative value of the divisor in the supplementary code (~ B) = 1001. To perform the division operation, we introduce additional character digits, which will be highlighted in bold. The sequence of actions in the division is presented below, in Fig. 2.17.

Algorithm for dividing binary numbers with restoring the remainder

Fig. 2.17. Algorithm for dividing binary numbers with restoring the remainder

Example 2.31. Division uses addition and shift operations.

As a result of division, a particular C = 0101 is obtained, which, in fact, is a collection of transfers that arise as a result of addition operations.

The algorithm of division without restoring the remainder. With the hardware implementation of the division of binary numbers, the addition operation is implemented in the adder, and the shifts in the register. The register has the ability to store the previous balance during the summation operation. Therefore, restoring the remainder is an optional operation. With negative the value of the current balance, it is necessary to use the previous remainder stored in the register and move it to the left one digit.

Example 2.32. The algorithm without restoring the remainder for the same values ​​of the divisor and dividend is similar to the example given in Example 2.29 (Figure 2.18).

Algorithm for dividing binary numbers without restoring a remainder

Fig. 2.18. Algorithm for dividing binary numbers without restoring the remainder

For algebraic division of binary numbers, it is necessary to perform separate actions to determine the sign and the module of the quotient. The private sign is determined using the addition operation modulo two above the signed digits, as well as multiplying binary numbers.

thematic pictures

Also We Can Offer!

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)