Как составить дополнительный код числа

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 31 января 2021 года; проверки требуют 29 правок.

Дополнительный код (англ. “two’s complement”, иногда “twos-complement”) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. В англоязычной литературе «обратный код» называют «дополнением единиц» (англ. “ones’ complement”), а «дополнительный код» называют «дополнением двойки» (англ. “two’s complement”).

Дополнительный код для отрицательного числа можно получить инвертированием его двоичного модуля и прибавлением к инверсии единицы, либо вычитанием числа из нуля.
Дополнительный код двоичного числа определяется как величина, полученная вычитанием числа из наибольшей степени двух (из 2^N для N-битного второго дополнения).

Представление отрицательного числа в дополнительном коде[править | править код]

При записи числа в дополнительном коде старший разряд является знаковым. Если значение старшего разряда равно 0, то это значит, что в остальных разрядах записано положительное двоичное число, совпадающее с прямым кодом.

Двоичное 8-разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах, равно .

Примеры:

Дополнительный код в иной системе счисления[править | править код]

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

Преобразования на примере десятичной системы счисления^[1][править | править код]

Положительное число[править | править код]

Изменение значений текущих разрядов числа не производится, но дописывается знаковый старший разряд, значение которого равно 0. Например число [+12’345] будет иметь следующее представление – [012’345]

Отрицательное число[править | править код]

Дописываем знаковый старший разряд, равный большей цифре данной системы счисления, в нашем случае – это 9, а также изменяем остальные разряды по определённому правилу; пусть значение цифры каждого разряда будет представлено переменной x , кроме знакового, тогда представим следующий алгоритм действий:

1. Присвоим переменной x новое значение, равное выражению 9 – x (процесс получения обратного кода) – например отрицательное число [-12345] в прямом коде от старшего к младшему разряду будет иметь вид [9′12345], где 9 – знаковая цифра, а в обратном представлении кода будет иметь следующий вид – [9’87654].
2. К результирующему числу прибавим 1, так число [9’87654] (первое дополнение) будет иметь вид [987’655] (доп. код).
3. Если возникла ситуация переноса разряда, в результате которого образовался новый разряд, то его (старший разряд) опускаем, а результирующее число считаем положительным. Результирующее положительное число будет одинаково представлено, как в прямом, так и в дополнительном коде. Например, имея возможность представить в таком виде отрицательный и положительный нуль, разберём их перевод в дополнительный код (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] → (второе дополнение или обычное представление) [0’1312]. При переводе из дополнительного кода в обычное представление результирующее значение является абсолютным.

Преобразование в дополнительный код[править | править код]

Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.

1. Если старший (знаковый) разряд числа, записанного в прямом коде, равен 0, то число положительное и никаких преобразований не делается;
2. Если старший (знаковый) разряд числа, записанного в прямом коде, равен 1, то число отрицательное, все разряды числа, кроме знакового, инвертируются, а к результату прибавляется 1.

Пример.
Преобразуем отрицательное число −5, записанное в прямом коде, в дополнительный код.
Прямой код отрицательного числа -5:

1000 0101 

Инвертируем все разряды числа, кроме знакового, получая таким образом обратный код (первое дополнение) отрицательного числа -5:

1111 1010

Добавим к результату 1, получая таким образом дополнительный код (второе дополнение) отрицательного числа -5:

1111 1011

Для преобразования отрицательного числа -5, записанного в дополнительном коде, в положительное число 5, записанное в прямом коде, используется похожий алгоритм. А именно:

1111 1011

Инвертируем все разряды отрицательного числа -5, получая таким образом положительное число 4 в прямом коде:

0000 0100

Добавив к результату 1 получим положительное число 5 в прямом коде:

0101

И проверим, сложив с дополнительным кодом

 0000 0101 + 1111 1011 = 0000 0000, пятый и старше разряды выбрасываются.

p-адические числа[править | править код]

В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ичная система счисления, то число, противоположное 0001₅ (1₁₀), равно 4444₅ (−1₁₀).

