Представление целых чисел

Попробуйте ответить на несколько вопросов, представленных ниже

Что будет выведено в следующих примерах? (примеры на Java)

А здесь, сколько раз будет выполнен цикл (язык C)?

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

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

Целые беззнаковые числа

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

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

Таким образом, число из n бит дает 2 в степени n значений, так как каждый следующий бит удваивает количество значений.

Так мы можем получить некоторое множество значений. Но эти значения нужно отобразить на наши десятичные числа. Сделать это можно просто соотнеся числа десятичной системы, начиная с 0 и прибавляя 1 и двоичной системы, также прибавляя 1. В десятичной системе, имея основание 10, мы переносим 1 в следующий разряд тогда, когда прибавляем к последней цифре 1. Например, 9 + 1 = 10, мы перенесли 1 в разряд десятков. В двоичной системе все тоже самое, но у нас разрядность 2, а значит мы переносим в следующий разряд тогда, когда прибавляем 1 к 1. Например, 01 + 1 = 10, мы перенесли 1 в следующий разряд. Так мы получим соотношение десятичных и двоичных цифр.

Рассмотрим на примере некоторого числа, например 55 (число неважно).

Итак, число 55 в двоичном формате будет выглядеть как 11_0111, или с ведущими нулями 0011_0111. Число 123 можно представить как 100 + 20 + 3, или (1 * 10 ^ 2) + (2 * 10 ^ 1) + (3 * 10 ^ 0). В двоичной системе все тоже самое, но основание равно не 10, а 2. Число 110(6 в десятичной) - это (1 * 2 ^ 2) + (1 * 2 ^ 1) + (0 * 2 ^ 0). Здесь все довольно просто.

Всего в 1 байт поместится 256 разных значений - от 0000_0000 до 1111_1111. Важно понимать, что это не значения от 0 до 255 - это просто последовательность бит, но мы можем интерпретировать это значение как знаковое число, беззнаковое число, символ или любым другим способом. За то, как мы будем интерпретировать это значение отвечает тип переменной и, возможно, ее модификаторы.

Целые знаковые числа

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

Если нам нужно хранить как положительные, так и отрицательные числа, то диапазон 256 значений мы делим поровну на числа со знаком "+" и "-".

Все, что описано для 1 байта можно обобщить на типы хранения чисел любой другой длины: 2, 4, 8 байт.

Прямой код

Принцип прямого кода предельно прост. Мы отдадим 1 бит под знак (самый первый) а остальные 7 бит будут отвечать за значение. Тогда наше значение числа 55 в 7 битах будет выглядеть как 011_0111. Если первый бит 0 - наше число 55, если 1 - число -55. Числа абсолютно симметричны и, например, для умножения числа на -1 (смены знака) нужно сменить только первый бит, что довольно удобно. Но не совсем понятно как реализовать и вычитание чисел.

Обратный код

Все тоже самое как и в прямом коде, но при смене знака числа мы инвертируем (меняем 0 на 1, а 1 на 0) все биты (при этом меняется и знаковый бит). Первый бит все также отвечает за знак. Число 55 остается 0011_0111, а вот -55 теперь будет иметь представление 1100_1000.

Для перевода из положительного числа в отрицательное нам нужно выполнить операцию исключающего или. Со сложением и вычитанием опять же не все очевидно.

У обоих способов, описанных выше есть серьезный недостаток - число "0" может быть как положительным, так и отрицательным, хотя оно является положительным. И запись 0000_0000, и 1000_0000 определяют число 0.

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

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

Если посмотреть на обратный код выше, можно заметить, что при сложении положительного числа Х и отрицательного числа Х получается значение, состоящее из всех единиц. Например 55 - 55 = 55 + (-55) = 0011_0111 + 1100_1000 = 1111_1111. Прибавив еще 1 мы бы получили все нули и 1 в 9 бите, т.е. 1111_1111 + 1 = 1_0000_0000, но первая единица не влезает в 1 байт, ее можно просто отбросить. Тогда мы получим то, что при сложении положительного числа с отрицательным такого же значения получается значение 0.

Можно забыть о различие сложения и вычитания, т.к. А - В = А + (-В). Мы просто складываем 2 числа так, как если бы они были положительными. Но для таких операций отрицательные числа должны иметь особую форму называемую дополнение до двух.

Возьмем для примера число 55. Для умножения его на -1 (т.е. для получения того же числа со знаком -) нам нужно сделать следующие действия

