Java: bits and bytes

Если коротко: бит это одна двоичная цифра, 0 или 1, а байт это восемь бит, самый маленький кусок памяти, к которому можно обратиться по адресу. В Java на байте построен тип byte со значениями от -128 до 127, а все остальные целые типы просто кратны ему по размеру. Ниже разбираем, откуда берется двоичная система, как в восьми битах умещаются отрицательные числа, что делают сдвиги и побитовые операции, и сколько на самом деле занимает каждый примитив.

Кратко

• Бит это один двоичный разряд, 0 или 1. Байт это восемь бит, наименьшая адресуемая единица памяти; восемь бит дают 256 разных значений.
• В Java byte знаковый: старший бит отвечает за знак, поэтому диапазон от -128 до 127, а 127 + 1 дает -128.
• Отрицательные числа хранятся в дополнительном коде: инвертировать все биты и прибавить 1. Поэтому ~5 это -6, а не -5.
• Сдвиг влево на N это умножение на 2 в степени N, сдвиг вправо это деление: 5 << 2 дает 20.
• Побитовое И проверяет отдельные биты: x & 1 равно 0 у четных чисел, а вместе с ИЛИ из битов собирают маски флагов.
• Целые типы растут вдвое: byte 8 бит, short 16, int 32, long 64. Для boolean у JVM нет своих инструкций: в вычислениях он обрабатывается как int, а в массивах на элемент отводится байт.

Вступление

Если люди считают в десятичной системе счисления, то компьютеры в двоичной. А программист должен понимать, как говорить и с людьми, и с компьютерами. Данный обзор должен помочь в этом деле. Порой за очевидными вещами кроется целый мир. Предлагаю об этом мире поговорить. Например, в неделе 7 дней. А теперь, ответим на вопрос: Что такое число "7"? ) Во-первых, это целое (integer) положительное (positive) натуральное (natural) число. А еще это десятичное число (decimal number). Десятичное число это число в десятичной системе счисления (Decimal System). Когда мы говорим "десятичная система счисления", это означает, что у системы счисления основание (base) равно 10. Основание показывает, сколько цифр может быть использовано в данной системе счисления для представления числа. Отсчет ведется от нуля. Соответственно, для представления чисел в десятичной системе счисления мы используем цифры от 0 до 9. Это хорошо, но считать нужно не только до 9, но и дальше. Как же быть? Например, число 10. Для записи данного числа мы используем уже целых 2 цифры. Позиция каждой цифры в десятичной системе называется десятичным разрядом (decimal place). Разряды отсчитываются справа налево: Кроме того, десятичное число можно разложить следующим образом: 103 = 1*10^2 + 0*10^1 + 3*10^0 Число ведь по сути растет справа на лево. То есть сначала было 7, а потом стало 10. Поэтому и разряды считаются справа, начиная с нуля. А для чего все это? Все потому, что мы не компьютеры. И если мы считаем в десятичной системе (то есть, по основанию 10), компьютеры считают в двоичной системе счисления (то есть, по основанию 2). Но правила, которые действуют в этих системах счисления, одинаковы.

Двоичная система

Двоичная система очень похожа на десятичную с тем лишь отличием, что ограничение здесь не 10, а 2.

Перевод из десятичной системы в двоичную

Давайте сравним на примере. Как нам представить 11 в двоичной системе? Очень просто: надо лишь разделить десятичное число на основание 2, то есть посчитать 11/2 в столбик. Пример: Или вот пример с WikiHow: Интересно, что мы можем число представить в двоичной системе так же, как и в десятичной: 111 в двоичной системе = 1*2^2 + 1*2^1 + 1*2^0 = 4 + 2 + 1 Переводить туда и обратно умеет и сама Java: Integer.toBinaryString(11) вернет строку "1011", а Integer.parseInt("1011", 2) прочитает ее как число 11 (второй аргумент это основание системы счисления). Говоря про то, что правила работы в системах счисления одинаковы, давайте посмотрим на сложение в двоичной системе: Как видно, мы точно так же переносим разряды при сложении, как и в десятичной системе. Разбор сложения можно посмотреть, например, здесь:

• "Фоксфорд: Сложение, вычитание и умножение двоичных чисел"

Разряд, бит и байт

Кстати, периодически упоминается какое-то слово "разряд". А что это такое? Разряд это всего лишь "структурный элемент" представления числа. То есть число 10 состоит из двух разрядов: нам надо 2 разряда, 2 места, 2 элемента, чтобы записать это число. Нам это важно понимать потому, что в двоичной системе счисления разряд это бит (bit). Слово Bit произошло от английского "binary digit", то есть двоичная цифра. Она может быть или 0, или 1. Но так же, как мы читаем с вами цифры и слова целиком, а не по буквам, компьютеры читают не по одному биту. Минимальным "куском" обрабатываемой информации в оперативной памяти (так называемая наименьшая адресуемая единица информации) считается последовательность из 8 бит. Так как их 8, это называют "октет". А еще более известным нам словом Байт (Byte). Чтобы запомнить октет, можно запомнить, что слово осьминог (восемь ног) переводится на английский как octopus. То есть тут как раз тот самый "окто" в названии: Давайте подумаем, какое максимальное число мы можем представить в виде 8 бит? И тут возникает вопрос: а как же быть с отрицательными числами? Чтобы понять это, поговорим о том, как представлены байты в Java.

