Алгоритм Бута — це алгоритм множення, який дозволяє нам множити два двійкові цілі числа зі знаком у доповненні до 2 відповідно. Він також використовується для прискорення виконання процесу множення. Це також дуже ефективно. Він працює з рядковими бітами 0 у множнику, який не потребує додаткових бітів, лише зміщує крайні праві біти рядка та рядок 1 у множнику бітової ваги 2kдо ваги 2мщо можна розглядати як 2k+ 1- 2м .
Нижче наведено графічне представлення алгоритму Бута:
На наведеній вище блок-схемі спочатку AC і Qn + 1 біти встановлені на 0, і SC це лічильник послідовності, який представляє загальний набір бітів n, яка дорівнює кількості бітів у множнику. Є BR які представляють кратні біти, і QR представляє біти множника . Після цього ми зустріли два біти множника як Qпі Qn + 1, де Qn представляє останній біт QR, а Qn + 1представляє біт Qn, збільшений на 1. Припустимо, що два біти множника дорівнюють 10; це означає, що ми повинні відняти множник від часткового добутку в акумуляторі AC, а потім виконати операцію арифметичного зсуву (ashr). Якщо два множники дорівнюють 01, це означає, що нам потрібно виконати додавання множеного до неповного добутку в акумуляторі AC, а потім виконати операцію арифметичного зсуву ( Ашр ), в тому числі Qn + 1 . Операція арифметичного зсуву використовується в алгоритмі Бута для зсуву бітів AC і QR вправо на одиницю, і знаковий біт в AC залишається незмінним. А лічильник послідовності безперервно зменшується, доки обчислювальний цикл не повториться, дорівнюючи числу бітів (n).
Робота над алгоритмом Бута
- Установіть двійкові біти множника та множника як M і Q відповідно.
- Спочатку ми встановлюємо AC і Qn + 1реєструє значення 0.
- SC представляє кількість бітів множника (Q), і це лічильник послідовності, який безперервно зменшується до тих пір, поки не дорівнюватиме числу бітів (n) або досягне 0.
- Qn представляє останній біт Q і Qn+1показує біт Qn, збільшений на 1.
- На кожному циклі алгоритму будки Qпі Qn + 1біти перевірятимуться за такими параметрами:
- Коли два біти Qпі Qn + 100 або 11, ми просто виконуємо операцію арифметичного зсуву вправо (ashr) до часткового добутку AC. І біти Qn і Qn + 1збільшується на 1 біт.
- Якщо біти Qпі Qn + 1відображається як 01, біти множеного (M) будуть додані до AC (регістру накопичувача). Після цього виконуємо операцію зсуву вправо до бітів AC і QR на 1.
- Якщо біти Qпі Qn + 1показує до 10, біти множеного (M) будуть віднімані з AC (регістру накопичувача). Після цього виконуємо операцію зсуву вправо до бітів AC і QR на 1.
- Операція безперервно працює, поки ми не досягнемо n - 1 біта в алгоритмі кабіни.
- Результати двійкових бітів множення будуть зберігатися в регістрах AC і QR.
В алгоритмі Бута використовуються два методи:
що таке const в java
1. RSC (Right Shift Circular)
Він зсуває крайній правий біт двійкового числа, а потім додає його до початку двійкових бітів.
2. RSA (арифметика правого зсуву)
Він додає два двійкові біти, а потім зсуває результат праворуч на 1-бітну позицію.
рядок для int у java
приклад : 0100 + 0110 => 1010, після додавання двійкового числа зрушити кожен біт на 1 праворуч і поставити перший біт результату на початок нового біта.
Приклад: помножте два числа 7 і 3 за допомогою алгоритму множення Бута.
років . Тут ми маємо два числа, 7 і 3. Перш за все, нам потрібно перетворити 7 і 3 у двійкові числа, наприклад 7 = (0111) і 3 = (0011). Тепер встановіть 7 (у двійковому 0111) як множене (M) і 3 (у двійковому 0011) як множник (Q). І SC (підрахунок послідовності) представляє кількість бітів, і тут ми маємо 4 біти, тому встановіть SC = 4. Крім того, це показує кількість ітераційних циклів алгоритмів кабіни, а потім цикли виконуються SC = SC - 1 раз.
| Qп | Qn + 1 | M = (0111) M' + 1 = (1001) & Операція | AC | Q | Qn + 1 | SC |
|---|---|---|---|---|---|---|
| 1 | 0 | Початковий | 0000 | 0011 | 0 | 4 |
| Відняти (М' + 1) | 1001 | |||||
| 1001 | ||||||
| Виконання арифметичних операцій зсуву вправо (ashr) | 1100 | 1001 | 1 | 3 | ||
| 1 | 1 | Виконання арифметичних операцій зсуву вправо (ashr) | 1110 | 0100 | 1 | 2 |
| 0 | 1 | Додавання (A + M) | 0111 | |||
| 0101 | 0100 | |||||
| Виконайте арифметичну операцію зсуву вправо | 0010 | 1010 | 0 | 1 | ||
| 0 | 0 | Виконайте арифметичну операцію зсуву вправо | 0001 | 0101 | 0 | 0 |
Числовим прикладом алгоритму множення Бута є 7 x 3 = 21, а двійкове представлення 21 дорівнює 10101. Тут ми отримуємо результант у двійковій системі 00010101. Тепер ми перетворюємо його в десяткове число, як (000010101)10= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
різниця між масивом і списком масивів
Приклад: помножте два числа 23 і -9 за допомогою алгоритму множення Бута.
Тут M = 23 = (010111) і Q = -9 = (110111)
| QпQn + 1 | M = 0 1 0 1 1 1 M' + 1 = 1 0 1 0 0 1 | AC | Q | Qn + 1SC |
|---|---|---|---|---|
| Спочатку | 000000 | 110111 | 0 6 | |
| 1 0 | Відніміть М | 101001 | ||
| 101001 | ||||
| Виконайте арифметичну операцію зсуву вправо | 110100 | 111011 | п'ятнадцять | |
| одинадцять | Виконайте арифметичну операцію зсуву вправо | 111010 | 011101 | 1 4 |
| одинадцять | Виконайте арифметичну операцію зсуву вправо | 111101 | 001110 | 1 3 |
| 0 1 | Додавання (A + M) | 010111 | ||
| 010100 | ||||
| Виконайте арифметичну операцію зсуву вправо | 001010 | 000111 | 0 2 | |
| 1 0 | Відніміть М | 101001 | ||
| 110011 | ||||
| Виконайте арифметичну операцію зсуву вправо | 111001 | 100011 | одинадцять | |
| одинадцять | Виконайте арифметичну операцію зсуву вправо | 111100 | 110001 | 1 0 |
Qn + 1 = 1, це означає, що результат негативний.
Отже, 23 * -9 = доповнення 2 до 111100110001 => (00001100111)