Сложение и вычитание целых чисел со знаком

Представление целых чисел

Рассмотрим n-разрядный вектор

В = b _n-1 … b ₁ b ₀

Здесь bi = 0 или 1 при 0 ≤ i ≤ n-1. Этот вектор может представлять беззнаковое це­лочисленное значение V в диапазоне от 0 до 2ⁿ-1, где

V(B) = b_n-1 x 2^n-1 +...+b₁ x 2¹ + b₀ x 2⁰

Совершенно очевидно, что нам необходимо как-то представлять и положи­тельные, и отрицательные числа. Существуют три системы представления чисел со знаком:

- значение со знаком;

- дополнение до единицы;

- дополнение до двух.

Во всех трех системах крайний слева бит, называемый самым старшим разря­дом (Most Significant Bit, MSB), равен 0 в случае положительных чисел и 1 — в случае отрицательных. На рис. 4.1 все три представления показаны на примере 4-разрядных (4-битовых) чисел. Положительные значения во всех трех системах представляются одинаково, а отрицательные — по-разному. В системе значения со знаком отрицательные числа отличаются от соответствующих положительных чисел тем, что значение самого старшего бита (bз на рисунке 4.1) в векторе В равня­ется не 0, а 1. Например, число +5 представляется как 0101, а число -5 как 1101. Такое представление чисел называют еще прямым кодом числа со знаком. В представлении дополнения до единицы отрицательные значения получают пу­тем дополнения каждого разряда соответствующего положительного значения до единицы. Таким образом, представление числа -3 формируется путем дополнения каждого бита вектора 0011, так что в результате получается 1100. Такое представление чисел еще называют обратным кодом числа. Очевидно, что эту же операцию необходимо выполнить для преобразования отрицательного числа в соответствующее положительное значение. И в одном и в другом случае преобразо­вание называется дополнением числа до единицы. Операция формирования до­полнения заданного числа до единицы эквивалентна вычитанию этого числа из 2ⁿ-1, то есть из 1111 в случае 4-разрядных чисел (см. рис. 4.1). В системе допол­нения до двух операция дополнения производится путем вычитания числа из 2ⁿ. То же самое значение можно получить и путем добавления 1 к дополнению этого числа до единицы. Такое представление числа еще называют дополнительным кодом числа.

Обратите внимание, что в системах значения со знаком и дополнения до едини­цы числа +0 и -0 представляются по-разному, а в системе дополнения до двух — одинаково. Имея всего четыре разряда, значение -8 можно представить в системе дополнения до двух, но нельзя представить ни в одной из двух других систем. Для нас наиболее естественной представляется система значения со знаком, по­скольку мы привыкли иметь дело с десятичными значениями со знаком. Систему дополнения до единицы относительно легко связать с системой значения со зна­ком, а вот система дополнения до двух кажется несколько неестественной. Но, как будет показано дальше, именно она оказалась наиболее эффективным способом представления чисел с точки зрения выполнения операций сложения и вычитания. Поэтому она чаще всего используется и в компьютерах.

Рис. 4.1. Двоичное представление целых чисел со знаком

Сложение положительных целых чисел

Рассмотрим принцип сложения двух одноразрядных чисел. Результат выполне­ния этой операции приведен на рис. 4.2. Обратите внимание, что для записи ре­зультата сложения двух единиц необходим 2-битовый вектор 10, представляю­щий значение 2. В этом случае говорят, что сумма равняется 0, а перенос — 1. Для сложения многоразрядных чисел используется метод, аналогичный тому, с помо­щью которого мы складываем десятичные числа на бумаге. Складываются пары разрядов, начиная с младшего разряда, то есть с правого края битового вектора, с переносом в направлении старшего разряда, то есть левого края битового вектора.

0 1 0 1

+0 +0 +1 +1

0 1 1 10

↑

Перенос

Рис. 4.2. Сложение одноразрядных чисел

Сложение и вычитание целых чисел со знаком

Итак, вы уже знакомы с тремя системами представления положительных и отри­цательных чисел, или, проще говоря, чисел со знаком. Эти системы различаются только способами представления отрицательных значений. Их сравнительные преимущества с точки зрения выполнения арифметических операций можно оп­ределить так: простейшая с точки зрения представления чисел система значения со знаком наименее удобна для их сложения и вычитания. Система дополнения до единицы несколько лучше. А наиболее эффективной с точки зрения выполне­ния указанных операций является система дополнения до двух.

Чтобы понять принципы арифметики дополнений до двух, нужно рассмотреть операцию сложения по модулю N (обозначаемую как mod N). Удобным графиче­ским представлением сложения положительных чисел по модулю N является круг с N значениями по его периметру: от 0 до N - 1 (рис. 4.2, а). Для примера рассмот­рим значение N = 16. Результатом операции (7 + 4) mod 16 является значение 11. Для того чтобы выполнить эту операцию с помощью графического представле­ния, найдите на окружности отметку 7 и переместитесь от нее на четыре деления по часовой стрелке. Там вы найдете ответ — значение 11. Аналогичным образом (9 + 14) mod 16 = 7. Найдя значение 9 и отсчитав от него 14 делений, вы опишете полный круг и остановитесь на делении 7. Этот нехитрый графический прием по­зволяет вычислить любую сумму (а + b) mod 16 для любых положительных чисел а и b: вы находите число а и перемещаетесь на b делений по часовой стрелке.