Java и Byte

Как же так получается, что в Java мы можем использовать отрицательные числа? Сделано это просто. В Java байты знаковые. Крайний левый разряд/бит (его еще называют "старший бит") сделан своего рода "маркером", отвечающим на вопрос: "Это число отрицательное?". Если ответ да, значит маркер имеет значение 1. А иначе 0. Давайте посмотрим на примере, как превратить число 5 в отрицательное число 5: Руководствуясь этой картинкой можно понять, в каких пределах лежит значение типа Byte: Так же видно, что:

• если прибавить единицу к 127, мы получим уже -128.
• если вычесть единицу из -128, мы получим 127.

Таким образом, Byte в Java может принимать значение от -128 до 127. Как мы помним, байт это октет. А максимальный разряд/старший бит имеет порядковый номер 7, так как мы считаем от нуля. В этом случае легко запомнить, что байт равен от -2 в степени 7 (нижняя граница) до 2 в степени 7 минус 1 (верхняя граница).

Байт в коде

Работа с самим типом данных проста. Используем в качестве "песочницы" для данной статьи онлайн-компилятор Replit (раньше он назывался repl.it): https://replit.com. Для примера выполним код, который переменную типа байт представит в двоичном виде в виде строки (метод Integer.toBinaryString отдает число без ведущих нулей, поэтому до восьми знаков его дополняет String.format):

class Main {
  public static void main(String[] args) {
    byte octet = 5;
    String bin = String.format("%8s", Integer.toBinaryString(octet)).replace(' ', '0');
    System.out.println(bin);
  }
}

Работа с байтами активно используется при работе с I/O Streams. Подробнее можно прочитать в tutorial от Oracle: "I/O Streams". Кроме того, в Java можно использовать особый литерал, чтобы значение указывать в виде битов:

class Main {
  public static void main(String[] args) {
    byte data = 0b101; 
    System.out.println(data);
  }
}

Bit Manipulation

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

Сдвиги

Наверно, самая распространенная операция это сдвиги (bitwise shift или bit-shift). А все потому, что их результат имеет явную практическую пользу. Какая польза? Сдвиг влево на N позиций эквивалентен умножению числа на 2 в степени N. А сдвиг вправо аналогичен такому же делению. Таким образом, 5<<2 == 5*Math.pow(2,2) А чтобы понять, почему так, давайте посмотрим на этот пример подробнее:

Побитовое отрицание NOT

Побитовое отрицание NOT (Unary bitwise), которое обозначается как тильда, инвертирует биты. Записывается, например, так: ~5.

public static void main(String[] args) {
	System.out.println(~5); //-6
 	System.out.println(~-5);//4
}

Это лишний раз показывает, что когда Java меняет знак у числа, кроме инверсии значений битов в самом конце выполняем +1. А без этого, как мы видим, наше число 5 изменяется. И чтобы оно осталось тем же числом, что и до смены знака, надо делать +1. Если хочется разобраться, почему все устроено именно так, у нас есть отдельная статья про побитовое отрицание.

Побитовое И и маски

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

int x=4;
System.out.println((x&1) != 1);

Данный код проверяет число x на четность. Давайте посмотрим на примере: При помощи совместного использования побитового И (Bitwise AND) и побитового ИЛИ (Bitwise OR) можно использовать маски:

public static void main(String[] args) {
    byte optionA=0b0100;
    byte optionB=0b0010;
    byte optionC=0b0001;
    byte value = (byte)(optionB | optionC);
    // Check for optionC
    if ((optionC & value) != 0b0000) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }

Подробнее см. "Masking options with bitwise operators in Java". Манипуляции с битами это занятная тема, по которой пишутся отдельные обзоры, статьи и книги. И отсюда начинается длинный путь в криптографию. В рамках данного обзора стоит понимать, почему это работает и как. Все семь операторов с примерами разобраны в статье «Побитовые операции в Java».

Примитивные типы