1. Инвертируем все биты в числе (там, где был 1 будет 0, а где был 0 - будет 1). Число 55, представленное в двоичном виде как 0011_0111 станет 1100_1000
2. Добавляем 1 к этому числу. Полученное значение: 1100_1000 + 0000_0001 = 1100_1001. Если рассмотреть это значение как беззнаковое (не учитывать первый бит как бит знака), то это число равняется 201. А если как знаковое - это число -55. Что более интересно, если мы прибавим к этому числу 54 (на 1 меньше модуля числа) - неважно знаковое оно или нет, то мы получим число 255 или в двоичном виде 1111_1111. если прибавим еще 1 - получим все нули в последних 8-ми битах.

Итак, чтобы перевести число из отрицательного в положительное (и наоборот) нужно инвертировать это число и прибавить 1.

Почему это работает

Для того, чтобы понять почему это работает, представим себе часы. Как может стрелка часов попасть из значения 6 в значение 3? Можно отодвинуть стрелку часов на 3 значения назад, что будет означать 6 - 3 = 3. А можно прибавить 9. Тогда мы получим значение 6 + 9 = 15, но на часах есть значения только до 12, после чего значения начнутся сначала. Если мы прибавим к значению часовой стрелки 9, она сделает круг и примет значение 3. Итак, 6 - 3 в данном случае эквивалентно 6 + 9. Мы свели вычитание к сложению

В общем случае 6 - 3 = 3 + (12 - 3), где 12 - наше основание или максимальное значение.

В случае 1 байта максимальное значение = 256 (точнее количество значений). Как можно представить -55? Как 0 - 55, по аналогии с часами, это 6 - 3. Это же значение можно записать как 0 + (256 - 55), что равняется 201 (как 6 + (12 - 3)). Т.е. мы дополнение до двух это такой формат, при котором мы можем забыть про то, что отрицательные числа - отрицательные.

Это важный момент. Мы работаем с последовательностью битов. Когда мы выполняем операцию 0 - 55, с точки зрения машины мы выполняем операцию 0000_0000 - 0011_0111 и получаем значение 1100_1001. Но что это за значение, зависит от того, как мы будем интерпретировать эти биты. Если мы говорим, что это знаковое число - мы получим -55. Если беззнаковое - число 201.

Зачем мы делаем инвертирование битов? Посмотрим на значение 55 - это 0011_0111. Его инвертированное значение равно 1100_1000 (или 200 беззнаковое). Что мы получим, если сложим оба этих числа? Правильно, 1111_1111 или 255. Чему равно значение 255 - 55, или 1111_1111 - 0011_0111? Равно 0011_0111, или 200. Т.е. мы не инвертируем значения, а вычитаем, просто используем то свойство что x + ~x = 11...11.

Итак, мы поняли что 0 - 55 можно представить как 0 + (256 - 55), а 256 мы можем представить как 255 + 1, значит 0 - 55 = 0 + (255 - 55 + 1), но 255 - 55, как мы выяснили выше, можно представить как инверсию всех битов числа 55, т.е. 0 - 55 = 0 + (~55 + 1) и это именно та формула, которую мы использовали. Почему мы прибавляем 1? Потому что число отрицательных чисел на 1 больше, чем положительных (в 1 знаковом байте максимальное отрицательное число -128, а положительное - 127. Это так, потому что 0 - положительное число и в итоге и положительных, и отрицательных чисел по 128).

Посмотрим на похожие часы, но состоящие из 3-бит в котором значения от -4 до 3 (или от 0 до 7, или от 000 до 111)

Как мы можем получить из значения -3(101) значение 3(011)? Можно вычесть 2 (101 - 010 = 011), а можем прибавить 6 (101 + 110 = (1)011, но первая единица будет обрезана т.к. для нее нет места, получим также 011). Раз эти операции для нас равны, осталось понять, какое число нам нужно прибавлять. Это число в данном случае равно 8 - 3 + 1, где 8 это количество вариантов, 3 - это число которое мы переводит.

В итоге распределение значений в 1 байте будет выглядеть так

Мы можем сделать из положительного числа отрицательное. Как сделать из отрицательного положительное? Точно также. Допустим нам нужно перевести -55 и получить 55, тогда -55 (1100_1001) - инвертируем (0011_0110) и прибавляем 1 (0011_0111).

Пример №2

