Buta algoritms
Šis raksts ir jāuzlabo, lai ievērotu Vikipēdijā pieņemto stilu un/vai formatēšanu. Iemesls: Noformējums, kategorijas, stils Lūdzu, palīdzi uzlabot šo rakstu. Ja ir kādi ieteikumi, vari tos pievienot diskusijā. Vairāk lasi lietošanas pamācībā. |
Buta algoritms ir reizināšanas algoritms, kas sareizina divus zīmes (+/-) binārus skaitļus, izmantojot binārā skaitļa papildkodu. To 1951. gadā izgudroja Endrū Donalds Buts.
Procedūra
labot šo sadaļuButa algoritms paredz atkārtoti pieskaitīt vienu no sākotnējām vērtībām (A un S) rezultātam P un tad izpildīt aritmētisko nobīdi pa labi skaitlim P.
m - reizināmais, r — reizinātājs.
x un y norāda bitu skaitu m un r.
- Nosaka A un S vērtības un P sākuma vērtību. A, S, P skaitļu garumiem jābūt vienādiem ar (x + y + 1).
- A: Nozīmīgākos bitus (pa labi) aizpilda ar m vērtību, atlikušos bitus (y + 1) ar nullēm.
- S: Nozīmīgākos bitus (pa labi) aizpilda ar (-m) papildkodu, atlikušos bitus (y + 1) ar nullēm.
- P: Nozīmīgākos x bitus aizpilda ar nullēm, pa labi pievieno r vērtību, pēdējam bitam (pa labi) pieškir vērtību 0.
- Nosaka P pēdējos divus nozīmīgākos (pa labi) bitus.
- Ja tie ir 01, tad P + A. Pārpilde tiek ignorēta.
- Ja tie ir 10, tad P + S. Pārpilde tiek ignorēta.
- Ja tie ir 00, neko nedara. Pāriet pie nākamā soļa.
- Ja tie ir 11, neko nedara. Pāriet pie nākamā soļa.
- P skaitļa aritmētiskā nobīde pa labi par vienu bitu. P satur jauno vērtību.
- 2. un 3. punktu atkārto līdz izpildīti y reizes.
- Atmet P pēdējo nozīmīgo bitu (pa labi), P satur m un r reizinājuma vērtību.
Piemērs
labot šo sadaļu3 x (-4), kur m = 3, r = -4, x = 4 un y = 4:
- A = 0011 0000 0
- B = 1101 0000 0
- P = 0000 1100 0
- Izpilda ciklu 4 reizes:
- P = 0000 1100 0. Pēdējie divi biti 00.
- P = 0000 0110 0. Aritmētiskā nobīde pa labi.
- P = 0000 0110 0. Pēdējie divi biti 00.
- P = 0000 0011 0. Aritmētiskā nobīde pa labi.
- P = 0000 0011 0. Pēdējie divi biti 10.
- P = 1101 0011 0. P = P + S
- P = 1110 1001 1. Aritmētiskā nobīde pa labi.
- P = 1110 1001 1. Pēdējie divi biti 11.
- P = 1111 0100 1. Aritmētiskā nobīde pa labi.
- P = 0000 1100 0. Pēdējie divi biti 00.
- P = 1111 0100, decimālā sistēmā -12