Теперь рассмотрим другую интерпретацию окружности mod 16. Предположим, что значения из диапазона от 0 до 15 представлены в соответствии с двоичной сис­темой счисления 4-битовыми двоичными векторами: 0000, 0001,..., 1111. А двоич­ные векторы, как видно на рис. 4.3, б, представляют числа со знаком от -8 до +7, что соответствует системе дополнения до двух (рис. 4.1).

Давайте применим графическую технологию сложения по модулю 16 к про­стому примеру сложения чисел +7 и -3. В системе дополнения до двух эти числа представлены как 0111и1101 соответственно. Для того чтобы их сложить, найди­те на окружности число 0111 и переместитесь на 1101 шагов по часовой стрелке (то есть на 13 шагов — сосчитайте количество делений от 0 до 1101). Вы окаже­тесь на делении 0100, представляющем ответ, а именно +4 (рис. 4.2, б). Если вы выполните эту операцию путем сложения пар разрядов справа налево, результат будет таким:

+ 1101

1 0100

↑

Перенос

Как видите, для получения правильного результата мы проигнорировали пе­ренос из четвертого разряда. В этом и состоит суть сложения по модулю. Переме­щаясь по кругу (рис. 4.2, 6), мы возвращаемся не к значению 10000, следующему за значением 1111, а к значению 0000.

Рис. 4.2. Сложение по модулю и сложение в системе дополнения до двух:

представление операций над целыми числами по модулю N (а); операции над числами в системе дополнения до 2 по модулю 16 (б)

Теперь мы можем описать правила сложения и вычитания n-разрядных чисел со знаком в системе дополнения до двух.

1. Для сложения двух чисел следует сложить их n-разрядные представления, игнорируя сигнал переноса из позиции старшего разряда (MSB). Суммой будет алгебраически правильное значение, представленное в системе допол­нения до двух, если это значение лежит в диапазоне от -2^n-l до +2^n-1 - 1.

2. Для вычитания чисел Х и У, то есть выполнения операции Х - Y, следует вычислить дополнение числа Y до двух, а затем добавить его к числу X с учетом правила 1. Результатом будет алгебраически правильное значе­ние, представленное в системе дополнения до двух, если это значение ле­жит в диапазоне от -2^n-l до +2^n-1 - 1.

На рис. 4.3 показано несколько примеров сложения и вычитания 4-разрядных двоичных чисел. Во всех этих примерах ответ оказывается в диапазоне от -8 до 7. Если ответ выходит за границу указанного диапазона, мы говорим, что произош­ло арифметическое переполнение. Такие ситуации рассматриваются ниже. Представленные здесь четыре операции сложения (рис. 4.3, а-г) вы­полнены по правилу 1, а шесть операций вычитания (рис. 4.3, д-к) — по правилу 2. В операции вычитания для вычитаемого (нижнее значение) сначала выполняется вычисление дополнения, а затем сложение — точно так же, как в случае двух по­ложительных чисел.

В программировании часто возникает необходимость выразить некоторое чис­ло, заданное в системе дополнения до двух, с использованием определенного ко­личества разрядов, большего, чем необходимо для представления этого числа на самом деле. Если речь идет о положительных числах, для этого достаточно просто добавить слева нужное количество нулей. В случае отрицательных чисел край­ний слева бит, представляющий знак числа, должен быть равен 1, и для получе­ния более длинного представления того же значения нужно повторить знаковый бит слева от числа столько раз, сколько нужно для достижения заданной длины. Чтобы понять, почему нужно действовать именно так, давайте снова вернемся к окружности для сложения по модулю 16, показанной на рис. 4.2, б. Сравните эту окружность с окружностью для сложения по модулям 32 и 64. Представление от­рицательных чисел, -1, -2 и т. д., будет точно таким же, с дополнительной едини­цей слева. Операция добавления единицы называется расширением знака.

Теперь вы знаете, насколько просто выполняется сложение и вычитание чисел со знаком в системе дополнения до двух. Поэтому для представления чисел в со­временных компьютерах выбрана именно эта система. Может показаться, что и система дополнения до 1 не хуже, но это только на первый взгляд. Хотя вычис­лить дополнение до единицы и проще, результаты операции сложения не всегда оказываются правильными. В данном случае нельзя игнорировать перенос, с_n. Если с_n = 0, полученный результат будет верным. Но если с_n = 1, то для определе­ния точного результата к полученному значению нужно добавить 1. Необходи­мость в этом поправочном цикле, зависящая от значения переноса, делает опера­ции сложения и вычитания в системе дополнения до единицы более сложными, чем в системе дополнения до двух.

Рис. 4.3. Операции сложения и вычитания в системе дополнения до двух