Представление информации. Целые числа.

Некоторые распространенные примеры:

Число разрядов Тип в C++[^1] Максимально представимое
8 unsigned char 255
16 unsigned short 65535
32 unsigned int 4 294 967 295
64 unsigned long long 18 446 744 073 709 551 615
#include <iostream>
#include <climits>
using namespace std;

int main() {
  cout    << "unsigned char " << sizeof(unsigned char) * CHAR_BIT
  << "\n" << "unsigned short " << sizeof(unsigned short) * CHAR_BIT
  << "\n" << "unsigned int " << sizeof(unsigned int) * CHAR_BIT
  << "\n" << "unsigned long " << sizeof(unsigned long) * CHAR_BIT
  << "\n" << "unsigned long long "
          << sizeof(unsigned long long) * CHAR_BIT
  << endl;
}

Типовый вывод:

unsigned char 8
unsigned short 16
unsigned int 32
unsigned long 64
unsigned long long 64
  • важное следствие конечности числа разрядов
  • при попытке представить число больше максимально представимого – целочисленное переполнение
  • старшие разряды отбрасываются
  • Одно из ключевых следствий – в \(n\) разрядах число \(2^n\) представляется так же, как \(0\)
  • На основе этого свойства строится представление отрицательных чисел.

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

  • старший разряд отводится под обозначение “знака”
  • можно было бы представлять отрицательные числа в виде знака и модуля.
  • но усложнение арифметики
  • Вместо этого – в виде дополнительного кода
  • дополнительного до \(0\), или, как было сказано выше, в \(n\) разрядах – до \(2^n\).
  • Для положительных чисел, знаковый (старший) разряд = 0
  • при использовании дополнительного кода, вычитание может быть реализовано как сложения

Построение дополнительного кода

  1. В \(n\)-битном представлении записывается модуль числа – это называется прямым кодом
  2. Все разряды инвертируются (там, где был 1 ставится 0, и наоборот) – это называется обратным кодом.
  3. К полученному представлению по правилам двоичной арифметики прибавляется 1.
  • определяем дополнительный код как представление \(y\) числа \(x\)
  • при сложении с прямым кодом \(x\) в \(n\) разрядах даст \(y+x = 2^n\)
  • Сложение обратного кода с прямым по построению даст \(2^n-1\)
  • следовательно, прибавление к обратному коду 1 даст дополнительный код
  • более строго можно показать, записав коды в виде суммы по степеням \(2\)

Пример

  • дополнительный код числа \(-11\) в 8-битном знаковом представлении
  • \(11 = 0000\,1011_2\)
  • Обратный код \(11110100_2\)
  • Прибавляя 1, получаем дополнительный код: \(11110101_2\)
  • эквивалентно, это \(1\,0000\,0000_2 - 1011_2\)
  • Для положительных чисел считается, что дополнительный код совпадает с прямым.
  • Если построить дополнительный код от дополнительного кода, снова получается прямой.
  • Т. о., если старший (“левый”) разряд равен 1, то в знаковом представлении число интерпретируется как отрицательное.
  • Проверим, что основное арифметическое тождество выполняется:
  • \(11 - 11 = 0\)
  • представление в 8 разрядах.

Прямой код (11):

0 0 0 0 1 0 1 1

Дополнительный код (-11):

1 1 1 1 0 1 0 1

Сумма:

0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0

0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0

Поскольку представление 8-битное, старший бит результата отбрасывается. Остается

0 0 0 0 0 0 0 0
  • один бит отводится под “знаковый” разряд

  • максимально представимое в знаковом представлении в 2 раза меньше, чем в беззнаковом

  • По соглашению, в \(n\)-битном знаковом представлении, число \(1\underbrace{0\ldots0}_{n-1}\) считается отрицательным, однако его дополнительный код совпадает с прямым:

  • обратный код: \(0\underbrace{1\ldots1}_{n-1}\)

  • дополнительный код: \(0\underbrace{1\ldots1}_{n-1}+1= 1\underbrace{0\ldots0}_{n-1}\)

  • модуль минимально представимого числа на 1 больше, чем модуль максимально представимого числа.
  • Общая формула для максимально представимого в \(n\)-битном знаковом представлении: \(I_{max} = 2^{n-1}-1\).
  • Общая формула для минимально представимого в \(n\)-битном знаковом представлении: \(I_{min} = -2^{n-1}\).

Распространённые примеры

Число разрядов Тип в C++ Мин Макс
8 char -128 127
16 short -32768 32767
32 int -2 147 483 648 2 147 483 647
64 long long -9 223 372 036 854 775 808 9 223 372 036 854 775 807

Перечисление чисел

  • в общем случае при перечислении чисел мы имеем “числовую прямую”
  • в конечном числе разрядов получается “числовая окружность” (формально, кольцо)
  • при прибавлении 1 к максимально представимому, получаем минимально представимое
  • важно иметь в виду при разработке программного обеспечения
  • Например, считаем зарплату сотрудника за месяц исходя из почасовой ставки
  • Пусть в месяце 20 рабочих дней, в дне 8 рабочих часов, и почасовая ставка 100 рублей
  • Все числа представимы в 8-битном знаковом представлении
  • Умножая, получаем \(20\cdot8\cdot100 = 16000\)
  • Попытавшись представить это число в 8-битном знаковом представлении, получим:
1 0 0 0 0 0 0 0
  • это отрицательное число \(-128\). Оказывается, сотрудник еще остался должен.
  • Подобные “сюрпризы” не являются редкостью а