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, цей називають "октет". А ще більш відомим нам словом Байт (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 байти). Коротка версія вдвічі менше - 16 біт (2 байти), а довга - вдвічі більше, тобто. 64 біти (8 байт). Таким чином, int максимум може зберігати число приблизно 2 мільярди і сто мільйонів. А long максимум може зберігати приблизно 9 квадрильйонів (гарне слово). Згадуючи бородатий анекдот про те, що програміст-початківець вважає, що в кілобайті 1000 байт,

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