Алгоритм Бута — це алгоритм множення, який дозволяє нам множити два двійкові цілі числа зі знаком у доповненні до 2 відповідно. Він також використовується для прискорення виконання процесу множення. Це також дуже ефективно. Він працює з рядковими бітами 0 у множнику, який не потребує додаткових бітів, лише зміщує крайні праві біти рядка та рядок 1 у множнику бітової ваги 2^kдо ваги 2^мщо можна розглядати як 2^{k+ 1}- 2^м .

Нижче наведено графічне представлення алгоритму Бута:

На наведеній вище блок-схемі спочатку AC і Q_{n + 1} біти встановлені на 0, і SC це лічильник послідовності, який представляє загальний набір бітів n, яка дорівнює кількості бітів у множнику. Є BR які представляють кратні біти, і QR представляє біти множника . Після цього ми зустріли два біти множника як Q_пі Q_{n + 1}, де Qn представляє останній біт QR, а Q_{n + 1}представляє біт Qn, збільшений на 1. Припустимо, що два біти множника дорівнюють 10; це означає, що ми повинні відняти множник від часткового добутку в акумуляторі AC, а потім виконати операцію арифметичного зсуву (ashr). Якщо два множники дорівнюють 01, це означає, що нам потрібно виконати додавання множеного до неповного добутку в акумуляторі AC, а потім виконати операцію арифметичного зсуву ( Ашр ), в тому числі Q_{n + 1} . Операція арифметичного зсуву використовується в алгоритмі Бута для зсуву бітів AC і QR вправо на одиницю, і знаковий біт в AC залишається незмінним. А лічильник послідовності безперервно зменшується, доки обчислювальний цикл не повториться, дорівнюючи числу бітів (n).

Робота над алгоритмом Бута

1. Установіть двійкові біти множника та множника як M і Q відповідно.
2. Спочатку ми встановлюємо AC і Q_{n + 1}реєструє значення 0.
3. SC представляє кількість бітів множника (Q), і це лічильник послідовності, який безперервно зменшується до тих пір, поки не дорівнюватиме числу бітів (n) або досягне 0.
4. Qn представляє останній біт Q і Q_n+1показує біт Qn, збільшений на 1.
5. На кожному циклі алгоритму будки Q_пі Q_{n + 1}біти перевірятимуться за такими параметрами:
   1. Коли два біти Q_пі Q_{n + 1}00 або 11, ми просто виконуємо операцію арифметичного зсуву вправо (ashr) до часткового добутку AC. І біти Qn і Q_{n + 1}збільшується на 1 біт.
   2. Якщо біти Q_пі Q_{n + 1}відображається як 01, біти множеного (M) будуть додані до AC (регістру накопичувача). Після цього виконуємо операцію зсуву вправо до бітів AC і QR на 1.
   3. Якщо біти Q_пі Q_{n + 1}показує до 10, біти множеного (M) будуть віднімані з AC (регістру накопичувача). Після цього виконуємо операцію зсуву вправо до бітів AC і QR на 1.
6. Операція безперервно працює, поки ми не досягнемо n - 1 біта в алгоритмі кабіни.
7. Результати двійкових бітів множення будуть зберігатися в регістрах 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 раз.

Числовим прикладом алгоритму множення Бута є 7 x 3 = 21, а двійкове представлення 21 дорівнює 10101. Тут ми отримуємо результант у двійковій системі 00010101. Тепер ми перетворюємо його в десяткове число, як (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

різниця між масивом і списком масивів

Приклад: помножте два числа 23 і -9 за допомогою алгоритму множення Бута.

Тут M = 23 = (010111) і Q = -9 = (110111)

Q_{n + 1} = 1, це означає, що результат негативний.

Отже, 23 * -9 = доповнення 2 до 111100110001 => (00001100111)