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

Не слід плутати з булевою функцією.

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

Побітові логічні операції

Ряд джерел за мовами низького рівня називає побітові логічні операції просто логічними, але в термінології програмування на мовах високого рівня в назвах бітових операцій присутні прикметники бітовий, побітовий (наприклад: «побітове логічне І», воно ж «побітове множення»), порозрядний. У деяких мовах програмування назви операторів, відповідних логічним та побітовим логічним операціям, схожі. Крім того, мова програмування може допускати неявне приведення числового типу до логічного та навпаки. У таких мовах програмування необхідно уважно стежити за використанням логічних та побітових операцій, перемішування яких може призвести до помилок. Наприклад, в C++ результатом виразу «2 && 1» (логічне І) є булеве значення true, а результатом виразу «2 & 1» (побітове І) — ціле 0.

Побітове заперечення (NOT)

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

НЕ	01
	10

Побітове І (AND)

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

І	0011
	0101
	0001

Побітове АБО (OR)

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

АБО	0011
	0101
	0111

Додавання за модулем два (XOR)

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

Викл. АБО	0011
	0101
	0110

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

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

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

Інші побітові логічні операції

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

Бітові зсуви

Логічний зсув праворуч

Арифметичний зсув праворуч

Циклічний зсув

Циклічний зсув через біт переносу

До бітових операцій також відносять бітові зсуви. При зсуві значення бітів копіюються в сусідні за напрямом зсуву. Розрізняють декілька видів зсувів — логічний, арифметичний і циклічний , залежно від обробки крайніх бітів.

Також розрізняють зсув ліворуч (в напрямку від молодшого біта до старшого) і праворуч (в напрямку від старшого біта до молодшого).

Логічний зсув

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

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

Арифметичний зсув

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

Циклічний зсув

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

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

У мовах програмування

У наступній таблиці для деяких мов програмування наведено вбудовані оператори та функції, що реалізують побітові логічні операції.

Мова	НЕ	І	АБО	Викл. АБО	Зсув ліворуч	Зсув праворуч	Інші
C/С++, Java, C#, Ruby, Python	~	&	|	^	<<	>>
JavaScript, Julia					<<	>>, >>>
Pascal, Delphi	not	and	or	xor	shl	shr
PL/I	INOT	IAND	IOR	IEOR			BOOL
	¬	&	|	¬
Prolog	\	/\	\/
Ocaml					lsl	lsr
Assembler					shl	shr
VHDL					sll	srl

В теорії складності алгоритмів

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

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

Зв'язок з іншими науками

Бітові операції та математична логіка

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

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

Узагальнення операцій на булеву алгебру

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

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

2-адична інтерпретація

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

Бітові операції як основа цифрової техніки

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

Практичні застосування

З точки зору застосування окрема бітова операція мало цікава. Тому практичне застосування ґрунтується на способах комбінування різних бітових операцій, для реалізації більш складного обчислення. Можна відзначити два аспекти:

1. збільшення розміру регістрів, в яких бітові операції виконуються не по одній, а одразу на безлічі 8, 16, 32, 64 бітах
2. експериментальні пристрої, де узагальнюють бітові операції з двійкової системи, на трійчастий та інші системи числення (так наприклад, розроблена теорія роботи з четверичною системою (ДНК-комп'ютер), Так само робляться дослідження в області квантового комп'ютера).

Фізична реалізація бітових операцій

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

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

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

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

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

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

Схеми апаратної логіки

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

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

Використання в програмуванні

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

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

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

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

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

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

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

Див. також

• Біт
• Двійкова система числення
• Логічні елементи
• Комбінаційна логіка