Итак, байт это октет, то есть 8 бит. Легко запомнить, что в Java существует тоже 8 примитивных типов, так уж совпало. Примитивным типом называется тип данных, который встроен в язык программирования, то есть доступен по умолчанию. Обзор всех восьми с примерами есть в отдельной статье. byte это минимальный по объему занимаемой памяти примитивный тип данных, с которым может работать Java. Как мы ранее говорили, байт занимает 8 бит. Следовательно, старший разряд имеет номер 7. Поэтому, byte содержит значения от -2 в 7 степени до 2 в 7 степени минус 1. Какие же еще есть примитивные типы? Границы целых типов взяты из JLS 4.2.1, размер boolean спецификация не задает (об этом ниже): Как мы видим по таблице, целые типы данных по объему занимаемой памяти растут в два раза. То есть short = 2 * byte, а int = 2 * short. Запомнить, на самом деле, легко. То, что байт = 8 бит, запомнили. То, что меньше быть не может, тоже запомнили. В английском языке целое число называется integer. Примитивный тип от него назвали сокращением int. Есть обычное целое число, int. Есть его короткая версия short и длинная версия long. Соответственно int занимает 32 бита (4 байта). Короткая версия в 2 раза меньше, 16 бит (2 байта), а длинная в два раза больше, то есть 64 бита (8 байт). Таким образом, int максимум может хранить число примерно в 2 миллиарда и сто миллионов (точнее, 2 147 483 647). А long максимум может хранить примерно 9 квинтиллионов (красивое слово): 9 223 372 036 854 775 807. Точные границы всех целых типов зафиксированы в спецификации языка, раздел 4.2.1. Вспоминая бородатый анекдот про то, что начинающий программист думает, что в килобайте 1000 байт, а законченный программист считает, что в килограмме 1024 грамм, можем понять:

1 mb = 1024 Kbyte = 1024 * 1024 = 1048576 bytes
1 int = 4 bytes
1 mb = 262144 int

Сколько занимает boolean

Внимательный читатель мог заметить, что у семи типов в таблице размер указан в битах, а у восьмого, boolean, стоит пометка «спецификацией не задан». boolean это логический тип данных, который имеет всего два значения: true и false. Но возникает вопрос: какого он размера? Ответит нам Java Virtual Machine Specification и раздел "2.3.4. The boolean Type": То есть своих инструкций для boolean у виртуальной машины нет, и в вычислениях она обращается с ним как с int. Если же мы объявим массив из boolean, то каждый элемент массива будет занимать 1 байт. А вот сколько занимает одиночное поле типа boolean внутри объекта, спецификация не фиксирует вовсе: это решает конкретная реализация JVM. Вот такие вот чудеса :)

Заключение

Предлагаю ознакомиться еще с парой материалов, для закрепления:

• "Hackerrank: Bit Manipulation"
• "Hackerrank: Solve 'Lonley Integer' Using Bit Manipulation"
• "Bit Manipulation 01: Introduction"
• "Coding Challenge #120: Bit Shifting"

#Viacheslav

Вопросы и ответы

Сколько бит в байте и почему именно восемь?

Восемь. Байт это наименьшая единица памяти, к которой процессор может обратиться по адресу, и исторически она закрепилась на восьми битах, отсюда второе название «октет». Восемь бит дают 2 в восьмой степени, то есть 256 разных комбинаций: от 0 до 255 без знака или от -128 до 127 со знаком.

Почему byte в Java хранит числа от -128 до 127, а не от 0 до 255?

Потому что byte в Java знаковый: старший из восьми битов отведен под знак. На само значение остается семь битов, это 128 положительных комбинаций (с нулем) и 128 отрицательных. Беззнакового байта в языке нет, но есть методы вроде Byte.toUnsignedInt, которые читают те же восемь бит как число от 0 до 255.

Как хранятся отрицательные числа: что такое дополнительный код?

Чтобы получить минус N, берут двоичную запись N, инвертируют все биты и прибавляют единицу. Для 5 это 00000101, после инверсии 11111010, после плюс единицы 11111011, и это и есть -5. Такой способ выбран потому, что сложение и вычитание с ним работают одной и той же схемой без отдельной обработки знака. Отсюда же эффект ~5 == -6: инверсия без прибавления единицы дает число на один меньше.

Чем оператор >> отличается от >>>?

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

Сколько памяти занимает boolean в Java?

Спецификация JVM это не фиксирует. У виртуальной машины нет отдельных инструкций для boolean, в вычислениях он обрабатывается как int, а в массивах на каждый элемент отводится один байт. Сколько занимает одиночное поле boolean внутри объекта, зависит от реализации JVM и выравнивания, на практике это обычно один байт плюс выравнивание до границы слова.

Как вывести число в двоичном виде в Java?

Методом Integer.toBinaryString(n): он возвращает строку из нулей и единиц без ведущих нулей, для 5 это "101". Если нужны все восемь разрядов, строку дополняют: String.format("%8s", Integer.toBinaryString(n)).replace(' ', '0') даст "00000101". Для long есть Long.toBinaryString. В обратную сторону работает Integer.parseInt("101", 2).

Читайте также

• Побитовые операции в Java
• Примитивные типы Java
• Вещественные числа в памяти компьютера
• Кодировка текста: ASCII, Windows-1251 и Юникод