Двоичное представление положительных целых чисел

Целые числа в компьютере обычно кодируются в двоичном коде, то есть в двоичной системе счисления. Например, число 5 можно представить в виде . Показатель системы счисления принято записывать справа снизу около числа.

Аналогично, , , , , , и так далее. Всё очень похоже на обозначение чисел в десятичной системе счисления: . Но только в качестве основания системы счисления используется число . У чисел, записанных в десятичной системе счисления, индекс 10 обычно не пишется, но его можно писать. Так что , , и так далее.

В двоичной арифметике всего две цифры, 0 и 1. Двоичный код положительного целого числа – это коэффициенты разложения числа по степеням двойки.

Умножение числа на двоичное десять, то есть на , приводит к дописыванию справа нуля в двоичном представлении числа. Умножение на двоичное сто, то есть на - дописыванию двух нулей. И так далее.

Целочисленное деление на с отбрасыванием остатка производится путём отбрасывания последнего (младшего) бита, деление на - отбрасывания двух последних бит, и так далее.

Обычно такие операции называют побитовыми сдвигами на n бит влево (умножение на ) или вправо (целочисленное деление на ).

Сложение двоичных чисел можно производить “в столбик” по полной аналогии со сложением десятичных чисел. Единственное отличие – то, что в двоичной арифметике только две цифры, 0и1, а не десять цифр (от 0 до 9) как в десятичной. Поэтому если в десятичной арифметике единицу более старшего разряда даёт, к примеру, сложение 1 и 9, то в двоичной арифметике её даст сложение 1 и 1. То есть

(в десятичной системе это равенство выглядит как 1+1=2). Аналогично, , и так далее.

Примеры сложения “в столбик”:

Совершенно аналогично выполняется умножение:

В машинной реализации целочисленного умножения используют побитовые сдвиги влево и сложения. Поскольку эти алгоритмы очень просты, они реализуются аппаратно.

Двоичное представление отрицательных целых чисел. Дополнительный код

Старший бит в целых без знака имеет обычный смысл, в целых со знаком – для положительных чисел всегда равен 0. В отрицательных числах старший бит всегда равен 1. В примерах для простоты мы будем рассматривать четырехбитную арифметику. Тогда в качестве примера целого положительного числа можно привести 0110₂.

Для хранения отрицательных чисел используется дополнительный код. Число (– n), где n положительно, переводится в число n2=-n по следующему алгоритму:

• этап 1: сначала число n преобразуется в число n1 путём преобразования , во время которого все единицы числа n заменяются нулями, а нули единицами, то есть ;

• этап 2: перевод , то есть к получившемуся числу n1 добавляется единица младшего разряда.

Надо отметить, что дополнительный код отрицательных чисел зависит от разрядности. Например, код числа (–1) в четырёхразрядной арифметике будет , а в 8-разрядной арифметике будет . Коды числа (–2) будут и , и так далее.

Для того, чтобы понять причину использования дополнительного кода, рассмотрим сложение чисел, представленных в дополнительном коде.

Сложение положительного и отрицательного чисел

Рассмотрим, чему равна сумма числа 1 и числа –1, представленного в дополнительном коде. Сначала переведём в дополнительный код число –1. При этом n=1₁₀, n₂= –1_10.

Этап1: n=1₁₀=0001₂ n1=1110₂;

Этап2: n2=1110₂+1=1111₂;

Таким образом, в четырёхбитном представлении –1₁₀=1111₂.

Проверка:

n2+n=10000₂. Получившийся пятый разряд, выходящий за пределы четырехбитной ячейки, отбрасывается, поэтому в рамках четырехбитной арифметики получается n2+n=0000₂=0.

Аналогично

n=2₁₀=0010₂ n1=1101₂; n2=1110₂;

n=3₁₀=0011₂ n1=1100₂; n2=1101₂;

n=4₁₀=0100₂ n1=1011₂; n2=1100₂;

Очевидно, во всех этих случаях n2+n=0.

Что будет, если мы сложим 3₁₀ и –2₁₀ (равное 1110₂, как мы уже знаем)?

После отбрасывания старшего бита, выходящего за пределы нашей четырёхбитовой ячейки, получаем 0011₂ + 1110₂=0001₂, то есть 3₁₀ + (–2₁₀)=1₁₀, как и должно быть.

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

из-за отбрасывания лишнего старшего бита, выходящего за пределы ячейки. Поэтому .

Вычитание положительных чисел осуществляется путём сложения положительного числа с отрицательным, получившимся из вычитаемого в результате его перевода в дополнительный код.

Приведенные примеры иллюстрируют тот факт, что сложение положительного числа с отрицательным, хранящимся в дополнительном коде, или двух отрицательных, может происходить аппаратно (что значит очень эффективно) на основе крайне простых электронных устройств.