Перегляд вихідного коду сторінки Бітові операції

{{Refimprove|date=вересень 2016}}
{{не плутати|Булева функція|булевою функцією}}
'''Бітова операція в програмуванні'''&nbsp;— деякі [[Оператор (програмування)|операції]] над [[Бітова мапа|ланцюжками бітів]]. У програмуванні, як правило, розглядаються лише деякі види цих операцій: логічні побітові операції та [[Бітовий зсув|бітові зсуви]]. Бітові операції застосовуються в [[Мова програмування|мовах програмування]] та [[Електроніка|цифровій техніці]], вивчаються в [[Дискретна математика|дискретній математиці]].

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

=== Побітове заперечення (NOT) {{anchor|NOT|НЕ}} ===
'''Побітове заперечення''' (або '''побітове НЕ''', або '''доповнення''')&nbsp;— це [[унарна операція]], дія якої еквівалентна застосуванню [[заперечення|логічного заперечення]] до кожного біту двійкового подання операнда. Іншими словами, на тій позиції, де в двійковому поданні операнда був 0, внаслідок буде 1, і, навпаки, де була 1, там буде 0. <br/>
Приклад:
{|class="standard"
|class="shadow"|НЕ||01
|-
|colspan="2"|
|-
| ||10
|}

=== Побітове І (AND) {{anchor|AND|І}} ===
'''Побітове І'''&nbsp;— це [[бінарна операція]], дія якої еквівалентно застосування [[кон'юнкція|логічного І]] до кожної пари бітів, які стоять на однакових позиціях у двійкових уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 1, результуючий двійковий розряд дорівнює 1, якщо ж хоча б один біт з пари дорівнює 0, результуючий двійковий розряд дорівнює 0.<br/>
Приклад:
{|class="standard"
|class="shadow" rowspan=2|І||0011
|-
|0101
|-
|colspan="2"|
|-
| ||0001
|}

=== Побітове АБО (OR) {{anchor|OR|АБО}} ===
'''Побітове АБО'''&nbsp;— це [[бінарна операція]], дія якої еквівалентно застосування [[диз'юнкція (логіка)|логічного АБО]] до кожної пари бітів, які стоять на однакових позиціях у двійкових уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 0, двійковий розряд результату дорівнює 0, якщо ж хоча б один біт з пари дорівнює 1, двійковий розряд результату дорівнює 1.<br/>
Приклад:
{|class="standard"
|class="shadow" rowspan=2|АБО||0011
|-
|0101
|-
|colspan="2"|
|-
| ||0111
|}

=== Додавання за модулем два (XOR) {{anchor|XOR|}} ===
{{main|Додавання за модулем два}}

'''Додавання за модулем два''' (або '''двомісна операція виключне АБО''')&nbsp;— це [[бінарна операція]], результат дії якої дорівнює 1, якщо число складаємих одиничних бітів непарне, якщо ж їх число парне, то результат дорівнює 0.<br/>
Приклад:
{|class="standard"
|class="shadow" rowspan=2|Викл. АБО||0011
|-
|0101
|-
|colspan="2"|
|-
| ||0110
|}
Перша назва операції обумовлена тим, що результат цієї операції відрізняється від результату «АБО» лише в одному з 4 випадків входу (1 випадок одночасної істинності аргументів «виключається»). Ще значення цієї логічної зв'язки передається [[Сполучник|союзом]] «або».

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

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

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

== Бітові зсуви ==
{{Головна|Бітовий зсув}}
{{Multiple image |width=160 |align=right |direction=vertical
 |image1=Rotate right logically.svg |caption1=Логічний зсув праворуч
 |image2=Rotate right arithmetically.svg |caption2=Арифметичний зсув праворуч
 |image3=Rotate right.svg |caption3=Циклічний зсув
 |image4=Rotate right through carry.svg |caption4=Циклічний зсув через [[біт переносу]]
}}
До бітових операцій також відносять бітові зсуви. При зсуві значення бітів копіюються в сусідні за напрямом зсуву. Розрізняють декілька видів зсувів&nbsp;— ''логічний'', ''арифметичний '' і'' циклічний '', залежно від обробки крайніх бітів.
 
Також розрізняють зсув ''ліворуч'' (в напрямку від [[Молодший значущий розряд|молодшого]] біта до [[Старший біт|старшого]]) і ''праворуч'' (в напрямку від старшого біта до молодшого).

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

Логічні зсуви на одиницю ліворуч та праворуч використовуються для множення та ділення на 2, відповідно. І на степінь двійки якщо зсув не на одиницю. Завдяки тому, що зсув займає менше тактів процесора ніж множення, його використовували замість множення чи ділення на степінь двійки. Але з сучасними оптимізованими компіляторами така діяльність небажана через можливість помилок.<ref>{{cite web|last=Steele Jr|first=Guy|title=Arithmetic Shifting Considered Harmful|url=http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf|publisher=MIT AI Lab|accessdate=20 травня 2013|archive-date=6 грудня 2014|archive-url=https://web.archive.org/web/20141206174706/http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf}}</ref>

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

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

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

== У мовах програмування ==
У наступній таблиці для деяких мов програмування наведено вбудовані оператори та функції, що реалізують побітові логічні операції.
{|class="standard"
!class="bright"|Мова||НЕ||І||АБО||Викл. АБО||Зсув ліворуч||Зсув праворуч||Інші
|-align="center"
!style="font-weight: normal"|[[C (мова програмування)|C]]/[[C++|С++]], [[Java]], [[C Sharp|C#]], [[Ruby]], [[Python]]<ref>{{Cite web |url=https://wiki.python.org/moin/BitwiseOperators |title=Архівована копія |accessdate=29 грудня 2017 |archive-date=29 вересня 2020 |archive-url=https://web.archive.org/web/20200929223632/https://wiki.python.org/moin/BitwiseOperators }}</ref>
|~||&amp;||<nowiki>|</nowiki>||^||<<||>>||class=shadow|
|-align="center"
!style="font-weight: normal"| [[JavaScript]], [[Julia]]
|class=shadow| ||class=shadow| ||class=shadow| ||class=shadow| || <tt><<</tt> || <tt>{{Comment|>>|арифметичний}}</tt>, <tt>{{Comment|>>>|логічний}}</tt><ref>[https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#Unsigned_right_shift Bitwise operators] {{Webarchive|url=https://web.archive.org/web/20151118225547/https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#Unsigned_right_shift |date=18 листопада 2015 }} [[MDN]]</ref>
|-align="center"
!style="font-weight: normal"|[[Pascal]], [[Borland Delphi|Delphi]]
|not||and||or||xor||shl||shr||class=shadow|
|-align="center"
!rowspan="2" style="font-weight: normal"|PL/I
|INOT||IAND||IOR||IEOR||class=shadow| ||class=shadow| ||rowspan="2"|BOOL
|-align="center"
|¬||&amp;||<nowiki>|</nowiki>||¬||class=shadow| ||class=shadow|
|-align="center"
!style="font-weight: normal"|Prolog
|\||/\||\/||class=shadow| ||class=shadow| ||class=shadow| ||class=shadow|
|-align="center"
!style="font-weight: normal"| [[Ocaml]]
|class=shadow| ||class=shadow| ||class=shadow| ||class=shadow| || <tt>lsl</tt> || <tt>lsr</tt>
|-align="center"
!style="font-weight: normal"| [[Assembler]]
|class=shadow| ||class=shadow| ||class=shadow| ||class=shadow| || <tt>shl</tt> || <tt>shr</tt> 
|-align="center"
!style="font-weight: normal"| [[VHDL]]
|class=shadow| ||class=shadow| ||class=shadow| ||class=shadow| || <tt>sll</tt> || <tt>srl</tt>
|}

== В теорії складності алгоритмів ==
{{main|Теорія складності обчислень}}

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

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

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

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

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

==== Узагальнення операцій на булеву алгебру ====
Замість поодиноких бітів ми можемо розглянути вектори з фіксованої кількості бітів (в програмуванні їх називають регістрами), наприклад, [[байт]]и.
У програмуванні регістри розглядають як двійкове розкладання цілого числа: <math>b = b_0 + 2 b_1 + 2^2 b_2 +... + 2^{N-1} b_{N-1}</math>, де ''N''&nbsp;— кількість бітів у регістрі.

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

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

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

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

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

З точки зору застосування окрема бітова операція мало цікава. Тому практичне застосування ґрунтується на способах комбінування різних бітових операцій, для реалізації більш складного обчислення. Можна відзначити два аспекти:
# збільшення розміру регістрів, в яких бітові операції виконуються не по одній, а одразу на безлічі 8, 16, 32, 64 бітах
# експериментальні пристрої, де узагальнюють бітові операції з двійкової системи, на трійчастий та інші системи числення (так наприклад, розроблена теорія роботи з четверичною системою ([[ДНК-комп'ютер]]), Так само робляться дослідження в області [[Квантовий комп'ютер|квантового комп'ютера]]).

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

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

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

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

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

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

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

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

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

Регістрова операція І використовується для:
* перевірки біта на 0 або 1
* установки 0 у вказаний біт (скидання біта)

Регістрова операція АБО використовується:
* установки 1 у вказаний біт

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

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

== Див. також ==
* [[Біт]]
* [[Двійкова система числення]]
* [[Логічні елементи]]
* [[Комбінаційна логіка]]

== Примітки ==
{{reflist}}

[[Категорія:Булева алгебра]]
[[Категорія:Двійкова арифметика]]
[[Категорія:Операції (програмування)]]