Двоичная арифметика и знаковые целые числа
Введено| English | Значение |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | переполнение |
| two's complement/tuːz ˈkɒmplɪmənt/ | дополнительный код |
| register/ˈredʒɪstə/ | регистр |
| sign bit/saɪn bɪt/ | знаковый бит |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | старший значащий бит |
| one's complement/wʌnz ˈkɒmplɪmənt/ | обратный код |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | двоично-десятичный код |
Банк, потерявший день
- На 1 сентября 1983 индекс фондовой биржи Ванкувера составлял 524.811. Он открылся на отметке 1000 двадцать два месяца назад, и рынок рос все это время.
- Программа пересчитывала индекс после каждой сделки, отбрасывая дробную часть вместо округления каждый раз. Каждый раз терялась доля пункта. Три тысячи сделок в день сделали свое дело.
- При правильном пересчете индекс составил 1098.892: арифметика, а не рынок, уменьшила его вдвое.
- Арифметика на фиксированном количестве битов — это не та арифметика, которую вы изучали в школе. Этот урок посвящен сложению в двоичной системе, переполнению, вычитанию с помощью дополнительного кода, знаковым целым числам и BCD.
Сложение в двоичной системе
- Складывайте столбиком справа налево, перенося единицу в следующий разряд, точно так же, как в десятичной системе.
- Правила: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, пишите 0 и переносите 1; $1 + 1 + 1 = 11$, пишите 1 и переносите 1.
0101$+$0011$=$1000, то есть $5 + 3 = 8$.
Тот же метод, что и в десятичной системе, только две цифры для переноса
Двоичные & знаковые целые числа
байт = сумма позиций значений
Посмотрите, как 8-битный паттерн отображается на число (и как происходит переполнение за пределы 255).
Сложите двоичные числа 0101 + 0011. Дайте результат в 4 битах.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$5 + 3 = 8$, что в двоичной системе равно 1000.
Переполнение
- Переполнение происходит, когда результат вычисления требует больше битов, чем может вместить регистр. Перенос из старшего разряда теряется, поэтому сохраненный ответ неверен.
- Это свойство ширины регистра, а не числа 255: в 16-битном регистре та же сумма является корректной.
- В знаковой арифметике признаком является неправильная инверсия знакового бита: два положительных числа дают отрицательное, или два отрицательных дают положительное.
Переполнение при сложении в двоичной системе означает:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Переполнение возникает, когда сумма слишком велика, чтобы поместиться в доступные биты; перенос из левого разряда теряется.
Разобранный пример: правильно назовите переполнение
- Сложите беззнаковые 8-битные числа
10110101и01101100и прокомментируйте результат. - Сумма составляет
1 0010 0001, что требует 9 бит. Истинный результат равен 289. - Полный ответ: произошло переполнение, потому что 289 больше максимального значения, которое может хранить 8-битный регистр (255); перенос из старшего бита теряется, поэтому сохраненный результат
0010 0001равен 33, что неверно. - Баллы начисляются за указание ширины регистра и утверждение, что результат не может быть представлен в нем. Фраза «Ответ превысил 255» сама по себе не оценивается.
Складываются два 8-битных беззнаковых целых числа, и результат требует 9 битов. Какой ответ является полным объяснением?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Укажите ширину регистра, скажите, что результат не может быть в нем представлен, и опишите, что происходит с переносом. Остальные варианты указывают лишь на симптом, но не на причину.
Вычитание с помощью дополнительного кода
- Для вычисления $A - B$: образуйте дополнительный код числа $B$, инвертировав каждый бит и прибавив 1, сложите его с $A$, затем отбросьте любой итоговый перенос.
- $100 - 30$ в 8 битах: дополнительный код числа
0001 1110получается инверсией1110 0001плюс 1, то есть1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; отбросьте ведущую 1 и прочитайте0100 0110$= 70$. ✓
Вычитание становится сложением, поэтому процессорам не нужен отдельный вычитатель
Чему равно 4-битное дополнение до двух для 0011? (инвертируйте, затем добавьте 1)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Инвертируем 0011 → 1100, затем добавляем 1 → 1101 (что представляет $-3$).
Расставьте шаги вычитания B из A с помощью дополнения до двух в правильном порядке.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Инвертируйте, добавьте единицу, прибавьте, отбросьте. Отбрасывание именно то, что удерживает ответ в пределах ширины регистра.
Знаковые целые числа в дополнительном коде
- В числе в дополнительном коде на $n$ бит старший значащий бит является знаковым битом: 0 означает положительное, 1 — отрицательное. Эквивалентно, старший бит имеет отрицательное разрядное значение, $-2^{n-1}$.
- Чтобы прочитать отрицательное число: инвертируйте каждый бит, добавьте 1, затем поставьте знак минус перед результатом.
1011 0100инвертируется в0100 1011, плюс 1 равно0100 1100$= 76$, поэтому значение составляет $-76$. Проверка по разрядным значениям: $-128 + 32 + 16 + 4 = -76$. ✓ - Для $n$ бит диапазон составляет от $-2^{n-1}$ до $+2^{n-1} - 1$: 8 бит дают от $-128$ до $+127$, 12 бит дают от $-2048$ до $+2047$. Наименьшее отрицательное число — это 1, за которой следуют нули; наибольшее положительное — это 0, за которой следуют единицы.
11111111 это 255 при одном прочтении и −1 при другом
Знаковые биты дополнения до двух
Левый бит имеет отрицательное значение разряда. Инвертируйте любой бит — или нажмите Negate (инвертировать все биты, затем добавить 1) — и наблюдайте, как меняется знаковое значение.
Прочитайте 8-битное число дополнения до двух 11111101 как знаковое десятичное значение.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
MSB равен 1 (отрицательное). Инвертируем → 00000010, добавляем 1 → 00000011 $= 3$, значит значение равно $-3$.
Какое максимальное положительное значение может хранить 8-битное число дополнения до двух?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Диапазон составляет $-2^{7}$ до $2^{7}-1$, т.е. $-128$ до $+127$. Максимум равен 01111111 = 127.
Разобранный пример: запишите −108 в 12 битах
- Начните со $+108$ в 12 битах: $108 = 64 + 32 + 8 + 4$, значит
0000 0110 1100. - Инвертируйте каждый бит:
1111 1001 0011. Добавьте 1:1111 1001 0100. - Проверьте с помощью разрядных значений, где старший бит равен $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- Самая частая ошибка — знаковое представление с модулем (sign and magnitude): установка старшего бита в 1 и сохранение остальных. Это другая, более старая схема, которая здесь не засчитывается.
Запишите −108 в виде 12-битного числа дополнения до двух (пробелы допускаются).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
+108 = 0000 0110 1100; инвертируем до 1111 1001 0011 и добавляем 1. Проверка: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108.
Обратный код
- Обратный код — это более старая схема: отрицательное число образуется путем инверсии каждого бита положительного числа без шага добавления 1. $+30$ это
0001 1110, значит $-30$ это1110 0001. - Его недостаток — два нуля,
0000 0000и1111 1111, что тратит битовый паттерн и усложняет арифметику. - Дополнительный код имеет один ноль и позволяет одной и той же схеме сумматора выполнять вычитание, поэтому он победил.
Дополнение до единиц предпочтительнее дополнения до двух, потому что оно имеет только одно представление нуля.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Наоборот: дополнение до единиц имеет два нуля, +0 и −0. Дополнение до двух имеет один ноль и позволяет сумматору выполнять вычитание.
Двоично-десятичный код
- В двоично-десятичном коде (BCD) каждая десятичная цифра хранится как собственный 4-битный паттерн, используя только
0000до1001. - 93 в BCD это
1001 0011, что не то же самое, что 93 в чистой двоичной системе,0101 1101. Чтение одного как другого — любимый ловушка экзаменов. - Применение: калькуляторы, цифровые часы и семисегментные дисплеи, где каждая цифра управляется отдельно, и валюта, где BCD избегает ошибок округления при хранении $0.1$ в чистой двоичной системе. Стоимость — потраченные впустую паттерны, поскольку
1010до1111никогда не используются.
Одна цифра, один ниббл, один дисплей
Запишите десятичную цифру $9$ в виде 4-битного паттерна BCD.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$9$ это 1001. В BCD каждой десятичной цифре выделяется свой собственный полубайт (0000–1001).
Соотнесите каждый битовый паттерн с тем, что он обозначает.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Ничто в самих битах не говорит, как их читать. Решение о представлении принимается договоренностью, которая определяет значение.
Потерянные баллы
- Объясните переполнение, используя ширину регистра, указанную в задании, а не фразу «это было больше 255».
- Для инвертирования инвертируйте биты и прибавьте 1. Установка старшего бита в 1 соответствует знаковому представлению с модулем, что является другой схемой.
- Вычитание в дополнительном коде заканчивается отбрасыванием последнего переноса. Если его сохранить, получится девятибитный результат.
- BCD хранит каждую цифру отдельно; двоичное число хранит всё число целиком.
1001 0011в BCD равно 93, а в двоичной системе — 147.
Вы поняли
- Складывайте по разрядам с учетом переносов; переполнение — это результат, требующий больше бит, чем вмещает регистр, и ответ должен указывать на эту ширину
- Вычитайте путем сложения дополнительного кода: инвертируйте биты, добавьте 1, затем отбросьте последний перенос
- Знаковое: MSB является знаковым битом и несет $-2^{n-1}$; диапазон $-2^{n-1}$ до $+2^{n-1}-1$; чтобы прочитать отрицательное значение, инвертируйте биты, добавьте 1 и измените знак
- Обратный код только инвертирует биты и имеет два нуля; BCD хранит каждую десятичную цифру в отдельной ниббле, используется в часах, калькуляторах и финансовых расчетах