Что такое алгоритм Бута? Можете ли вы объяснить его на примере?

Алгоритм Бута используется для умножения двух двоичных чисел путем уменьшения числа на 1. Он равномерно обрабатывает как положительные, так и отрицательные числа.

Алгоритм умножения Бута Процедура Алгоритм Бута включает многократное добавление одного из двух заранее определенных значений A и S к произведению P, а затем выполнение арифметического сдвига вправо на P. Пусть m и r будут множителем и множителем соответственно; и пусть x и y представляют количество бит в m и r. 1. Определите значения A и S и начальное значение P. Все эти числа должны иметь длину, равную (x + y + 1). 1. A: Заполните самые старшие (крайние левые) биты значением m. Заполните оставшиеся (y + 1) биты нулями. 2. S: заполнить старшие значащие биты значением (-m) в нотации с дополнением до двух. Заполните оставшиеся (y + 1) биты нулями. 3. P: Заполните самые старшие биты x нулями. Справа от него добавьте значение r.Заполните наименьший значащий (крайний правый) бит нулем. 2. Определите два наименее значимых (крайних правых) бита P. 1. Если они равны 01, найдите значение P + A. Игнорируйте любое переполнение. 2. Если они равны 10, найдите значение P + S. Игнорируйте любое переполнение. 3. Если они равны 00, ничего не делайте. Используйте P непосредственно на следующем шаге. 4. Если им 11, ничего не делайте. Используйте P непосредственно на следующем шаге. 3. Арифметически сдвиньте значение, полученное на 2-м шаге, на одну позицию вправо. Пусть теперь P равно этому новому значению. 4. Повторите шаги 2 и 3, пока они не будут выполнены y раз. 5. Удалите младший значащий (крайний правый) бит из P. Это произведение m и r. Пример Найти 3 × −4, с m = 3 и r = −4, а также x = 4 и y = 4: • A = 0011 0000 0 • S = 1101 0000 0 • P = 0000 1100 0 • Выполнить цикл четыре раза : 1. P = 0000 1100 0. Последние два бита - 00. P = 0000 0110 0. Арифметический сдвиг вправо. 2. P = 0000 0110 0. Последние два бита - 00.  P = 0000 0011 0. Арифметический сдвиг вправо. 3. P = 0000 0011 0. Последние два бита равны 10.  P = 1101 0011 0. P = P + S.  P = 1110 1001 1. Арифметический сдвиг вправо. 4. P = 1110 1001 1. Последние два бита - 11.  P = 1111 0100 1. Арифметический сдвиг вправо. • Произведение 1111 0100, что равно −12. Вышеупомянутый метод неадекватен, когда множимое является наибольшим отрицательным числом, которое может быть представлено (т. Е. Если множимое имеет 8 битов, это значение равно -128). Одно из возможных исправлений этой проблемы - добавить еще один бит слева от A, S и P. Ниже мы продемонстрируем улучшенную технику, умножив −8 на 2, используя 4 бита для множимого и множителя:• A = 1 1000 0000 0 • S = 0 1000 0000 0 • P = 0 0000 0010 0 • Выполните цикл четыре раза: 1. P = 0 0000 0010 0. Последние два бита равны 00.  P = 0 0000 0001 0. Сдвиг вправо. 2. P = 0 0000 0001 0. Последние два бита равны 10.  P = 0 1000 0001 0. P = P + S.  P = 0 0100 0000 1. Сдвиг вправо. 3. P = 0 0100 0000 1. Последние два бита - 01.  P = 1 1100 0000 1. P = P + A.  P = 1 1110 0000 0. Сдвиг вправо. 4. P = 1 1110 0000 0. Последние два бита - 00.  P = 0 1111 0000 0. Сдвиг вправо. • Произведение равно 11110000 (после отбрасывания первого и последнего бита), что равно −16. Как это работает Рассмотрим положительный множитель, состоящий из блока единиц, окруженного нулями. Например, 00111110. Произведение определяется по формуле: Где M - множимое. Количество операций можно сократить до двух, переписав так же, как Фактически,можно показать, что любую последовательность единиц в двоичном числе можно разбить на разность двух двоичных чисел: Следовательно, мы можем фактически заменить умножение строкой единиц в исходном числе более простыми операциями, добавив множитель, сдвинув частичное произведение, таким образом, образованное соответствующими местами, а затем, наконец, вычитание множителя. Он использует тот факт, что нам не нужно ничего делать, кроме сдвига, когда мы имеем дело с 0 в двоичном умножителе, и аналогично использованию математического свойства, которое 99 = 100 - 1 при умножении на 99. Эта схема может может быть расширен до любого количества блоков единиц в умножителе (включая случай единственной единицы в блоке). Итак, БутАлгоритм s следует этой схеме, выполняя сложение, когда он встречает первую цифру блока единиц (0 1) и вычитание, когда он встречает конец блока (1 0). Это также работает для отрицательного множителя. Когда единицы умножителя сгруппированы в длинные блоки, алгоритм Бута выполняет меньше сложений и вычитаний, чем обычный алгоритм умножения.

Это прямой метод ... в книге для задержек есть потоковый график ... вы можете сослаться на него, если у вас есть какие-либо сомнения, позвольте мне знать