Давайте посмотрим на пример №2. Math.abs() выводит модуль числа (число без знака), т.е. если число = 55, то выводит 55. Если число -55 - то выводит 55.

Попробуем вывести число 2_147_483_647. В двоичном виде оно 1000_(все нули)_0001. Переводим значение в положительное - инвертируем и прибавляем 1 - получим 0111_(все единицы)_1111, т.е. число 2_147_483_647. Все верно.

Теперь тоже самое с числом -2_147_483_648. В двоичном виде 1000_(все нули)_000. Инвертируем - получим 0111_(все 1)_1111. Прибавляем 1 и получаем ... 1000_(все нули)_0000. Это опять же число -2_147_483_648. Да, это так так как в int нет положительного значения 2_147_483_648. Эта не особенность языка, это особенность выбранного формата.

Пример на языке С

В первом случае цикл будет выполняться бесконечно. Его условие для продолжение - i >= 0. Как только i станет равно 0, цикл выполнится. Но на следующей итерации i будет равно не 0 - 1 = -1, a 0 - 1 для беззнакового типа, т.е. наибольшее значение int. У unsigned int просто нет отрицательных значений. Если мы заменим unsigned на signed, все будет работать как ожидается (цикл выведет значения от 10 до 0).

Во втором примере мы добавили лимит на 20 строк, так что цикл точно не будет бесконечным. Единственная разница здесь - метод printf. Если мы пишем %d, то мы просим вывести число со знаком. Если %u - то без знака. Это одна и та же последовательность бит, но в случае с %d мы получим значения 10, 9 ... 0, -1, -2 ... -9, а в случае с u мы получим 10, 9 ... 0, 4294967295, 4294967294 ... 4294967287.

Перевод в двоичное представление

В Java для получения двоичного представления числа можно вызвать статический метод toBinaryString у класса Integer

В общем виде мы можем сделать следующий метод, который переводит int в двоичное число. Да, метод будет работать только с 32-битными значениями (значение k), но он довольно прост.

Работает он следующим образом. Сначала нам нужно создать переменную mask - это переменная у которой в каждый момент из 32 бит только один равен 1, а остальные 31 равны 0.

В начале единице равен самый последний, 32-ой бит. Если в числе x 32-ой бит также 1, то побитовая операция & (И) вернет 1, т.к. 1 & 1 = 1. Если в числе x 32-ой бит равен 0, то и операция & вернет 0 т.к. 1 & 0 = 0.

Единицу мы сдвигаем вправо на каждой итерации и проверяем следующий бит числа x. Иллюстрация этой идеи для первых двух итераций представлена ниже.

Вывод, в отличие от toBinaryString, будет со всеми битами, даже если первые из них нули.

Получение знака числа

Для получения знака числа нам нужно просто узнать самый последний бит. Мы можем сдвинуть все биты вправо до того момента, пока знаковый бит не окажется на первом бите, заполняя старшие биты 0 (побитовый беззнаковый сдвиг вправо), а можем сделать это тем-же способом, как поступали при переводе в двоичный формат числа, т.е. применить побитовый оператор & с маской в виде числа, в котором все кроме 32 бита равны 0. Если после этой операции полученное число будет равно маске, это значит что 32-ой бит равен 1 и число отрицательное. Если нет - 32-ой бит равен 0 и число положительное.

Порядок байт

Представим, что у нас есть 2 байта, которые в двоичном виде выглядят так: 0000_0000_1111_1111. Предположим, что мы интерпретируем их как беззнаковое число. Какое это число? Вы уверенно можете заявить, что это число 255 т.к. первые 8 байт равны нуля, а вторые 8 байт равны 1, что дает число 255.

Это действительно 255, но вы будете правы на половину. Дело в том, что помимо значения байт есть еще и такое понятие как порядок байт от старшего к младшему.

Мы все привыкли к порядку от старшего к младшему, т.е. сначала идут старшие биты, а потом младшие. В число 54 сначала идут десятки (5), а потом единицы(4), т.е. сначала старшие разряды.

Но есть и другой способ представления - от младшего к старшему, т.е. первые идут младшие разряды и наше число будет записано как 45. Да, это немного сбивает, ведь мы получаем совсем другое число - 45, но в данном случае это число 54, просто записанное в порядке от младшего к старшему.

