Порозрядні операції

2.7. Порозрядні операції

Порозрядні (або побітові) операції — це особливий клас операцій, які виконуються не над числом як цілим значенням, а безпосередньо над його окремими двійковими розрядами (бітами). Щоб зрозуміти порозрядні операції, необхідно мати уявлення про те, як числа зберігаються в пам'яті у вигляді послідовності нулів і одиниць. Наприклад, число 5 у двійковому поданні — це 101, число 12 — це 00001100. Порозрядні операції працюють саме з цими позиціями (розрядами) і формують результат, обробляючи кожен розряд незалежно.

Побітовий AND — операція `&`

Операція & (AND, кон'юнкція) виконує побітове логічне множення: для кожного розряду результат дорівнює 1 лише тоді, коли в обох операндів цей розряд дорівнює 1. Якщо хоча б в одного операнда розряд дорівнює 0 — результат 0.

Розглянемо приклад з числами 4 (двійк. 100) та 5 (двійк. 101):

  100   (4)
& 101   (5)
-----
  100   (4)

Перший розряд: 1 & 1 = 1. Другий: 0 & 0 = 0. Третій: 0 & 1 = 0. Результат — 100, тобто 4.

Операція AND часто використовується для перевірки або скидання окремих бітів у числі — наприклад, щоб з'ясувати, чи встановлений певний прапорець у бітовому полі.

Побітовий OR — операція `|`

Операція | (OR, диз'юнкція) повертає 1 у розряді, якщо хоча б у одного з операндів цей розряд дорівнює 1. Тільки якщо обидва розряди дорівнюють 0 — результат 0.

Операція OR застосовується для встановлення бітів — примусового переведення окремих розрядів у 1.

Побітовий XOR — операція `^`

Операція ^ (XOR, виключне АБО) повертає 1, якщо розряди в операндів різні: один — 0, інший — 1. Якщо обидва розряди однакові (обидва 0 або обидва 1) — результат 0.

Ця операція має цікаву властивість: якщо застосувати XOR двічі з тим самим ключем, отримаємо вихідне значення. Саме на цьому ґрунтується найпростіший алгоритм симетричного шифрування:

Перше застосування XOR «змішує» число з ключем. Друге застосування того самого XOR з тим самим ключем відновлює оригінал. Це відбувається тому, що (x ^ k) ^ k = x — XOR сам є своєю оберненою операцією.

Побітове заперечення — операція `~`

Операція ~ (NOT, інверсія) є унарною — вона приймає один операнд і інвертує всі його розряди: 0 стає 1, 1 стає 0. Для числа 12 (двійк. 00001100) результатом буде 11110011:

Результат –13 пояснюється тим, як у C# зберігаються від'ємні цілі числа.

Подання від'ємних чисел: додатковий код

У C# для знакових цілих типів застосовується додатковий код (two's complement). У цій системі старший (лівий) розряд є знаковим: якщо він 0 — число додатне, якщо 1 — від'ємне. Решта розрядів разом зі знаковим кодують величину числа у спеціальному форматі.

Щоб отримати від'ємне число з позитивного, виконують два кроки: інвертують усі розряди (~x) і додають одиницю. Тому -12 представляється як ~12 + 1:

Саме тому ~12 дає не просто «інвертовані біти» як беззнакове число, а -13: інверсія 12 дає двійкове значення, яке в signed-форматі читається як -13. Тобто ~x = -(x + 1) — ця формула точно описує поведінку NOT для будь-якого знакового цілого.

Операції зсуву: `<<` і `>>`

Операції зсуву переміщують усі біти числа вліво або вправо на задану кількість позицій.

Зсув вліво << додає праворуч нулі, «вштовхуючи» біти числа ліворуч. Кожне зміщення на одну позицію вліво рівнозначне множенню на 2. Зсув на n позицій — множенню на 2ⁿ:

Зсув вправо >> переміщує біти праворуч; відповідні ліві позиції заповнюються знаковим бітом (для від'ємних чисел — одиницями, для додатних — нулями). Кожне зміщення вправо рівнозначне цілочисленному діленню на 2:

Зсув є більш ефективним, ніж арифметичне ділення або множення, оскільки процесор виконує його за одну команду. Проте використовувати зсуви замість * і / варто лише там, де це справді критично для продуктивності — в решті випадків ясність коду важливіша.

Розглянемо зсув числа, яке не є степенем двійки:

При зсуві вправо дробова частина ділення втрачається — так само, як і при цілочисленному поділі. Тому 22 >> 2 дає 5, а не 5.5.