Java: bits and bytes

Вступление

Если люди считают в десятичной системе счисления, то компьютеры — в двоичной. А программист должен понимать,как говорить и с людьми, и с компьютерами. Данный обзор должен помочь в этом деле. Порой за очевидными вещами кроется целый мир. Предлагаю об этом мире поговорить. Например, в неделе 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 Пример перевода из двоичной системы в десятичную можно увидеть в онлайн калькуляторе. Говоря про то, что правила работы в системах счисления одинаковы, давайте посмотрим на сложение в двоичной системе: Как видно, мы точно так же переносим разряды при сложении, как и в десятичной системе. Разбор сложения можно посмотреть, например, здесь:

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

Кстати, периодически упоминается какое-то слово "разряд". А что это такое? Разряд — это всего лишь "структурный элемент" представления числа. То есть число 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 (верхняя граница). Работа с самим типом данных проста. Используем в качестве "песочницы" для данной статьи онлайн компилятором Java "repl.it". https://repl.it/languages/java. Для примера выполним код, который переменную типа байт представит в двоичном виде в виде строки:

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

Затрагивая байты и биты, нельзя не упомянуть о различных манипуляциях с битами. Наверно, самая распространённая операция — это сдвиги (bitwise shift или bit-shift). А всё потому, что их результат имеет явную практическую пользу. Какая польза? Сдвиг влево на N позиций эквивалентен умножению числа на 2N. А сдвиг вправо аналогичен такому же делению.Таким образом, 5<<2 == 5*Math.pow(2,2) А чтобы понять, почему так, давайте посмотрим на этот пример подробнее: Побитовое отрицание 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 optionB
    if ((optionC & value) != 0b0000) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }

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

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

Итак, байт — это октет, то есть 8 бит. Легко запомнить, что в Java существует тоже 8 примитивных типов, так уж совпало. Примитивным типом называется тип данных, который встроен в язык программирования, то есть доступен по умолчанию. byte — минимальный по объёму занимаемой памяти примитивный тип данных, с которым может работать Java. Как мы ранее говорили, байт занимает 8 бит. Следовательно, старший разряд имеет номер 7. Поэтому, byte содержит значения от -2 в 7 степени до 2 в 7 степени минус 1 из результата. Какие же ещё есть примитивные типы: Как мы видим по таблице, типы данных по объёму занимаемых данных растут в два раза. То есть short = 2 * byte, а int = 2 * short. Запомнить, на самом деле, легко. То, что байт = 8 бит, запомнили. То, что меньше быть не может — тоже запомнили. В английском языке целое число называется integer. Примитивный тип от него назвали сокращением int. Есть обычное целое число — int. Есть его коротка версия short и длинная версия long. Соответственно int занимает 32 бита (4 байта). Короткая версия в 2 раза меньше -— 16 бит (2 байта), а длинная — в два раза больше, т.е. 64 бита (8 байт). Таким образом, int максимум может хранить число примерно в 2 миллиарда и сто миллионов. А long максимум может хранить примерно 9 квадриллионов (красивое слово). Вспоминая бородатый анекдот про то, что начинающий программист думает, что в килобайте 1000 байт, а законченный программист считает, что в килограмме 1024 грамм, можем понять:

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

Кстати, внимательный читатель мог заметить, что на картинке всего 7 типов. 8 примитивный тип — это boolean. boolean — это логический тип данных, который имеет всего два значения: true и false. Но возникает вопрос — какого он размера? Ответит нам Java Virtual Machine Specifiaction и раздел "2.3.4. The boolean Type": То есть просто boolean будет занимать столько же, сколько и int. Если же мы объявим массив из boolean, то каждый элемент массива будет занимать 1 байт. Вот такие вот чудеса :)

Заключение

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

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

#Viacheslav