Введення в двійкову арифметику

Арифметичні операції над двійковими числами здійснюються за допомогою алгоритму, який в школі вивчають під назвою "складання в стовпчик".

Таблиця 1.1. Таблиця складання однорозрядних двійкових чисел

З таблиці. 1.1 видно, що результат складання двох однорозрядних чисел є дворозрядним (двозначним) числом, а результат складання два N-разрядных — N+1 -разрядным. Додатковий біт, що утворюється, називається бітом перенесення (carry bit).
При складанні двійкових чисел в стовпчик ми виписуємо їх один під одним (приклад 1.1). Два молодші розряди ми складаємо відповідно до таблиці. 1.1. При складанні подальших двох розрядів ми повинні враховувати не лише ці розряди, але і біт перенесення з молодшого розряду, тобто виробляти складання відповідно до таблиці. 1.2. З цієї таблиці видно, що для трьох однорозрядних доданків все одно виходить лише два біта суми, так що для роботи зі всіма подальшими розрядами ми можемо обійтися лише одним бітом перенесення (мал. 1.1).

Таблиця 1.2. Таблиця складання з врахуванням перенесення

Приклад 1.1. Складання двох 8-розрядних чисел (83 + 56 = 139)

Мал. 1.1. 8-розрядний двійковий суматор

Додатковий, 9-й розряд, що утворюється при складанні 8-розрядних чисел, переноситься в спеціальний біт слова стану процесора, який також називається бітом перенесення, і зазвичай позначається буквою З (від англ., саrrу — перенесення). Цей біт можна використовувати як умова в командах умовного переходу, а також для реалізації 16-розрядної операції складання або однойменної операції більшої розрядності на 8-розрядному АЛУ.
При операціях над беззнаковими (ненегативними) числами біт перенесення можна інтерпретувати як ознака переповнювання: тобто того, що результат не можна представити числом з розрядністю АЛУ. Ігнорування цього біта може наводити до неприємних наслідків: наприклад, складали ми 164 + 95, а отримали в результаті 3.
Інколи цей ефект, званий "обертанням лічильників", має і корисне вживання. Наприклад, використовуючи "годинний" кварцевий генератор з частотою 32 768 Гц і 15-розрядний двійковий лічильник, ми можемо відмірювати секунди по появі біта перенесення в 16-м розряді і позбавляємося від необхідності скидати сам лічильник.
Двійкове віднімання може виконуватися аналогічним чином, лише необхідно використовувати не таблиці складання, а таблиці віднімання для двох і три доданків. Не стомлюючи себе і читача виписуванням цих таблиць, скажемо відразу, що операція двійкового віднімання еквівалентна операції двійкового складання зменшуваного з двійковим доповненням від'ємника. Двійкове доповнення будується таким чином: всі біти числа інвертуються (нулі замінюються на одиниці, і навпаки), а потім до результату додається одиниця. Доказ цього твердження ми залишаємо цікавому читачеві, а самі просто розглянемо приклад 1.2.

Приклад 1.2. Віднімання чисел (83 — 56 = 27)

Побудова двійкового доповнення 56 :

Складання з двійковим доповненням (83 + 56) mod 256 = 27:

	1		0
+	0	1	0	1	0	0	1	1
	1	1	0	0	1	0	0	0
1	0	0	0	0	1	0	1	1

З прикладу видно, що еквівалентність між операціями неповна: складання з доповненням супроводиться перенесенням в 9-й розряд, якого немає при прямому відніманні. Цей факт наводить до того, що ми вже не можемо рахувати перенесення в 9-й розряд критерієм того, що результат складання не може бути представлений 8-у бітами. Точний критерій переповнювання для цілочисельних операцій складання і віднімання тепер звучить так: переповнювання сталося, якщо перенесення в 9-й біт (для 8-розрядного АЛУ) не дорівнює перенесенню в 10-й біт.
Але в останньому двійкове доповнення сильно спрощує життя проектувальникам процесорів: замість двох пристроїв, суматора і диференціатора (по-російськи, сложителя і вычитателя), нам досить мати лише суматор. Крім того, можна представляти негативні числа в двійково-додатковому коді (таблиця. 1.3). При такій виставі ознаку переповнювання називають також ознакою втрати знаку.
Видно, що чотири біта дозволяють нам представити або нуль і натуральні числа від 1 до 15, або цілі числа - 8 до 7. У другому випадку, старший біт може інтерпретуватися як знаковий — якщо він дорівнює 1, число негативне, якщо 0 — позитивне. Для маніпулювання числами в обох виставах можна використовувати одні і ті ж команди складання і віднімання, відмінність виникає лише, коли ми починаємо інтерпретувати результати порівняння таких чисел або самі ці числа (наприклад, переводити їх в десятковий формат).
Для команд множення і ділення трюк з двійковим доповненням не проходит, тому процесори, що використовують таке представлення даних, вимушені мати по дві пари команд множення і ділення, знакові і беззнакові. Допитливому читачеві пропонується самостійно Розробити алгоритми множення і ділення двійкових чисел в Двійково-додатковій виставі. За основу для цих алгоритмів знову-таки рекомендується узяти шкільні методи множення і ділення багатозначних чисел "в стовпчик".

Таблиця 1.3. Двійкове представлення знакових і беззнакових чисел

Переважна більшість сучасних процесорів використовують двійково-додаткову виставу для цілих чисел. В ті часи, коли комп'ютери були великими, зустрічалися системи, що застосовували для цієї мети додатковий, знаковий біт: число —1 представлялося так само, як +1, але зі встановленим знаковим бітом. Такі процесори повинні були мати окремі команди для беззнакових і знакових арифметичних операцій і складніше АЛУ. Крім того, при такій виставі виникає специфічна проблема "негативного нуля".
Інколи нарівні з двійковим використовується і специфічне, так зване двійково-десяткове представлення чисел (мал. 1.2). Ця вистава особлива зручно для додатків, які постійно вимушені використовувати десяткове введення і вивід (мікрокалькулятори, годинник, телефони з автовизначником номера і т. д.) і мають невеликий об'єм програмної пам'яті, в який недоцільно поміщати універсальну процедуру перетворення чисел з двійкової вистави в десяткове і назад.
У такій виставі десяткова цифра позначається тетрадою, чотирма бітами. Цифри від 0 до 9 представляються 0, 1111 недопустимы.своими двійковими еквівалентами, а комбінації бітів 1010, 1011, 1100, 1101, 111

Мал. 1.2. Двійково-десяткове представлення чисел

Замість арифметичних операцій над такими числами більшість сучасних мікропроцесорів пропонують використовувати для їх складання і віднімання звичайні бінарні операції, а потім виправляти недопустимі значення, що виникають при цьому, за допомогою спеціальної команди двійково-десятковій корекції. Алгоритм роботи цієї команди читачеві пропонується розробити самостійно. Для нього буде потрібно інформацію про те, чи відбувалося при складанні двійкове перенесення з молодшої тетради. Процесори, що надають таку команду, мають і біт міжтетрадного перенесення.
Якщо операція виробляється над числами, що мають 16 або більш двійкових розрядів (4 і більш двійково-десяткових), для корекції нам недостатньо одного міжтетрадного перенесення — треба мати по біту перенесення на кожну з пар послідовних тетрад. Так далеко жоден з існуючих процесорів не заходить. Наприклад, 32-розрядні процесори х86 мають команди двійково-десяткової корекції лише для операцій над числами з 8-у двійковими (двома двійково-десятковими) розрядами.