У такие порядков есть имена - от старшего к младшему называется big - endian, (т.е. что то вроде с большого конца числа), обратный порядок - little endian (т.е. с малого конца числа). Чтобы понять, какой из них лучше, представьте себе форму, где вас просят написать свое имя и фамилию. Спор о том, что лучше big или little endian равносилен спору что лучше, сначала имя, а потом фамилия или наоборот.

Но для техники порядок байт крайне важен. Порядок байт от старшего к младшему называют "сетевым порядком байт", т.к. именно он используется при формировании пакетов для протоколов TCP/IP.

Порядок от младшему к старшему используется в архитектуре x86 (его называют интеловский порядок).

Вернемся к вопросу из начала: чему равно число 0000_0000_1111_1111? Или 255, или 65280 (это если мы рассматривает как беззнаковое число). Зависит от порядка байт.

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

Ответ на вопрос почему мы не можем договориться об одном формате - это вопрос из серии почему мы не можем договорится и все общаться на одном языке.

Переполнения

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

Вся суть переполнения можно показать на примере одометра. Это устройство, которое есть у любого автомобиля и оно показывает пройденный путь. Но в какой то момент одометр покажет максимальное значение и начнет отсчет заново. Например, на изображении ниже после 999_999 должно идти 1_000_000, но у одометра есть только 6 значений и он не может отобразить миллион. Поэтому 1 просто теряется, а отсчет начинается сначала.

Пример №4

Пример №4 показывает эту ситуацию. Переменная i_x2 просто не помещается в int (на самом деле в целочисленный int), и значение становится отрицательным

Другой пример. Математика и логика нам подсказывает, что при любом значении x выражение x + 1 больше, чем просто x, т.е. x + 1 > x. Однако Это не так для максимального положительного значения любого знакового типа. Выведя эти значения, понятно почему.

Пример №1

В примере №1 было следующее выражение

(byte) 511 == (byte) -1

Оно возвращает true, и вот почему. В 1 байт может поместиться только 8 бит. Число 511 в двоичном виде выглядит так 1_1111_1111, а число -1 - так 1111_1111. Это разные числа, но последние 8 бит у них совпадают, а так как мы указали конкретный тип, Java отсекает все старшие биты. Такой же результат даст сравнение с любым числом, у которого младшие 8 бит равны 1.

Так что сравнение выше - это не сравнение серии " А правда что 255 равно -1". Это сравнение серии "А правда, что младшие 8 бит числа 255 совпадают с 8 битами знакового 8-ми битного целого числа". Да, правда.

Пример №3

Пример №3 также теперь понятен.

В первом случае мы умножили 127 на 2, получили 254 и сказали что это значение типа знаковый байт, у которого максимальное значение 128. Полученное значение в двоичном виде (1111_1110) равняется -2.

В выражении (byte) b1 * 2 мы сказали, что у нас есть тип значение b1 типа байт и значение 2, не указав его тип. В Java, если мы не указали значение типа, оно равно int (32 бита). Еще одна особенность, что если мы выполняем вычисления с 2-мя разными типами, то меньший тип расширяется до большего. В данном случае byte будет расширен до int (первые байты будут просто заполнены нулями), дальше будет вычислен результат как int (который вмещает число 254) и это число как int передано методу println, который выведет его в консоль. Приведение к byte в данном случае ничего не дает и строки 3 и 4 в целом одинаковы.

Двоично-десятичное представление

Кроме чисто двоичного представления чисел иногда используют так называемую двоично-десятичную форму. Эта представление десятичной цифры с помощью 4-х байт. Имея 4 байта, мы имеет 16 возможных вариантом, из которых используются только 10 (0 - 0000, 9 - 1001). Остальные значения не используется.

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

Например, при использовании таких чисел в дробных числах точность не теряется. Такой формат можно встретить в калькуляторах. Формат такого числа довольно легко умножать на степени 10 (нужно сдвинуть на 4 бита влево).

Заключение

• Отрицательные числа в компьютере представлены с помощью дополнительного кода
• Вычитание и сложение чисел выполняются одинаково
• диапазон представленных чисел для N бит при беззнаковом способе: от 0 до 2 ^ N, при знаковом: от 2 ^ (N - 1) до 2 ^ (N - 1) - 1. Например, для 1 байта эти значения от 0 до 255 и от -128 до 127 соответственно
• Мы можем по разному интерпретировать одну и туже последовательность бит.
• Следите за типами чисел и тем, чтобы не происходило переполнения.