Знаковые представления чисел

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Представления подписанных чисел»  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2013 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

В вычислениях , прямой код необходимо закодировать отрицательные числа в системах двойных чисел.

В математике отрицательные числа в любом основании обозначаются префиксом со знаком минус ("-"). Однако в компьютерном оборудовании числа представлены только как последовательности битов без дополнительных символов. Четыре наиболее известные способами расширения двоичной системы счисления для представления чисел со знаком, являются: знак-и магнитуды , обратный кода , дополнение до двух , и смещение двоичных . Некоторые из альтернативных методов используют неявные знаки вместо явных, такие как отрицательный двоичный код, с использованием основания -2 . Соответствующие методы могут быть разработаны для других баз., будь то положительные, отрицательные, частичные или другие разработки по таким темам.

Не существует окончательного критерия, по которому любое из представлений является универсально превосходящим. Для целых чисел представление, используемое в большинстве современных вычислительных устройств, является дополнением до двух, хотя в мэйнфреймах серии Unisys ClearPath Dorado используется дополнение до единиц.

История [ править ]

Первые дни цифровых вычислений были отмечены множеством конкурирующих идей как в отношении аппаратных технологий, так и математических технологий (систем счисления). Одним из самых больших споров был формат отрицательных чисел, некоторые из ведущих экспертов эпохи имели очень сильные и разные мнения. ^{[ необходима цитата ]} Один лагерь поддерживал два дополнения , систему, которая сегодня доминирует. Другой лагерь поддерживал дополнение, где любое положительное значение превращается в его отрицательный эквивалент путем инвертирования всех битов в слове. Третья группа поддерживает «знак и величину» (знак-величина), где значение изменяется с положительного на отрицательное просто путем переключения бита знака (старшего разряда) слова.

Были аргументы за и против каждой из систем. Знак и величина позволили упростить отслеживание дампов памяти (распространенный процесс в 1960-х годах), поскольку для небольших числовых значений используется меньше 1 бит. Внутри этих систем выполнялась математика с дополнением единиц, поэтому числа должны были быть преобразованы в значения дополнения единиц, когда они были переданы из регистра в математический блок, а затем преобразованы обратно в знаковую величину, когда результат был передан обратно в регистр. Электронике требовалось больше вентилей, чем другим системам, что было ключевой проблемой, когда стоимость и упаковка дискретных транзисторов были критическими. IBM была одним из первых сторонников знаковой величины, и их компьютеры серий 704 , 709 и 709x были, пожалуй, самыми известными системами, в которых она использовалась.

Их дополнение позволило несколько упростить конструкцию оборудования, поскольку не было необходимости преобразовывать значения при передаче в математический блок и из него. Но у него также есть нежелательная характеристика со знаком-величиной - способность представлять отрицательный ноль (-0). Отрицательный ноль ведет себя точно так же, как положительный ноль; при использовании в качестве операнда в любом вычислении результат будет одинаковым независимо от того, является ли операнд положительным или отрицательным нулем. Однако недостатком является то, что наличие двух форм одного и того же значения требует двух, а не одного сравнения при проверке равенства нулю. Вычитание дополнительных элементов также может привести к заимствованию на конец периода.(описано ниже). Можно утверждать, что это усложняет логику сложения / вычитания или упрощает ее, поскольку вычитание требует простого инвертирования битов второго операнда при его передаче в сумматор. PDP-1 , CDC 160 серии , CDC 3000 серии, CDC серии 6000 , UNIVAC 1100 серии, а также ЛИНК дополнение представление компьютера использовать поразрядное.

Дополнение до двух проще всего реализовать на оборудовании, что может быть основной причиной его широкой популярности. ^[1] Процессоры на ранних мэйнфреймах часто состояли из тысяч транзисторов - устранение значительного количества транзисторов было значительной экономией. Мэйнфреймы , такие как IBM System / 360 , в серии GE-600 , ^[2] и PDP-6 и PDP-10 использовать два с дополнением, как и миникомпьютеры , такие , как PDP-5 и PDP-8 и PDP-11 и VAX . Архитекторы первых процессоров на базе интегральных схем ( Intel 8080и т. д.) решили использовать математику с дополнением до двух. По мере развития технологии ИС практически все использовали технологию дополнения до двух. Процессоры x86 , ^[3] m68k , Power ISA , ^[4] MIPS , SPARC , ARM , Itanium , PA-RISC и DEC Alpha дополняют друг друга.

