Таблица сложения
| ai | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | ||||||||||||||||
| bi | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |||||||||||||||||
| Pi-1 | 0 | 0 | 0 | 0 |  | | | | 1 | 1 | 1 | 1 | |||||||||||||||||
| gi | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |||||||||||||||||
| Pi | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 0 | | | |
| Примеры: | 3 | ~ | 0 | 0 | 1 | 1 | 1 | +9 | ~ | 1 | 1 | 0 | 0 | 1 | |||||||||||||||||
| 5 | ~ | 0 | 0 | 1 | 0 | 1 | ?6 | ~ | 0 | 1 | 1 | 1 | 0 | ||||||||||||||||||
| 8 | ~ | 1 | 1 | 0 | 0 | 0 | +3 | ~ | 0 | 0 | 1 | 1 | 1 |
2. Вычитание. Так как a-b = a+b?2b = a+b+b(?2), причем b(?2) – это число b, сдвинутое на один разряд влево, то алгоритм вычитания может быть сформулирован так. Для того чтобы из a вычесть b, необходимо к a прибавить b и прибавить b, сдвинутое на один разряд влево.
Примеры:
| а) | +6 | ~ | 1 | 1 | 0 | 1 | 0 | б) | –5 | ~ | 0 | 1 | 1 | 1 | 1 | в) | –7 | ~ | 0 | 1 | 0 | 0 | 1 | ||||||||||||||||||||||||||||||||
| – | – | – | |||||||||||||||||||||||||||||||||||||||||||||||||||||
| +3 | ~ | 0 | 0 | 1 | 1 | 1 | +4 | ~ | 0 | 0 | 1 | 0 | 0 | –10 | ~ | 0 | 1 | 0 | 1 | 0 | |||||||||||||||||||||||||||||||||||
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | ||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 1 | 1 | 1 | (+сдвинутое 3) | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | ||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 0 | 1 | 1 | 1 | = +3 | 0 | 1 | 0 | 1 | 1 | = –9 | 0 | 0 | 0 | 1 | 1 | 1 | = +3 |
3. Умножение Операция умножения осуществляется посредством последовательных сложений и сдвигов.
Примеры.
|
а) |
2 |
~ |
0 |
0 |
1 |
1 |
0 |
б) |
3 |
~ |
0 |
0 |
1 |
1 |
1 |
||||||
|
х |
х |
||||||||||||||||||||
|
5 |
~ |
0 |
0 |
1 |
0 |
1 |
–3 |
~ |
0 |
1 |
1 |
0 |
1 |
||||||||
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
||||||||||||
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|||||||||||||
|
0 |
1 |
1 |
1 |
1 |
0 |
= +10 |
0 |
0 |
1 |
1 |
1 |
||||||||||
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
= –9 |
4. Деление. Пусть требуется разделить число u на a и получить частное w, т. е. u : a = w.
Введем следующие обозначения:
ak – a, сдвинутое на k разрядов влево;
ui+1=ui – ak,, на каждом шаге алгоритма индекс у ui увеличивается на 1;
N(u) – номер разряда старшей значащей цифры.
Разрядность частного w равна k+1:
(?2)k, (?2)k-1, ..., (?2)0.
Алгоритм деления.
1. Сдвигаем a на k разрядов влево до тех пор, пока старшая значащая цифра у a не станет под старшей значащей цифрой u, таким образом:
a ® ak, т. е. a преобразуется в ak;
u = u0, т. е. u присваивается начальное обозначение u0.
2.
Вычитаем u0 – ak, т. е. u1 = u0+ak+(–2) ak.
3. Если N(ui+1)=N(ak), то записываем "1" в разряд (–2)k
частного и еще раз вычитаем ak.
4. Если N(ui+1)<N(ak), то записываем "1" в разряд (–2)k частного и ak
меняем на ak-1, т. е. сдвигаем ak на 1 разряд вправо и вычитаем ak-1.
5. Если N(ui+1)>N(ak), то записываем "0" в разряд (–2)k
частного, ui+1
заменяем на ui,
ak меняем на ak-1 и производим вычитание.
6. Процесс завершается, если ui+1=0.
Замечание 1. Результат "0" или "1" записывается в разряд частного с весом (–2)k, где k – индекс у a.
Замечание 2. Возможен случай, когда в один и тот же разряд частного записывается несколько значений. Тогда для получения частного необходимо дополнительно выполнить одну операцию сложения.
Пример 1. Пусть необходимо число 14 разделить на число 2, т. е. u0=14, a=2. Тогда 14~10010(–2), 2~110(–2). Для выравнивания делимого и делителя сдвигаем a на два разряда влево, т. е. a® a2 =11000.
Структура частного w:
|
Веса разрядов |
(–2)2 |
(–2)1 |
(–2)0 |
|
|
Частное |
+1 |
+1 |
+1 |
|
|
+1 |
||||
|
110 |
1 |
1 |
= 7 |
Процесс деления:
|
1 |
0 |
0 |
1 |
0 |
u0 |
|||||
|
1 |
1 |
0 |
0 |
0 |
a2 |
|||||
|
Записываем |
1 |
1 |
0 |
0 |
0 |
|||||
|
"1" во второй разряд |
¬ |
0 |
1 |
1 |
0 |
1 |
0 |
u1 |
N(u1)=N(a2) |
|
|
1 |
1 |
0 |
0 |
0 |
a2 |
|||||
|
Записываем |
1 |
1 |
0 |
0 |
0 |
|||||
|
"1" во второй разряд |
¬ |
0 |
0 |
0 |
0 |
1 |
0 |
u2 |
N(u2)<N(a2) |
|
|
1 |
1 |
0 |
0 |
a1 |
||||||
|
Записываем |
1 |
1 |
0 |
0 |
||||||
|
"1" в первый разряд |
¬ |
0 |
0 |
0 |
1 |
1 |
0 |
u3 |
N(u3)<N(a1) |
|
|
1 |
1 |
0 |
a0 |
|||||||
|
Записываем |
1 |
1 |
0 |
|||||||
|
"1" в нулевой разряд |
¬ |
0 |
0 |
0 |
0 |
0 |
0 |
u4 |
N(u4)<N(a0) |
|
Процесс stop, ибо u4=0.
Пример 2. Пусть u0=12, a=2. Тогда 12 ~ 11100(–2), 2 ~ 110(–2).
a® a2 =11000.
Структура частного w:
|
Веса разрядов |
(–2)2 |
(–2)1 |
(–2)0 |
|
|
Частное |
1 |
0 |
1 |
|
|
1 |
||||
|
110 |
1 |
0 |
= 6 |
Процесс деления:
|
1 |
1 |
1 |
0 |
0 |
u0 |
||||||
|
1 |
1 |
0 |
0 |
0 |
a2 |
||||||
|
1 |
1 |
0 |
0 |
0 |
|||||||
|
Записываем |
|||||||||||
|
"1" во второй разряд |
¬ |
0 |
0 |
0 |
1 |
0 |
0 |
u1 |
N(u1)<N(a2) |
||
|
1 |
1 |
0 |
0 |
a1 |
|||||||
|
Записываем |
1 |
1 |
0 |
0 |
|||||||
|
"0" в первый разряд |
¬ |
1 |
1 |
0 |
0 |
0 |
u2 |
N(u2)>N(a1) |
u1 возврат
|
0 |
0 |
1 |
0 |
0 |
u1 |
||||||
|
0 |
1 |
1 |
0 |
a0 |
|||||||
|
Записываем |
0 |
1 |
1 |
0 |
|||||||
|
"1" в нулевой разряд |
¬ |
0 |
0 |
1 |
1 |
0 |
u2’ |
N(u2’)=N(a0) |
|||
|
|
0 |
1 |
1 |
0 |
|
||||||
|
Записываем |
0 |
1 |
1 |
0 |
|||||||
|
"1" в нулевой разряд |
¬ |
0 |
0 |
0 |
0 |
0 |
u3 |
N(u3)<N(a0) |
Процесс окончен, так как u3=0.
