Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Бута - Пример

Вычислить 3 ×. В этом случае m = 3, r = −4, x = 4, y = 4:

• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0

• Выполним цикл 4 раза :
  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

Вышеупомянутой техники недостаточно, когда множимое является наибольшим по модулю отрицательным числом, которое может быть представлено в текущей разрядной сетке. Один из возможных способов решить эту проблему — добавить один дополнительный бит слева от A, S и P. Ниже мы покажем усовершенствованную технику на примере умножения −8 на 2 используя по 4 бита под множимое и множитель:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0

• Выполним цикл 4 раза :
  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 = 1 1111 0000 0. Арифметический сдвиг вправо.

• После отбрасывания крайних бит, получаем значение произведения: 11110000.