Знаковое представление величины [ править ]

Это представление также называется представлением «знак-величина» или «знак и величина». В этом подходе знак числа представлен битом знака : установка этого бита (часто самого старшего бита ) на 0 для положительного числа или положительного нуля и установка на 1 для отрицательного числа или отрицательного нуля. Остальные биты числа указывают величину (или абсолютное значение ). Например, в восьмибитном байте только семь битов представляют величину, которая может находиться в диапазоне от 0000000 (0) до 1111111 (127). Таким образом, числа в диапазоне от -127 ₁₀ до +127 ₁₀ могут быть представлены после добавления знакового бита (восьмого бита). Например, −43 ₁₀в восьмибитном байте кодируется как 1 0101011, а 43 ₁₀ - 0 0101011. Использование представления величины со знаком имеет несколько последствий, что усложняет их реализацию: ^[5]

1. Есть два способа представить ноль: 00000000 (0) и 10000000 ( -0 ).
2. Сложение и вычитание требуют разного поведения в зависимости от знакового бита, в то время как одно дополнение может игнорировать знаковый бит и просто выполнять сквозной перенос, а два дополнения могут игнорировать знаковый бит и зависеть от поведения переполнения.
3. Сравнение также требует проверки знакового бита, тогда как в дополнении до двух можно просто вычесть два числа и проверить, является ли результат положительным или отрицательным.
4. Минимальное отрицательное число -127 вместо -128 в случае дополнения до двух.

Этот подход напрямую сопоставим с обычным способом показа знака (размещение «+» или «-» рядом с величиной числа). Некоторые ранние бинарные компьютеры (например, IBM 7090 ) использовали это представление, возможно, из-за его естественного отношения к обычному использованию. Величина со знаком - это наиболее распространенный способ представления мантиссы в значениях с плавающей запятой .

Дополнение [ править ]

В качестве альтернативы для представления отрицательных чисел можно использовать систему, известную как дополнение до единиц ^[6] . Форма дополнения до единиц отрицательного двоичного числа - это побитовое НЕ, применяемое к нему, то есть «дополнение» его положительного аналога. Как и представление знака и величины, дополнение до единиц имеет два представления 0: 00000000 (+0) и 11111111 ( -0 ). ^[7]

Например, форма дополнения единиц 00101011 (43 ₁₀ ) становится 11010100 (-43 ₁₀ ). Диапазон подписанных чисел , используя обратный код представлен - (2 ^{Н -1} - 1) к (2 ^{N -1} - 1) и ± 0. Обычный восьмиразрядный байт - это от −127 ₁₀ до +127 _10, где ноль равен либо 00000000 (+0), либо 11111111 (−0).

Чтобы сложить два числа, представленных в этой системе, выполняется обычное двоичное сложение, но затем необходимо выполнить сквозной перенос : то есть добавить любой результирующий перенос обратно в полученную сумму. ^[8] Чтобы понять, почему это необходимо, рассмотрим следующий пример, показывающий случай добавления −1 (11111110) к +2 (00000010):

 двоичный десятичный 11111110 -1+ 00000010 +2──────────── ── 1 00000000 0 ← Не правильный ответ 1 +1 ← Добавить перенос──────────── ── 00000001 1 ← Правильный ответ

В предыдущем примере первое двоичное сложение дает 00000000, что неверно. Правильный результат (00000001) появляется только при добавлении переноса.

Замечание по терминологии: Система называется «дополнением , поскольку того , » отрицание положительного значения х (представлено в виде побитового НЕ из й ) также может быть образованно путем вычитания х из один комплемента представления нуля , что является длинная последовательность единиц (−0). С другой стороны, арифметика с дополнением до двух формирует отрицание x путем вычитания x из одной большой степени двойки, которая конгруэнтна +0. ^[9] Следовательно, представление одного и того же отрицательного значения в виде дополнения до единицы и дополнения до двух будет отличаться на единицу.