Реализация алгоритма преобразования в дополнительный код (для 8-битных чисел)[править | править код]

Pascal[править | править код]

  if (a < 0) then
    a := ((not a) or 128) + 1;

C/C++[править | править код]

int convert(int a) {
    if (a<0)
        a = ~(-a) + 1;
  return a;
}

Преимущества и недостатки[править | править код]

Преимущества[править | править код]

• Общие инструкции (процессора) для сложения, вычитания и левого сдвига для знаковых и беззнаковых чисел (различия только в арифметических флагах, которые нужно проверять для контроля переполнения в результате).
• Отсутствие числа «минус ноль».

Недостатки[править | править код]

• Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
• В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно.
• Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 127₁₀ = 01111111₂, минимальное число: -128₁₀ = 10000000₂. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

Пример программного преобразования[править | править код]

Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, файл WAVE), может оказаться необходимым преобразовать байты. Если данные хранятся в 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, потому что знаковый разряд - ноль.

Расширение знака[править | править код]

Расширение знака (англ. Sign extension) — операция над двоичным числом, которая позволяет увеличить разрядность числа с сохранением знака и значения. Выполняется добавлением цифр со стороны старшего значащего разряда. Если число положительное (старший разряд равен 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 с.

Ссылки[править | править код]

1. ↑ Florida Tech. Дата обращения: 28 ноября 2020. Архивировано 8 октября 2016 года.

Двоичное число: прямой, обратный и дополнительный коды

Прямой код двоичного числа
Обратный код двоичного числа
Дополнительный код двоичного числа

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

Мы знаем, что десятичное число можно представить в двоичном виде. К примеру, десятичное число 100 в двоичном виде будет равно 1100100, или в восьмибитном представлении 0110 0100. А как представить отрицательное десятичное число в двоичном виде и произвести с ним арифметические операции? Для этого и предназначены разные способы представления чисел в двоичном коде.
Сразу отмечу, что положительные числа в двоичном коде вне зависимости от способа представления (прямой, обратный или дополнительный коды) имеют одинаковый вид.

Прямой код

Прямой код – способ представления двоичных чисел с фиксированной запятой. Главным образом используется для записи неотрицательных чисел

Прямой код используется в двух вариантах.
В первом (основной) – для записи только неотрицательных чисел:

В этом варианте (для восьмибитного двоичного числа) мы можем записать максимальное число 255 (всего чисел 256 – от 0 до 255)

Второй вариант – для записи как положительных, так и отрицательных чисел.
В этом случае старший бит (в нашем случае – восьмой) объявляется знаковым разрядом (знаковым битом).
При этом, если:
– знаковый разряд равен 0, то число положительное
– знаковый разряд равен 1, то число отрицательное

В этом случае диапазон десятичных чисел, которые можно записать в прямом коде составляет от – 127 до +127:

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

Обратный код

Обратный код – метод вычислительной математики, позволяющий вычесть одно число из другого, используя только операцию сложения.
Обратный двоичный код положительного числа состоит из одноразрядного кода знака (битового знака) – двоичной цифры 0, за которым следует значение числа.
Обратный двоичный код отрицательного числа состоит из одноразрядного кода знака (битового знака) – двоичной цифры 1, за которым следует инвертированное значение положительного числа.

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

При 8-битном двоичном числе – знаковый бит (как и в прямом коде) старший (8-й)

Диапазон десятичных чисел, который можно записать в обратном коде от -127 до + 127

Арифметические операции с отрицательными числами в обратном коде:

(Арифметические операции с двоичными числами)

1-й пример (для положительного результата)
Дано два числа:
100 = 0110 0100
-25 = – 0001 1001
Необходимо их сложить:
100 + (-25) = 100 – 25 = 75

1-й этап
Переводим число -25 в двоичное число в обратном коде:
25 = 0001 1001
-25= 1110 0110
и складываем два числа:
0110 0100 (100) + 1110 0110 (-25) = 1 0100 1010, отбрасываем старшую 1 (у нас получился лишний 9-й разряд – переполнение), = 0100 1010
2-й этап
Отброшенную в результате старшую единицу прибавляем к результату:
0100 1010 + 1 = 0100 1011 (знаковый бит =0, значит число положительное), что равно 75 в десятичной системе

2-й пример (для отрицательного результата)
Дано два числа:
5 = 0000 0101
-10 = – 0000 1010
Необходимо их сложить:
5 + (-10) = 5 – 10 = -5

1-й этап
Переводим число -10 в двоичное число в обратном коде:
10 = 0000 1010
-10= 1111 0101
и складываем два числа:
0000 0101 (5) + 1111 0101 (-10) = 1111 1010 (знаковый бит =1, значит число отрицательное)

2-й этап
Раз результат получился отрицательный, значит число представлено в обратном коде.
Переводим результат в прямой код (путем инвертирования значения, знаковый бит не трогаем):
1111 1010 —-> 1000 0101
Проверяем:
1000 0101 = – 0000 0101 = -5

Обратный код решает проблему сложения и вычитания чисел с различными знаками, но и имеет свои недостатки:
– арифметические операции проводятся в два этапа
– как и в прямом коде два представления нуля – положительный и отрицательный

Дополнительный код

Дополнительный код – наиболее распространенный способ представления отрицательных чисел. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел.

В дополнительном коде (как и в прямом и обратном) старший разряд отводится для представления знака числа (знаковый бит).

Диапазон десятичных чисел которые можно записать в дополнительном коде от -128 до +127. Запись положительных двоичных чисел в дополнительном коде та-же, что и в прямом и обратном кодах.

Дополнительный код отрицательного числа можно получить двумя способами
1-й способ:
– инвертируем значение отрицательного числа, записанного в прямом коде (знаковый бит не трогаем)
– к полученной инверсии прибавляем 1
Пример:
Дано десятичное число -10
Переводим в прямой код:
10 = 0000 1010 —-> -10 = 1000 1010
Инвертируем значение (получаем обратный код):
1000 1010 —-> 1111 0101
К полученной инверсии прибавляем 1:
1111 0101 + 1 = 1111 0110 – десятичное число -10 в дополнительном коде

2-й способ:
Вычитание числа из нуля
Дано десятичное число 10, необходимо получить отрицательное число (-10) в дополнительном двоичном коде
Переводим 10 в двоичное число:
10 = 0000 1010
Вычитаем из нуля:
0 – 0000 1010 = 1111 0110 – десятичное число -10 в дополнительном коде

Арифметические операции с отрицательными числами в дополнительном коде

Дано: необходимо сложить два числа -10 и 5
-10 + 5 = -5
Решение:
5 = 0000 0101
-10 = 1111 0110 (в дополнительном коде)
Складываем:
1111 0110 + 0000 0101 = 1111 1011, что соответствует числу -5 в дополнительном коде

Как мы видим на этом примере – дополнительный код отрицательного двоичного числа наиболее подходит для выполнения арифметических операций сложения и вычитания отрицательных чисел.

Вывод:
1. Для арифметических операций сложения и вычитания положительных двоичных чисел наиболее подходит применение прямого кода
2. Для арифметических операций сложения и вычитания отрицательных двоичных чисел наиболее подходит применение дополнительного кода

Предыдущие статьи:
1. Микроконтроллеры – первый шаг
2. Системы счисления: десятичная, двоичная и шестнадцатиричная
3. Логические операции, логические выражения, логические элементы
4. Битовые операции

(39 голосов, оценка: 4,69 из 5)

Загрузка…

Машинные коды[править]

Все операции в ЭВМ выполняются над числами, представленными специальными машинными кодами. Их использование позволяет обрабатывать знаковые разряды чисел так же, как и значащие разряды, а также заменять операцию вычитания операцией сложения.

Различают следующие коды двоичных чисел:

• прямой код (П),
• обратный код (ОК),
• дополнительный код (ДК).

Прямой код[править]

Прямой код двоичного числа образуется из абсолютного значения этого числа и кода знака (0 или 1) перед его старшим числовым разрядом.

Пример.

А₁₀ = +10; А₂ = +1010; [А₂]_п = 0|1010

В₁₀ = –15; В₂ = –1111; [В₂]_п = 1|1111

Обратный код[править]

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

Пример.

А₁₀ = +10; А₂ = +1010; [А₂]ок = [А₂]п = 0|1010

В₁₀ = –15; В₂ = –1111; [В₂]ок = 1|0000

Свое название обратный код получил потому, что коды цифр отрицательного числа заменены на инверсные. Наиболее важные свойства обратного кода чисел:

• сложение положительного числа С с его отрицательным значением в обратном коде дает т.н. машинную единицу МЕок=1|11…11, состоящую из единиц в знаковом и в значащих разрядах числа;
• нуль в обратном коде имеет двоякое значение. Он может быть как положительным числом – 0|00…00, так и отрицательным 1|11…11. Значение отрицательного числа совпадает с МЕок. Двойственное представление 0 явилось причиной того, что в современных ЭВМ все числа представляются не обратным, а дополнительным кодом.

Дополнительный код[править]

Дополнительный код положительных чисел совпадает с их прямым кодом. Дополнительный код отрицательного числа представляет собой результат суммирования обратного кода числа с единицей младшего разряда (2⁰ – для целых чисел, 2^-л – для дробных)

Пример.

А₁₀ = +10; А₂ = +1010; [А₂]дк = [А₂]ок = [А₂]п = 0|1010

В₁₀ = –15; В₂ = –1111; [В₂]дк = [В₂]ок + 2⁰ = 1|0000+1 = 1|0001

Основные свойства дополнительного кода:

• сложение дополнительных кодов положительного числа С с его отрицательным значением дает т.н. машинную единицу дополнительного кода:

МЕдк=МЕок + 2⁰ = 10|00…00,

т.е. число 10 (два) в знаковых разрядах числа;

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

МЕдк.

Модифицированные обратные и дополнительные коды[править]

Модифицированные обратные и дополнительные коды двоичных чисел отличаются соответственно от обратных и дополнительных кодов удвоением значений знаковых разрядов. Знак «+» в этих кодах кодируется двумя нулевыми знаковыми разрядами, а знак «–» – двумя единичными разрядами.

Пример.

А₁₀ = +10; А₂ = +1010; [А₂]дк = [А₂]ок = [А₂]п = 0|1010

[А₂]мок = [А₂]мдк = 00|1010

В₁₀ = –15; В₂ = –1111; [В₂]дк= [В₂]ок+2⁰ = 1|0000+1 = 1|0001

[В₂]мок= [В₂]мдк= 11|0001

Целью введения модифицированных кодов являются фиксация и обнаружение случаев получения неправильного результата, когда значение результата превышает максимально возможный результат в отведенной разрядной сетке машины. В этом случае перенос из значащего разряда может исказить значение младшего знакового разряда. Значение знаковых разрядов «01» свидетельствует о положительном переполнении разрядной сетки, а «10» – об отрицательном переполнении. В настоящее время практически во всех компьютерах роль сдвоенных разрядов для фиксации переполнения разрядной сетки играют переносы, идущие в знаковый и из знакового разряда.

Арифметические действия в машинных кодах.[править]

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

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

1. Слагаемые должны иметь одинаковое число разрядов. Для выравнивания разрядной сетки слагаемых можно дописывать незначащие нули слева к целой части числа и незначащие нули справа к дробной части числа.
2. Знаковые разряды участвуют в сложении так же, как и значащие.
3. Необходимые преобразования кодов производятся с изменением знаков чисел. Приписанные незначащие нули изменяют свое значение при преобразованиях по общему правилу.
4. При преобразовании единицы переноса из старшего знакового разряда, в случае использования ОК, эта единица складывается с младшим числовым разрядом. При использовании ДК единица переноса теряется. Знак результата формируется автоматически, результат представляется в том коде, в котором представлены исходные слагаемые.

Пример 1. Сложить два числа: А₁₀ = 7, В₁₀ = 16.

А₂ = +111 = +0111; В₂ = +10000.

Исходные числа имеют различную разрядность, необходимо провести выравнивание разрядной сетки:

[A₂]п = [A₂]ок = [A₂]дк = 0|00111; [В₂]п = [В₂]ок = [В₂]дк = 0|10000.

Сложение в обратном или дополнительном коде дает один и тот же результат:

0|00111

+0|10000

———-

С₂ = 0|10111

С₁₀ = +23

Пример 2. Сложить два числа: А₁₀ = +16, В₁₀ = -7 в ОК и ДК.

По таблице необходимо преобразование А+(-В), в которой второй член преобразуется с учетом знака

[A₂]п = [A₂]ок = [A₂]дк = 0|10000;

[В₂]п = 1|111 = 1|00111; [В₂]ок = 1|11000; [В₂]дк = 1|11001

При сложении чисел в ОК и ДК были получены переносы в знаковый разряд и из знакового разряда. В случае ОК перенос из знакового разряда требует дополнительного прибавления единицы младшего разряда (п.4 правил). В случае ДК этот перенос игнорируется.

Практическая часть.[править]

Задание:

1. Взять две пары десятичных двузначных целых числа: А, В, С, D. (Варианты по списку)
2. Вычислить (А-В)ок, (В-А)дк, (С-D)ок, (D-C)дк.

Варианты

1. Вариант — 78, 56, 11, 35;
2. Вариант — 67, 36, 45, 22;
3. Вариант — 21, 87, 38, 44;
4. Вариант — 99, 26, -73, 26,
5. Вариант — 28, 33, 42, 54;
6. Вариант — 61, 43, 65, 41;
7. Вариант — 11, 84, 49, 53;
8. Вариант — 85,- 47, 43, 66;
9. Вариант — 48, 52, 65, 88;
10. Вариант — 26, 58, 63, 77;
11. Вариант — 91, 22, 46, -14;
12. Вариант — 57, 14, 69, 55;
13. Вариант — 77, 98, 25, -88;
14. Вариант — 46, 66, 35, 36;
15. Вариант — 44, 37, 92, 28;
16. Вариант — 63, 46, 83, 71;
17. Вариант — 35, -51, 63, 24;
18. Вариант — 25, 95, -38, 33;
19. Вариант — 32, 29, 86, 27;
20. Вариант — 49, 55, -73, 22
21. Вариант — 33, -77, 53, 71;
22. Вариант — 48, 86, 62, 42;
23. Вариант — 69, -48, 11, 20;
24. Вариант — 10; 82, 80, 45;
25. Вариант — 70, 93, -27, 30;
26. Вариант — 88, -40, 16, 83;
27. Вариант — 64, 80, -17, 77;
28. Вариант — 40, 46, -73, 19;
29. Вариант — 14, -60, 11, 27;
30. Вариант — 90, 73, -10, 20.

19 апреля автор курса «Алгоритмы для разработчиков» в Яндекс.Практикуме и разработчик в компании Joom Александра Воронцова провела открытый вебинар «Оптимизация на простых типах данных». У Аси за спиной 11 лет разработки, опыт олимпиадного программирования, а также работа в Яндексе с высоконагруженными проектами.

Мы подготовили расшифровку вебинара в двух частях. Первая часть — про строки и работу с ними, вторая — про числа.

Статья будет полезна разработчикам на Python и C/C++, которые хотят научиться трюкам для ускорения кода, а также программистам на других языках, которым интересны фишки, связанные с типами данных.

Числа

Что же происходит с числами? Числа как тип данных тоже кодируются битами ноликов и единичек. Вот пример.

Итак, мы умеем хранить положительные числа. А если нам надо каким-то образом зафиксировать ещё и знак числа? Числа же могут быть как положительными, так и отрицательными.

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

Так что нам надо отрезать 1 бит от 8-битного числа (на нашем маленьком примере).

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

А теперь смотрите на нижнюю часть слайда — там есть отрицательные числа. Что делать? Просто записать единичку и следом записать такое же число, как и в случае с положительным — рабочий вариант. Это называется прямой код: мы сравниваем в первой строке, как выглядит чёрная часть массивчика, сравниваем во второй строке и видим, что они равны. Удобно.

Но оказывается, что если мы хотим сложить 75 и –75, то в прямом коде это делать неудобно, потому что у нас не получится 0. Попробуйте сами.

Дополнительный и обратный коды

Поэтому эволюционно в computer science было решено, что удобнее использовать обратный код. Это когда мы берём и все символы (если на первом месте единичка) переворачиваем. В целом вариант удобный, и тут уже при сложении 75 и –75 получается –0. Вроде бы уже сильно ближе, но что это вообще за –0 такой?

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

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

В таком случае сложение двух чисел в дополнительном коде будет давать нам просто +0. Что мы имеем благодаря такому хранению целых чисел — мы можем сохранить в 8 битах (в 1 байте) числа от 2^7-1 до 2⁷. В отрицательных числах просто на одно значение больше.

Зачем всё это знать

Давайте посмотрим пример, на который я сама натыкалась в Java несколько раз, скопипастила его с одного сайта.

public class OverflowUnderflow {
 public static void main(String args[]){
 //roll over effect to lower limit in overflow
 int overflowExample = 2147483647;
 System.out.println("Overflow: "+ (overflowExample + 1));
 //roll over effect to upper limit in underflow
 int underflowExample = -2147483648;
 System.out.println("Underflow: "+ (underflowExample - 1));
 }
}
26
Overflow: -2147483648
Underflow: 2147483647

В чём суть. Java, несмотря на то, какой это большой и полезный язык с количеством разных функций, имеет такую особенность: если взять максимальное целое число, которое влезает в 4 байта, в положительном у нас получится overflowExample, а в отрицательном underflowExample. В коде видно, что underflowExample на единичку по модулю больше, то есть у нас в отрицательном поле есть на 1 резервное число больше.

ОК, добавим к максимальному числу единичку, из минимального числа вычтем единичку и выведем это на экран. И оказывается, что у нас уменьшенное минимальное число больше, чем увеличенное максимальное.

И вот такое перескакивание через границу может вам встретиться в реальном коде. Я сама такое встречала, когда мне важно было посчитать количество фотографий у пользователя. Это был фотограф, который фотографировал всё, до чего дотягивался, и было довольно неприятно, когда ты пытаешься посчитать количество фотографий, а у тебя на выходе внезапно отрицательное число. На это всегда надо обращать внимание. Зная, как оно устроено внутри, вы будете понимать предпосылки и корни возможных проблем.

Длинная арифметика

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

В зависимости от языков программирования у нас есть разные варианты. Тот же Python умеет считать длинную арифметику из коробки. В Java, насколько я помню, она тоже есть в дополнительной библиотеке. А вот во времена моего детства нас такие штуки заставляли писать руками, чтобы понимать, что происходит в библиотеках, когда мы переключаемся на вычисления длинных чисел.

Итак, варианты.

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

Какие у такого сложения могут быть подводные камни? Будет оно работать быстро или медленно? Когда именно оно будет работать медленно?

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

ОК, с суммированием всё неплохо, с вычитанием тоже.

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

Есть простой вариант: мы можем в цикле прибавлять меньшее из чисел, например 321, и в цикле 321 раз складываем 876 435.

В принципе, работать будет. Сложность тут равна длине первого числа, перемноженной на значение второго числа. Может, и многовато, особенно потому, что значение существенно больше, чем длина числа.

Но есть вариант удобнее, если понимать, что происходит внутри.

Давайте посмотрим на простые (не такие длинные) числа и запишем их двоичной системе счисления.

Вот у нас семёрка. Она будет выглядеть как три единички подряд в двоичной системе.

А вот 14, тоже несложно — 2¹+2²+2³. Или расписать иначе, как 2*(2⁰+2¹+2²), а это мы уже видели у семёрки.

Тут полезно заметить, что оба этих числа выглядят друг на друга подозрительно похожими с точностью до нолика справа. Это как раз связано с тем, что одно является другим, умноженным на 2. Поэтому степень двойки в сумме повышается. И выходит, что мы, зная битовую форму числа, быстро можем умножать на 2.

Для небольшой проверки рассчитайте в двоичной форме число 28.

Как это поможет в исходной задаче?

Мы же хотели умножать одно длинное число на другое длинное, помните? Давайте представим число 321 в двоичном виде, а точнее, тут нам удобнее его представить в форме сумм степеней двойки.

Соответственно, каждую из этих трёх строчек мы можем получить в двоичной форме довольно быстро, просто просчитав одно исходное число 876 435. У нас есть специальный побитовый оператор, который позволяет подобное.

Вот так это число выглядит в двоичной форме.

У первого числа справа 8 ноликов, у второго справа 6 ноликов, у последнего справа нулей нет.

Вопрос: если мы говорим, что длинная арифметика — это долго, что у нас десятичные числа долго складываются, что это линейное время, почему число, записанное в двоичной форме (которая всегда длиннее десятичной), работает быстро?

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

Результат такого вычисления позволяет нам сначала узнать, чему будет равно 2⁶. Какие тут варианты — исходное число не помещается, но мы можем сложить нужное количество раз число с самим собой. Сложив один раз, мы получим 2 в первой степени, сложив два раза — 2 во второй и так далее.

Итого мы сначала рассчитаем 2⁶ и прибавим к нему 2⁸. На вычисление 2⁶ у нас потребуется шесть операций сложения, каждая за линейное время, на 2⁸ мы просто сделаем ещё два сложения числа с самим собой. И получится результат.

Для процессора все числа двоичные, но когда мы используем длинную арифметику, как мы сделали в примере на массивах, у нас в одной ячейке хранится не одна цифра и не один бит информации, а в лучшем случае однобайтное число. А как вы помните, один даже беззнаковый байт — это 2⁷.

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

Что ещё важно. Понимание алгоритмов — это здорово, но существует следующий уровень — понимание не только алгоритмов, но и устройства процессоров, потому что там внезапно много интересного. Оттуда же можно почерпнуть, что хоть двоичная система кажется базисом, но математически она не самая оптимальная, и во всём этом реально интересно разбираться.

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

Зачастую для решения задачи нам достаточно не получить точный ответ, а узнать какой-то признак. Например, у нас есть задачка.

Собрали урожай яблок на 23 килограмма, собирали урожай вдевятером. Делить надо всё поровну. Оставшиеся яблоки отвезут бабушке.

Сколько яблок надо отвезти бабушке?

Пока у нас 23 кг, всё не так уже плохо: бабушка получает остаток от деления 23 на 9, то есть 5 кг.

А если количество кг яблок не влезает в целочисленную переменную?

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

Условно вот что мы вычисляем в этот момент времени: если бы работы выполнял только один рабочий и мы бы все его яблоки распределили по остальным рабочим поровну и взяли бы остаток, мы бы получили вклад этого рабочего в остаток яблок для бабушки.

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

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

Удобно. Работает. Но не идеально и оставляет простор для ошибок.

Где всё это применять

Во многих местах, например, в кибербезопасности — тайна вашей переписки.

У нас есть какое-то сообщение, к которому мы добавляем ключ и считаем специальную чек-сумму (отсылка к хэшам, о которых мы говорили), и отправляем письмо.

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

Адресат получает всё это и расшифровывает на своей стороне. Понимает, что расшифровалась какая-то фигня, чек-сумма не совпадает, всё плохо.

Нам важно брать хэш по модулю для того, чтобы не перейти за границу наших целочисленных вычислений. Помните пример с Java? Может оказаться, что наша чек-сумма разъедется потому, что вместо положительного числа у нас получится отрицательное.

Таких применений арифметики по модулю много, они встречаются регулярно, просто часто скрыты от глаз.

Как видите, на самом деле в алгоритмах куда больше интересного, чем может показаться со стороны. Сильно больше, чем можно вместить в один пост (да и в два). Если у вас есть какие-то вопросы или уточнения по тексту или видео вебинара — пишите в комментарии, буду рада ответить.