Лучшие вопросы
Таймлайн
Чат
Перспективы
Дополнительный код
Способ представления отрицательных чисел в компьютерах Из Википедии, свободной энциклопедии
Remove ads
Дополнительный код (англ. "two’s complement", иногда "twos-complement") — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, что упрощает архитектуру ЭВМ. В англоязычной литературе «обратный код» (инверсия прямого кода) называют «первым дополнением» (англ. "ones' complement"), а «дополнительный код» называют «вторым дополнением» (англ. "two’s complement").
Дополнительный код для отрицательного числа можно получить инвертированием его двоичного модуля (получается "первое дополнение") и прибавлением к инверсии единицы (получается "второе дополнение"), либо вычитанием числа из нуля (сразу получается "второе дополнение").
Дополнительный код двоичного числа определяется как величина, полученная вычитанием модуля числа из наибольшей степени двух (из для -битного второго дополнения).
Remove ads
История
То, что отрицательные числа в дополнительном коде можно складывать на сумматоре, было известно ещё во времена Паскаля, который и применил это свойство в своей суммирующей машине "Паскалина".
Представление отрицательного числа в дополнительном коде
Суммиров вкратце
Перспектива
При записи числа в дополнительном коде старший разряд является знаковым. Если значение старшего разряда равно 0, то это значит, что в остальных разрядах записано положительное двоичное число, совпадающее с прямым кодом.
Двоичное 8-разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах, равно .
Примеры:
Remove ads
Дополнительный код в иной системе счисления
Суммиров вкратце
Перспектива
Тот же принцип можно использовать и в компьютерном представлении любой системы счисления, например, для десятичных чисел.
Преобразования на примере десятичной системы счисления[1]
Положительное число
Изменение значений текущих разрядов числа не производится, но дописывается знаковый старший разряд, значение которого равно 0. Например число [+12'345] будет иметь следующее представление - [012'345]
Отрицательное число
Дописываем знаковый старший разряд, равный большей цифре данной системы счисления, в нашем случае - это 9, а также изменяем остальные разряды по определённому правилу; пусть значение цифры каждого разряда будет представлено переменной , кроме знакового, тогда представим следующий алгоритм действий:
- Присвоим переменной новое значение, равное выражению (процесс получения обратного кода) - например отрицательное число [-12345] в прямом коде от старшего к младшему разряду будет иметь вид [9'12345], где - знаковая цифра, а в обратном представлении кода будет иметь следующий вид - [9'87654].
- К результирующему числу прибавим , так число [9'87654] (первое дополнение) будет иметь вид [987'655] (доп. код).
- Если возникла ситуация переноса разряда, в результате которого образовался новый разряд, то его (старший разряд) опускаем, а результирующее число считаем положительным. Результирующее положительное число будет одинаково представлено, как в прямом, так и в дополнительном коде. Например, имея возможность представить в таком виде отрицательный и положительный нуль, разберём их перевод в дополнительный код (1 знаковый и 4 дополнительных разряда):
- [+0] в прямом коде [0'0000]. Первое и второе дополнения равны [0'0000].
- [-0] в прямом коде [9'0000]. Первое дополнение - [9'9999]. При получении второго дополнения старший разряд числа [(1)0'0000] опускаем и получаем результирующее значение [0'0000], как у числа [+0].
Идея представления десятичного (как и любого другого) числа в дополнительном коде, идентична правилам для двоичной системы счисления и может использоваться в гипотетическом процессоре:
Арифметика в дополнительном коде
Сложение и вычитание
Оба числа представляются в дополнительном коде. Дополнительный код обоих чисел имеет одинаковое количество разрядов. В данном представлении числа складываются.
Знаки разные: Если в процессе сложения образуется выходящий за пределы первоначальных чисел разряд, то он опускается. Результирующее значение считается положительным, где прямой и дополнительный коды являются идентичными. Иначе — отрицательным в виде дополнительного кода.
Например:
- [1234] + [-78] → [0’1234] + [9’9922] = [(1)0’1156] = [1156].
- [-1234] + [78] → [9’8766] + [0’0078] = [9’8844] = [-1156].
Знаки одинаковые:
- Положительные числа. Разряд не опускается, результат положительный.
- Отрицательные числа. Разряд опускается, результат отрицательный в дополнительном коде.
Например:
- [1234] + [78] → [0’1234] + [0’0078] = [0’1312] = [1312].
- [-1234] + [-78] → [9’8766] + [9’9922] = [(1)9’8688] → (первое дополнение) [0’1311] → (второе дополнение или обычное представление) [-1312]. При переводе из дополнительного кода в обычное представление результирующее значение является абсолютным.
Remove ads
Преобразование в дополнительный код
Суммиров вкратце
Перспектива
Из прямого в дополнительный код
Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.
- Если старший (знаковый) разряд числа, записанного в прямом коде, равен 0, то число положительное и никаких преобразований не делается;
- Если старший (знаковый) разряд числа, записанного в прямом коде, равен 1, то число отрицательное, все разряды числа, кроме знакового, инвертируются, а к результату прибавляется 1.
Для примера преобразуем отрицательное число , записанное в прямом коде, в дополнительный код.
Прямой код отрицательного числа : 1000 0101
- Инвертируем все разряды числа, кроме знакового, получая таким образом обратный код (первое дополнение) отрицательного числа :
1111 1010
- Добавим к результату , получая таким образом дополнительный код (второе дополнение) отрицательного числа :
1111 1011
Изменение знака числа
Для преобразования отрицательного числа , записанного в дополнительном коде, в положительное число , записанное в прямом коде, используется похожий алгоритм:
- Инвертируем все разряды отрицательного числа , получая таким образом положительное число 4 в прямом коде:
0000 0100
- Добавив к результату получим положительное число в прямом коде:
0000 0101
И проверим, сложив получившееся записи и :0000 0101 + 1111 1011 = 0000 0000 (пятый и старше разряды выбрасываются)
Remove ads
p-адические числа
В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 00015 (110), равно 44445 (−110).
Реализация алгоритма нахождения модуля для дополнительного кода
Суммиров вкратце
Перспектива
TurboBasic
DEF FN TwosComplAbs%(a%)
IF a% < 0 THEN a% = NOT(a% - 1)
FN TwosComplAbs% = a%
END DEF
Pascal
function TwosComplAbs(a: integer): integer;
begin
if (a < 0) then TwosComplAbs := (not a) + 1
else TwosComplAbs := a;
end;
C/C++
int twos_compl_abs(int a)
{
if (a < 0) a = (~a) + 1;
return a;
}
Реализация без ветвления
С помощью следующей формулы можно вычислить модуль числа без ветвления[2]:
- ,
где: — Операция исключающего "или";
— Арифметический сдвиг вправо;
— Количество двоичных разрядов
Следующий код на языке Си вычисляет модуль по этой формуле:
int32_t fastabs32(int32_t num)
{
int32_t mask = (num >> 31);
return ((num ^ mask) - mask);
}
Remove ads
Преимущества и недостатки
Преимущества
- Общие инструкции (процессора) для сложения, вычитания и левого сдвига для знаковых и беззнаковых чисел (различия только в арифметических флагах, которые нужно проверять для контроля переполнения в результате).
- Отсутствие числа «минус ноль».
Недостатки
- Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
- В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно.
- Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 12710 = 011111112, минимальное число: -12810 = 100000002. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.
Remove ads
Пример программного преобразования
Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, WAV файл), может оказаться необходимым преобразовать байты. Если данные хранятся в 8 битах, необходимо, чтобы значения 128-255 были отрицательными.
C# .NET / C style
byte b1 = 254; //11111110 (бинарное)
byte b2 = 121; //01111001 (бинарное)
byte c = 1<<(sizeof(byte)*8-1); //2 возводится в степень 7. Результат: 10000000 (бинарное)
byte b1Conversion=(c ^ b1) - c; //Результат: -2. А фактически, двоичный дополнительный код.
byte b2Conversion=(c ^ b2) - c; //Результат остаётся 121, потому что знаковый разряд - ноль.
Remove ads
Расширение знака
Расширение знака (англ. sign extension[en]) — операция над двоичным числом, которая позволяет увеличить разрядность числа с сохранением знака и значения. Выполняется добавлением цифр со стороны старшего значащего разряда. Если число положительное (старший разряд равен 0), то добавляются нули, если отрицательное (старший разряд равен 1) — единицы.
Пример
Примечание: Добавленные цифры подчёркнуты
См. также
- Обратный код
- Прямой код
- Целый тип
- Алгоритм Бута — специализированный алгоритм умножения для чисел в дополнительном коде
Литература
- Behrooz Parhami. 2.3. Complement Representation, 2.4. Two's- and 1's-complement numbers // Computer Arithmetic: Algorithms and Hardware Designs. — New York: Oxford University Press, 2000. — P. 22-27. — 510 p. — ISBN 0-19-512583-5.
- Самофалов К.Г., Романкевич А.М., Валуйский В.Н., Каневский Ю.С., Пиневич М.М. Прикладная теория цифровых автоматов. — Киев: Вища школа, 1987. — 375 с.
Remove ads
Примечания
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads