Бітові операції

Побітове заперечення (або побітове НЕ, або доповнення) — це унарна операція, дія якої еквівалентна застосуванню логічного заперечення до кожного біту двійкового подання операнда. Іншими словами, на тій позиції, де в двійковому поданні операнда був 0, внаслідок буде 1, і, навпаки, де була 1, там буде 0.
Приклад:

Побітове І — це бінарна операція, дія якої еквівалентно застосування логічного І до кожної пари бітів, які стоять на однакових позиціях у двійкових уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 1, результуючий двійковий розряд дорівнює 1, якщо ж хоча б один біт з пари дорівнює 0, результуючий двійковий розряд дорівнює 0.
Приклад:

Побітове АБО — це бінарна операція, дія якої еквівалентно застосування логічного АБО до кожної пари бітів, які стоять на однакових позиціях у двійкових уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 0, двійковий розряд результату дорівнює 0, якщо ж хоча б один біт з пари дорівнює 1, двійковий розряд результату дорівнює 1.
Приклад:

Додавання за модулем два (або двомісна операція виключне АБО) — це бінарна операція, результат дії якої дорівнює 1, якщо число складаємих одиничних бітів непарне, якщо ж їх число парне, то результат дорівнює 0.
Приклад:

Перша назва операції обумовлена тим, що результат цієї операції відрізняється від результату «АБО» лише в одному з 4 випадків входу (1 випадок одночасної істинності аргументів «виключається»). Ще значення цієї логічної зв'язки передається союзом «або».

Друга назва — тим, що дійсно є складанням в кільці вирахувань за модулем два, з чого слідують деякі цікаві властивості. Наприклад, на відміну від вищеописаних «І» та «АБО», ця операція є оборотною, або інволютивною: ${\displaystyle (x\oplus y)\oplus y=x}$. В комп'ютерній графіці «додавання по модулю два» застосовується при виведенні спрайтів на картинку — повторне її застосування прибирає спрайт з картинки. Завдяки інволютивності ця ж операція знайшла застосування в криптографії як найпростіша реалізація ідеального шифру (шифру Вернама). «Додавання за модулем два» також може використовуватися для обміну двох змінних значеннями, використовуючи алгоритм обміну XOR.

Також ця операція може називатися «інверсією по масці», тобто у вихідного двійкового числа інвертуються біти, які збігаються з 1 в масці.

У поширених мовах програмування вбудованими засобами реалізуються лише чотири побітові логічні операції: І, АБО, НЕ і виключне АБО. Для завдання довільної побітовій логічної операції цілком достатньо перерахованих, і, більше того, як випливає з теорії булевих функцій, можна обмежитися ще меншим набором базових операцій. Є також мови програмування, де існує вбудована можливість виконати будь-яку бінарну логічну операцію побітово. Наприклад, в PL/I є вбудована функція BOOL, третій аргумент якої призначено для вказівки довільної логічної операції, яку необхідно побітово застосувати до перших двох аргументів.

При логічному зсуві значення останнього біта за напрямом зсуву втрачається (копіюємо в біт перенесення), а перший набуває нульове значення.

Логічні зсуви на одиницю вліво та вправо використовуються для множення та ділення на 2, відповідно. І на степінь двійки якщо зсув не на одиницю. Завдяки тому, що зсув займає менше тактів процесора ніж множення, його використовували замість множення чи ділення на степінь двійки. Але з сучасними оптимізованими компіляторами така діяльність небажана через можливість помилок.[1]

Арифметичний зсув аналогічний логічному, але значення слова вважається знаковим числом, представленим в додатковому коді. Так, при правому зсуві старший біт зберігає своє значення. Лівий арифметичний зсув ідентичний логічному.

При циклічному зсуві, значення останнього біта за напрямом зсуву копіюється в перший біт (і копіюється в біт переносу).

Також розрізняють циклічний зсув через біт переносу — при ньому перший біт за напрямом зсуву отримує значення з біта переносу, а значення останнього біта зсувається в біт переносу.

Бітові операції дуже близькі (хоча і не тотожні) логічним зв'язкам в класичній логіці. Біт можна розглядати як логічне судження — його значеннями є 1 «істина» і 0 «брехня». При такій інтерпретації відомі в логіці зв'язки кон'юнкції, диз'юнкції, імплікації, заперечення та інші мають уявлення на мові бітів. І навпаки, бітові операції легко описуються мовою обчислення висловлювань.

Однак, зв'язкам математичної логіки більш відповідають логічні операції у тому числі в програмуванні, ніж власне бітові операції.

Замість поодиноких бітів ми можемо розглянути вектори з фіксованої кількості бітів (в програмуванні їх називають регістрами), наприклад, байти. У програмуванні регістри розглядають як двійкове розкладання цілого числа: ${\displaystyle b=b_{0}+2b_{1}+2^{2}b_{2}+...+2^{N-1}b_{N-1}}$, де N — кількість бітів у регістрі.

Тим не менш, ніщо не заважає розглядати ці регістри саме як бітові вектори та проводити булеві операції покомпонентно (біт номер k значення є результат операції від бітів номер k аргументів). речі, математично кажучи, булеві операції поширюються таким чином на довільну булеву алгебру. Таким чином ми отримуємо операції побітового І, АБО, НЕ, викл. АБО, тощо. Як арифметичні, дані операції не володіють хорошими властивостями за винятком побітового НЕ, яке для чисел в додатковому коді збігається з вирахуванням з-1 (~x ==-1-x). Однак, вони дуже корисні в програмуванні.

Ціле число, записане (в додатковому коді) в нескінченний (в бік додатних ступенів двійки) двійковий регістр є природним об'єктом для теорії p-адичних чисел при ${\displaystyle p=2}$. Множина цілих 2-адичних чисел (тобто довільних нескінченних бітових послідовностей) може бути розглянуте як булева алгебра точно так само як і безліч значень бітового регістра кінцевої довжини. Всі перераховані вище бітові операції виявляються безперервними відображеннями. Хоча практичне програмування не має регістрів нескінченної довжини, це не заважає використовувати цей теоретичний факт в криптографії для створення швидкодійних алгоритмів шифрування.

Бітові операції лежать в основі обробки цифрових сигналів. А саме, за допомогою них ми можемо з одного або декількох сигналів на вході отримати новий сигнал, який у свою чергу може бути поданий на вхід однієї або декільком такими операціями. Власне, саме бітові операції в поєднанні з запам'ятовувальними елементами (напр. тригерами) реалізують все багатство можливостей сучасної цифрової техніки.

Реалізація бітових операцій може в принципі бути будь-який: механічної (в тому числі гідравлічної та пневматичної), хімічною, тепловою, електричної, магнітної та електромагнітної (діапазони — ІК, видимий оптичний, УФ і далі за зменшенням довжин хвиль), а також у вигляді комбінацій, наприклад, електромеханічної.

У першій половині XX століття до винаходу транзисторів застосовували електромеханічні реле та електронні лампи.

У пожежонебезпечних та вибухонебезпечних умовах досі застосовують пневматичні логічні пристрої (пневмоніка).

Найбільш поширені електронні реалізації бітових операцій за допомогою транзисторів, наприклад Резисторно-транзисторна логіка (РТЛ), діод-транзисторна логіка (ДТЛ), емітерний-пов'язана логіка (ЕСЛ), транзисторних-транзисторна логіка (ТТЛ), N-МОП логіка, КМОН логіка і ін

Однією з причин, через яку базові (основні) логічні елементи будують на інвертора, а повторювачі є додатковими елементами, було те, що в електроніці інвертори (ОЕ) могутніше повторювачів (ОК). Але основною причиною є те, що два інвертора замінюють один повторювач, а на повторювачах інвертор не збудувати.

В квантових обчисленнях з перерахованих булевих операцій реалізуються лише НЕ і викл. АБО (з деякими застереженнями). Квантових аналогів І, АБО, тощо. не існує.

Результат операції АБО-НЕ або АБО від усіх бітів двійкового регістра перевіряє, чи дорівнює значення регістра нулю; те ж саме взяте від виходу викл. АБО двох регістрів перевіряє рівність їх значень між собою.

Бітові операції застосовуються в знакогенераторах та графічних адаптерах; особливо велика була їх роль в адаптері EGA в режимах з 16 кольорами — хитромудре поєднання апаратної логіки адаптера з логічними командами центрального процесора дозволяє розглядати EGA як перший в історії графічний прискорювач.

Завдяки реалізації в арифметичному логічному пристрої (АЛУ) процесора чималі їх реєстрові бітові операції апаратно доступні в мовах низького рівня. У більшості процесорів реалізовані як інструкції: регістрове НЕ; реєстрові двохаргументні І, АБО, викл. АБО; перевірка рівності нулю (див. вище); три типи бітових зрушень, а також циклічні бітові зрушення.

Регістрова операція І використовується для:

• перевірки біта на 0 або 1
• установки 0 у вказаний біт (скидання біта)

Регістрова операція АБО використовується:

• установки 1 у вказаний біт

Регістрова операція виключає АБО використовується для інвертування бітів регістра по масці Зрушення вліво/вправо використовується для множення/цілочисельного ділення на 2 і виділення окремих бітів.

Так, наприклад, в мережевих інтернет-технологіях операція І між значенням IP-адреси та значенням маски підмережі використовується для визначення належності цієї адреси до підмережі.