Content deleted Content added
16*2 Tags: section blanking Mobile edit Mobile web edit |
Undid revision 793390692 by 106.203.68.128 (talk) |
||
Line 34:
# Repeat steps 2 and 3 until they have been done ''y'' times.
# Drop the least significant (rightmost) bit from ''P''. This is the product of '''m''' and '''r'''.
==Example==
Find 3 × (−4), with '''m''' = 3 and '''r''' = −4, and ''x'' = 4 and ''y'' = 4:
* m = 0011, -m = 1101, r = 1100
* A = 0011 0000 0
* S = 1101 0000 0
* P = 0000 1100 0
* Perform the loop four times:
*# P = 0000 110'''0 0'''. The last two bits are 00.
*#* P = 0000 0110 0. Arithmetic right shift.
*# P = 0000 011'''0 0'''. The last two bits are 00.
*#* P = 0000 0011 0. Arithmetic right shift.
*# P = 0000 001'''1 0'''. The last two bits are 10.
*#* P = 1101 0011 0. P = P + S.
*#* P = 1110 1001 1. Arithmetic right shift.
*# P = 1110 100'''1 1'''. The last two bits are 11.
*#* P = 1111 0100 1. Arithmetic right shift.
* The product is 1111 0100, which is −12.
The above-mentioned technique is inadequate when the multiplicand is the [[two's complement#The most negative number|most negative number]] that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). One possible correction to this problem is to add one more bit to the left of A, S and P. This then follows the implementation described above, with modifications in determining the bits of A and S; e.g., the value of '''m''', originally assigned to the first ''x'' bits of A, will be assigned to the first ''x''+1 bits of A. Below, the improved technique is demonstrated by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
* A = 1 1000 0000 0
* S = 0 1000 0000 0
* P = 0 0000 0010 0
* Perform the loop four times:
*# P = 0 0000 001'''0 0'''. The last two bits are 00.
*#* P = 0 0000 0001 0. Right shift.
*# P = 0 0000 000'''1 0'''. The last two bits are 10.
*#* P = 0 1000 0001 0. P = P + S.
*#* P = 0 0100 0000 1. Right shift.
*# P = 0 0100 000'''0 1'''. The last two bits are 01.
*#* P = 1 1100 0000 1. P = P + A.
*#* P = 1 1110 0000 0. Right shift.
*# P = 1 1110 000'''0 0'''. The last two bits are 00.
*#* P = 1 1111 0000 0. Right shift.
* The product is 11110000 (after discarding the first and the last bit) which is −16.
==How it works==
| |||