Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

проектная компания Казань, android | | финская сауна как построить
 

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

  А для такого низького життя були числа
Як домашній, под'яремний худоба
Тому, що всі відтінки сенсу
Розумне число передасть
Н. Гумільов

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

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

0 + 0 = 00
0+1 =01
1+0 = 01
1 + 1 = 10

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

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

0+0+0=0
0+1+0=01
1+0+0=01
0+0+1=01
1+1+0=10
1+0+1=10
0+1+1=10
1+1+1=11

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

    1 1           перенесення
+ 0 1 0 1 0 0 1 1 1-й доданок
  0 0 1 1 1 0 0 0 2-й доданок

 
  1 0 0 0 1 0 1 1 результат

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

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

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

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

0 0 1 1 1 0 0 0 число
1 1 0 0 0 1 1 1 побітове заперечення
1 1 0 0 1 0 0 0 побітове отріцаніє+1

Складання з двійковим доповненням (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. Двійкове представлення знакових і беззнакових чисел

Беззнакове Знакове Двійкове
7 +7 0111
6 +6 0110
5 +5 0101
4 +4 0100
3 +3 0011
2 +2 0010
1 +1 0001
0 0 0000
15 -1 1111
14 -2 1110
13 -3 1101
12 -4 1100
11 -5 1011
10 -6 1010
9 -7 1001
8 -8 1000

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

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

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


:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017