Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Кодирование отрицательных чисел в двоичных системах счисления
Encoding of negative numbers in binary number systems
В вычислительной технике требуются представления чисел со знаком для кодирования отрицательных чисел в двоичных системах счисления. В математике отрицательные числа в любой системе счисления представляются с помощью префикса знака минус ("−"). Однако в оперативной памяти или регистрах процессора числа представляются только как последовательности битов, без дополнительных символов. Четыре наиболее известных метода расширения двоичной системы счисления для представления чисел со знаком: знак-величина, дополнительный код единицы, дополнительный код двойки и сдвинутый двоичный код. Некоторые альтернативные методы используют неявные, а не явные знаки, например, отрицачная двоичная система, использующая основание −2. Соответствующие методы могут быть разработаны для других систем счисления, будь то положительные, отрицательные, дробные или другие вариации на эту тему. Не существует однозначного критерия, по которому какое-либо из представлений было бы универсально превосходящим. Для целых чисел представление, используемое в большинстве современных вычислительных устройств, – это дополнительный код двойки, хотя мейнфреймы серии Unisys ClearPath Dorado используют дополнительный код единицы.
In computing, signed number representations are required to encode negative numbers in binary number systems. In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU registers, numbers are represented only as sequences of bits, without extra symbols. The four best known methods of extending the binary numeral system to represent signed numbers are: sign–magnitude, ones' complement, two's complement, and offset binary. Some of the alternative methods use implicit instead of explicit signs, such as negative binary, using the base −2. Corresponding methods can be devised for other bases, whether positive, negative, fractional, or other elaborations on such themes. There is no definitive criterion by which any of the representations is universally superior. For integers, the representation used in most current computing devices is two's complement, although the Unisys ClearPath Dorado series mainframes use ones' complement.
История
Ранние дни цифровых вычислений характеризовались соперничеством идей в отношении как аппаратных технологий, так и математических технологий (систем счисления). Одним из главных вопросов был формат представления отрицательных чисел, по которому ведущие эксперты того времени высказывали очень сильные и различные мнения. Одна группа поддерживала систему дополнительного кода (дополнение до двух), которая доминирует и сегодня. Другая группа поддерживала систему дополнительного кода "один", где отрицательное значение формируется путем инвертирования всех битов его положительного эквивалента. Третья группа поддерживала представление "знак-величина", где значение меняется с положительного на отрицательное простым переключением старшего бита слова. Существовали аргументы за и против каждой из этих систем. Представление "знак-величина" облегчало трассировку дампов памяти (распространенный процесс в 1960-х годах), поскольку небольшие числовые значения использовали меньше единичных битов. Эти системы выполняли арифметику в дополнительном коде "один", поэтому числа должны были преобразовываться в значения дополнительного кода "один" при передаче из регистра в арифметическое устройство, а затем обратно в представление "знак-величина" при передаче результата обратно в регистр. Для реализации такой электроники требовалось больше логических элементов, чем для других систем – что было критичным фактором, учитывая стоимость и компоновку дискретных транзисторов. IBM была одним из первых сторонников представления "знак-величина", и их компьютеры серий 704, 709 и 709x, пожалуй, наиболее известны как системы, использующие его. Дополнительный код "один" позволял создавать несколько более простые аппаратные конструкции, поскольку не требовалось преобразования значений при передаче в арифметическое устройство и из него. Однако он также разделял нежелательную характеристику с представлением "знак-величина": возможность представления отрицательного нуля (−0). Отрицательный ноль ведет себя точно так же, как положительный ноль: при использовании в качестве операнда в любом вычислении результат будет одинаковым, независимо от того, является ли операнд положительным или отрицательным нулем. Недостатком является то, что наличие двух форм одного и того же значения требует двух сравнений при проверке на равенство с нулем. Вычитание в дополнительном коде "один" также может привести к заимствованию с переносом (описано ниже). Можно утверждать, что это усложняет логику сложения и вычитания, или, наоборот, упрощает ее, поскольку вычитание требует лишь инвертирования битов второго операнда при передаче его в сумматор. Компьютеры PDP 1, серии CDC 160, серии CDC 3000, серии CDC 6000, серии UNIVAC 1100 и LINC использовали представление в дополнительном коде "один". Дополнительный код (дополнение до двух) является самым простым в реализации на аппаратном уровне, что, возможно, и является главной причиной его широкой популярности. Процессоры ранних мейнфреймов часто состояли из тысяч транзисторов, поэтому устранение значительного их числа давало существенную экономию средств. Мейнфреймы, такие как IBM System/360, серия GE 600, PDP 6 и PDP 10, использовали дополнительный код, как и миникомпьютеры, такие как PDP 5 и PDP 8, PDP 11 и машины VAX. Архитекторы первых процессоров на основе интегральных схем (Intel 8080 и т. д.) также выбрали арифметику в дополнительном коде. С развитием технологии интегральных схем дополнительный код был принят практически во всех процессорах, включая x86, m68k, Power ISA, MIPS, SPARC, ARM, Itanium, PA RISC и DEC Alpha.
The early days of digital computing were marked by competing ideas about both hardware technology and mathematics technology (numbering systems). One of the great debates was the format of negative numbers, with some of the era's top experts expressing very strong and differing opinions. One camp supported two's complement, the system that is dominant today. Another camp supported ones' complement, where a negative value is formed by inverting all of the bits in its positive equivalent. A third group supported sign–magnitude, where a value is changed from positive to negative simply by toggling the word's highest order bit. There were arguments for and against each of the systems. Sign–magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 bits. These systems did ones' complement math internally, so numbers would have to be converted to ones' complement values when they were transmitted from a register to the math unit and then converted back to sign–magnitude when the result was transmitted back to the register. The electronics required more gates than the other systemsa key concern when the cost and packaging of discrete transistors were critical. IBM was one of the early supporters of sign–magnitude, with their 704, 709 and 709x series computers being perhaps the best known systems to use it. Ones' complement allowed for somewhat simpler hardware designs, as there was no need to convert values when passed to and from the math unit. But it also shared an undesirable characteristic with sign–magnitude: the ability to represent negative zero (−0). Negative zero behaves exactly like positive zero: when used as an operand in any calculation, the result will be the same whether an operand is positive or negative zero. The disadvantage is that the existence of two forms of the same value necessitates two comparisons when checking for equality with zero. Ones' complement subtraction can also result in an end around borrow (described below). It can be argued that this makes the addition and subtraction logic more complicated or that it makes it simpler, as a subtraction requires simply inverting the bits of the second operand as it is passed to the adder. The PDP 1, CDC 160 series, CDC 3000 series, CDC 6000 series, UNIVAC 1100 series, and LINC computer use ones' complement representation. Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity. Processors on the early mainframes often consisted of thousands of transistors, so eliminating a significant number of transistors was a significant cost savings. Mainframes such as the IBM System/360, the GE 600 series, and the PDP 6 and PDP 10 use two's complement, as did minicomputers such as the PDP 5 and PDP 8 and the PDP 11 and VAX machines. The architects of the early integrated circuit based CPUs (Intel 8080, etc.) also chose to use two's complement math. As IC technology advanced, two's complement technology was adopted in virtually all processors, including x86, m68k, Power ISA, MIPS, SPARC, ARM, Itanium, PA RISC, and DEC Alpha.
Другие системы
Протокол Google Buffers "зигзагообразное кодирование" – это система, аналогичная кодированию со знаком и величиной (sign-magnitude), но использующая младший значащий бит для представления знака и имеющая единственное представление нуля. Это позволяет эффективно использовать кодирование чисел переменной длины, предназначенное для неотрицательных (беззнаковых) целых чисел, для представления знаковых целых чисел. Аналогичный метод применяется в стандартах сжатия видео Advanced Video Coding/H.264 и High Efficiency Video Coding/H.265 для расширения экспоненциального кодирования Голомба на отрицательные числа. В этом расширении младший значащий бит почти является битом знака; ноль имеет такой же младший значащий бит (0), как и все отрицательные числа. Этот выбор приводит к тому, что наибольшее по модулю положительное число, которое можно представить, на единицу больше, чем наибольшее по модулю отрицательное число, в отличие от дополнительного кода или зигзагообразного кодирования протокола буферов. Другой подход заключается в присвоении знака каждой цифре, что приводит к представлению чисел со знаком. Например, в 1726 году Джон Колсон выступал за приведение выражений к "малым числам" – цифрам 1, 2, 3, 4 и 5. В 1840 году Огюстен Коши также выразил предпочтение таким модифицированным десятичным числам для уменьшения ошибок при вычислениях.
Google's Protocol Buffers "zig zag encoding" is a system similar to sign–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. A similar method is used in the Advanced Video Coding/H.264 and High Efficiency Video Coding/H.265 video compression standards to extend exponential Golomb coding to negative numbers. In that extension, the least significant bit is almost a sign bit; zero has the same least significant bit (0) as all the negative numbers. This choice results in the largest magnitude representable positive number being one higher than the largest magnitude negative number, unlike in two's complement or the Protocol Buffers zig zag encoding. 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.