- Побітове заперечення (NOT) [ правити | правити код ]
- Побітове «І» (AND) [ правити | правити код ]
- Побітове «АБО» (OR) [ правити | правити код ]
- Що виключає «АБО» (XOR) [ правити | правити код ]
- Інші побітові логічні операції [ правити | правити код ]
- Логічний зсув [ правити | правити код ]
- Арифметичний зрушення [ правити | правити код ]
- Циклічний зсув [ правити | правити код ]
- У мовах програмування [ правити | правити код ]
- Бітові операції і математична логіка [ правити | правити код ]
- Узагальнення операцій на булеву алгебру [ правити | правити код ]
- 2-адіческая інтерпретація [ правити | правити код ]
- Бітові операції як основа цифрової техніки [ правити | правити код ]
- Фізична реалізація бітових операцій [ правити | правити код ]
- Схеми апаратної логіки [ правити | правити код ]
- Використання в програмуванні [ правити | правити код ]
open wikipedia design.
Бітова операція в програмуванні - деякі операції над ланцюжками бітів . У програмуванні, як правило, розглядаються лише деякі види цих операцій: логічні побітові операції і бітові зрушення . Бітові операції застосовуються в мовах програмування і цифрову техніку , Вивчаються в дискретної математики .
Ряд джерел по мовам низького рівня називає побітові логічні операції просто логічними [1] [2] , Але в термінології програмування на мовах високого рівня в назвах бітових операцій присутні прикметники бітовий, побітовий (наприклад: «побітовое логічне І », Воно ж« побітовое множення »), порозрядному.
У деяких мовах програмування назви операторів, відповідних логічним і побітовим логічним операціям, схожі. Крім того, мова програмування може допускати неявне приведення числового типу до логічного і навпаки. У таких мовах програмування необхідно уважно стежити за використанням логічних і побітових операцій, перемішування яких може привести до помилок. Наприклад, в C ++ результатом виразу «2 && 1» (логічне І) є логічне значення true, а результатом виразу «2 & 1» (побітовое І) - ціле значення 0.
Побітове заперечення (NOT) [ правити | правити код ]
Побітове заперечення (або побітове НЕ, або доповнення) - це унарна операція , Дія якої еквівалентно застосуванню логічного заперечення до кожного біту двійкового представлення операнда. Іншими словами, на тій позиції, де в двійковому поданні операнда був 0, в результаті буде 1, і, навпаки, де була 1, там буде 0. Наприклад:
Побітове «І» (AND) [ правити | правити код ]
Побітове «І» - це бінарна операція , Дія якої еквівалентно застосуванню логічного «І» до кожної пари бітів, які стоять на однакових позиціях в довічних уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 1, результуючий двійковий розряд дорівнює 1; якщо ж хоча б один біт з пари дорівнює 0, результуючий двійковий розряд дорівнює 0.
Приклад.
Побітове «АБО» (OR) [ правити | правити код ]
Побітове «АБО» - це бінарна операція , Дія якої еквівалентно застосуванню логічного «АБО» до кожної пари бітів, які стоять на однакових позиціях в довічних уявленнях операндів. Іншими словами, якщо обидва відповідних біта операндів рівні 0, двійковий розряд результату дорівнює 0; якщо ж хоча б один біт з пари дорівнює 1, двійковий розряд результату дорівнює 1.
Приклад.
Що виключає «АБО» (XOR) [ правити | правити код ]
Що виключає «АБО» (або додавання по модулю 2) - це бінарна операція , Результат дії якої дорівнює 1, якщо число що складаються одиничних бітів непарній, і дорівнює 0, якщо парне. Іншими словами, якщо обидва відповідних біта операндів рівні між собою, двійковий розряд результату дорівнює 0; в іншому випадку, двійковий розряд результату дорівнює 1.
Приклад.
Викл. АБО 0011 0101 0110
Перше російське назва операції обумовлено тим, що результат цієї операції відрізняється від результату «АБО» тільки в одному випадку з 4 випадків входу - обох 1 (випадок одночасної істинності аргументів «виключається»). Ще в русской грамматике значення даної логічної зв'язки передається союзом «Або».
Друга назва - тим, що дійсно є складанням в кільці відрахувань по модулю два, з чого слідують деякі цікаві властивості. Наприклад, на відміну від вищеописаних «І» та «АБО», дана операція є оборотною, або інволютивно: (x ⊕ y) ⊕ y = x {\ displaystyle (x \ oplus y) \ oplus y = x} 
В комп'ютерній графіці «Складання по модулю два» застосовується при виведенні спрайтів на картинку - повторне її застосування прибирає спрайт з картинки. Завдяки інволютивними ця ж операція знайшла застосування в криптографії як найпростіша реалізація абсолютно стійкого шифру ( шифру Вернама ). «Складання по модулю два» також може використовуватися для обміну двох змінних, використовуючи алгоритм обміну за допомогою виключає АБО .
Також дана операція може називатися «інверсією по масці», тобто у вихідного двійкового числа інвертуються біти, які збігаються з 1 в масці.
Інші побітові логічні операції [ правити | правити код ]
У поширених мовах програмування вбудованими засобами реалізуються тільки чотири побітові логічні операції: І, АБО, НЕ і виключає АБО. Для завдання довільної побітової логічної операції цілком достатньо перерахованих, і, більш того, як випливає з теорії булевих функцій, можна обмежитися ще меншим набором базових операцій. Є також мови програмування, де існує вбудована можливість виконати будь-яку бінарну логічну операцію побитово. Наприклад, в PL / I є вбудована функція BOOL, третій аргумент якої призначений для вказівки довільної логічної операції, яку необхідно побитово застосувати до перших двох аргументів [3] .
До бітових операцій також відносять бітові зрушення. При зсуві значення бітів копіюються в сусідні по напрямку зсуву. Розрізняють декілька видів зрушень - логічний, арифметичний і циклічний, в залежності від обробки крайніх бітів.
Також розрізняють зрушення вліво (в напрямку від молодшого біта до старшого) і вправо (в напрямі від старшого біта до молодшого).
Логічний зсув [ правити | правити код ]
При логічному зсуві значення останнього біта у напрямку зсуву втрачається (копіюємо в біт переносу), а перший набуває нульове значення.
Арифметичний зрушення [ правити | правити код ]
Арифметичний зрушення аналогічний логічному, але число вважається знаковим, представленим в додатковому коді. Так, при правом зсуві старший біт зберігає своє значення. Лівий арифметичний зрушення ідентичний логічного.
Арифметичні зрушення вліво і вправо використовуються для швидкого множення і ділення на 2.
Циклічний зсув [ правити | правити код ]
При циклічному зсуві, значення останнього біта у напрямку зсуву копіюється в перший біт (і копіюється в біт переносу).
Також розрізняють циклічний зсув через біт перенесення - при ньому перший біт у напрямку зсуву отримує значення з біта перенесення, а значення останнього біта зсувається в біт переносу.
У мовах програмування [ правити | правити код ]
У наступній таблиці для деяких мов програмування наведені вбудовані оператори та функції, що реалізують побітові логічні операції.
Термін бітова операція, часто використовується в області обчислень так званих швидких алгоритмів , Які вивчають алгоритми обчислення заданої функції з заданою точністю з використанням якомога меншої кількості бітових операцій.
Бітова операція в теорії алгоритмів запис знаків 0, 1, плюс, мінус, дужка; додавання, віднімання і множення двох бітів (числа записані в двійковій системі числення) [9] [10] . Використовується для оцінки складності алгоритму .
Бітові операції і математична логіка [ правити | правити код ]
Бітові операції дуже близькі (хоча і не тотожні) логічним зв'язкам в класичній логіці . Біт можна розглядати як логічне судження - його значеннями є 1 «істина» і 0 «брехня». При такій інтерпретації відомі в логіці зв'язки кон'юнкції , диз'юнкції , імплікації , заперечення і інші мають уявлення мовою бітів. І навпаки, бітові операції легко описуються на мові обчислення висловлювань .
Однак, зв'язкам математичної логіки більш відповідають логічні операції в тому числі в програмуванні, ніж власне бітові операції.
Узагальнення операцій на булеву алгебру [ правити | правити код ]
Замість одиночних бітів ми можемо розглянути вектори з фіксованої кількості бітів (в програмуванні їх називають регістрами), наприклад, байти . У програмуванні регістри розглядають як двійкове розкладання цілого числа: b = b 0 + 2 b 1 + 2 + 2 b 2 +. . . + 2 N - 1 b N - 1 {\ displaystyle b = b_ {0} + 2b_ {1} + 2 ^ {2} b_ {2} + ... + 2 ^ {N-1} b_ {N-1 }} 
Проте, ніщо не заважає розглядати ці регістри саме як бітові вектори і проводити булеві операції покомпонентно (біт номер k значення є результат операції від бітів номер k аргументів). До речі, математично кажучи, булеві операції поширюються таким чином на довільну булеву алгебру . Таким чином ми отримуємо операції побітового І, АБО, НЕ, викл. АБО і т. Д. Як арифметичні, дані операції не володіють хорошими властивостями за винятком побітового НЕ, яке для чисел в додатковому коді збігається з вирахуванням з -1 (~ x == -1-x). Однак, вони дуже корисні в програмуванні.
2-адіческая інтерпретація [ правити | правити код ]
Ціле число, записане (в додатковому коді) в нескінченний (в сторону позитивних ступенів двійки) двійковий регістр є природним об'єктом для теорії p-адіческіх чисел при p = 2 {\ displaystyle p = 2} 
Бітові операції як основа цифрової техніки [ правити | правити код ]
Бітові операції лежать в основі обробки цифрових сигналів . А саме, за допомогою них ми можемо з одного або декількох сигналів на вході отримати новий сигнал, який в свою чергу може бути поданий на вхід одній або кільком таким операціям. По суті, саме бітові операції в поєднанні з пристроями, що запам'ятовують елементами (напр. тригерами ) Реалізують все багатство можливостей сучасної цифрової техніки.
З точки зору застосування окрема бітова операція мало цікава. Тому практичне застосування ґрунтується на способах комбінування різних бітових операцій, для реалізації більш складного обчислення. Можна відзначити два аспекти:
- збільшення розміру регістрів, в яких бітові операції виконуються не по одній, а відразу на безлічі 8, 16, 32, 64 бітах
- експериментальні пристрої, де узагальнюють бітові операції з двійкової системи, на трійчастий та інші системи числення (так наприклад, розроблена теорія роботи з четверичной системою ( ДНК-комп'ютер ), Так само робляться дослідження в області квантового комп'ютера ).
Фізична реалізація бітових операцій [ правити | правити код ]
Реалізація бітових операцій може в принципі бути будь-який: механічної (в тому числі гідравлічної і пневматичної), хімічної, теплової, [11] електричної, магнітної та електромагнітної (діапазони - ІК, видимий оптичний, УФ і далі за зменшенням довжин хвиль), а також у вигляді комбінацій, наприклад, електромеханічної .
У першій половині XX століття до винаходу транзисторів застосовували електромеханічні реле і електронні лампи .
В пожежонебезпечних і вибухонебезпечних умовах досі застосовують пневматичні логічні пристрої (Пневмоніка).
найбільш поширені електронні реалізації бітових операцій за допомогою транзисторів , наприклад резисторно-транзисторна логіка (РТЛ), діод-транзисторна логіка (ДТЛ), емітерний-пов'язана логіка (ЕСЛ), транзисторних-транзисторна логіка (ТТЛ), N-МОП -логіка, КМОП -логіка і ін.
В квантових обчисленнях з перерахованих булевих операцій реалізуються тільки НЕ і викл. АБО (з деякими застереженнями). Квантових аналогів І, АБО і т. Д. Не існує.
Схеми апаратної логіки [ правити | правити код ]
Результат операції АБО-НЕ або АБО від всіх бітів двійкового регістра перевіряє, чи дорівнює значення регістра нулю; те ж саме, взяте від виходу викл. АБО двох регістрів, перевіряє рівність їх значень між собою.
Бітові операції застосовуються в знакогенератор і графічних адаптерів ; особливо велика була їх роль в адаптері EGA в режимах з 16 квітами - хитромудре поєднання апаратної логіки адаптера з логічними командами центрального процесора дозволяє розглядати EGA як перший в історії графічний прискорювач .
Використання в програмуванні [ правити | правити код ]
Завдяки реалізації в арифметичному логічному пристрої ( АЛУ ) процесора багато реєстрові бітові операції апаратно доступні в мовах низького рівня . У більшості процесорів реалізовано в якості інструкції регістровий НЕ; реєстрові двухаргументние І, АБО, що виключає АБО; перевірка рівності нулю (див. вище); три типи бітових зрушень, а також циклічні бітові зрушення.
Реєстрова операція І використовується для:
- перевірки біта на 0 або 1
- установки 0 в зазначений біт (скидання біта)
Реєстрова операція АБО використовується для:
- установки 1 в зазначений біт
Реєстрова операція виключає АБО використовується для інвертування бітів регістра по масці.
Зрушення вліво / вправо використовується для множення / цілочисельного ділення на 2 і виділення окремих бітів.
Так, наприклад, в мережевих інтернет-технологіях операція І між значенням IP-адреси і значенням маски підмережі використовується для визначення приналежності цієї адреси до підмережі.