Note that the ones' complement representation of a negative number can be obtained from the sign-magnitude representation merely by bitwise complementing the magnitude (inverting all the bits after the first). For example, the decimal number −125 with its sign-magnitude representation 11111101 can be represented in ones' complement form as 10000010.

Two's complement[edit]

The problems of multiple representations of 0 and the need for the end-around carry are circumvented by a system called two's complement. In two's complement, negative numbers are represented by the bit pattern which is one greater (in an unsigned sense) than the ones' complement of the positive value.

In two's-complement, there is only one zero, represented as 00000000. Negating a number (whether negative or positive) is done by inverting all the bits and then adding one to that result.^[10] This actually reflects the ring structure on all integers modulo 2N: ${\displaystyle \mathbb {Z} /2^{N}\mathbb {Z} }$. Addition of a pair of two's-complement integers is the same as addition of a pair of unsigned numbers (except for detection of overflow, if that is done); the same is true for subtraction and even for N lowest significant bits of a product (value of multiplication). For instance, a two's-complement addition of 127 and −128 gives the same binary bit pattern as an unsigned addition of 127 and 128, as can be seen from the 8-bit two's complement table.

An easier method to get the negation of a number in two's complement is as follows:

Method two:

1. Invert all the bits through the number
2. Add one

Example: for +2, which is 00000010 in binary (the ~ character is the C bitwise NOT operator, so ~X means "invert all the bits in X"):

1. ~00000010 → 11111101
2. 11111101 + 1 → 11111110 (−2 in two's complement)

Offset binary[edit]

Offset binary, also called excess-K or biased representation, uses a pre-specified number K as a biasing value. A value is represented by the unsigned number which is K greater than the intended value. Thus 0 is represented by K, and −K is represented by the all-zeros bit pattern. This can be seen as a slight modification and generalization of the aforementioned two's-complement, which is virtually the excess-(2^N−1) representation with negated most significant bit.

Biased representations are now primarily used for the exponent of floating-point numbers. The IEEE 754 floating-point standard defines the exponent field of a single-precision (32-bit) number as an 8-bit excess-127 field. The double-precision (64-bit) exponent field is an 11-bit excess-1023 field; see exponent bias. It also had use for binary-coded decimal numbers as excess-3.

Base −2[edit]

In conventional binary number systems, the base, or radix, is 2; thus the rightmost bit represents 2⁰, the next bit represents 2¹, the next bit 2², and so on. However, a binary number system with base −2 is also possible. The rightmost bit represents (−2)⁰ = +1, the next bit represents (−2)¹ = −2, the next bit (−2)² = +4 and so on, with alternating sign. The numbers that can be represented with four bits are shown in the comparison table below.

The range of numbers that can be represented is asymmetric. If the word has an even number of bits, the magnitude of the largest negative number that can be represented is twice as large as the largest positive number that can be represented, and vice versa if the word has an odd number of bits.

Comparison table[edit]

The following table shows the positive and negative integers that can be represented using four bits.

Same table, as viewed from "given these binary bits, what is the number as interpreted by the representation system":

Other systems[edit]

Google's Protocol Buffers "zig-zag encoding" is a system similar to sign-and-magnitude, but uses the least significant bit to represent the sign and has a single representation of zero. This allows a variable-length quantity encoding intended for nonnegative (unsigned) integers to be used efficiently for signed integers.^[11]

Another approach is to give each digit a sign, yielding the signed-digit representation. For instance, in 1726, John Colson advocated reducing expressions to "small numbers", numerals 1, 2, 3, 4, and 5. In 1840, Augustin Cauchy also expressed preference for such modified decimal numbers to reduce errors in computation.

See also[edit]

• Balanced ternary
• Binary-coded decimal
• Computer number format
• Method of complements
• Signedness

References[edit]

• Ivan Flores, The Logic of Computer Arithmetic, Prentice-Hall (1963)
• Israel Koren, Computer Arithmetic Algorithms, A.K. Peters (2002), ISBN 1-56881-160-8