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

  1. Побітове заперечення (NOT) [ правити | правити код ]
  2. Побітове «І» (AND) [ правити | правити код ]
  3. Побітове «АБО» (OR) [ правити | правити код ]
  4. Що виключає «АБО» (XOR) [ правити | правити код ]
  5. Інші побітові логічні операції [ правити | правити код ]
  6. Логічний зсув [ правити | правити код ]
  7. Арифметичний зрушення [ правити | правити код ]
  8. Циклічний зсув [ правити | правити код ]
  9. У мовах програмування [ правити | правити код ]
  10. Бітові операції і математична логіка [ правити | правити код ]
  11. Узагальнення операцій на булеву алгебру [ правити | правити код ]
  12. 2-адіческая інтерпретація [ правити | правити код ]
  13. Бітові операції як основа цифрової техніки [ правити | правити код ]
  14. Фізична реалізація бітових операцій [ правити | правити код ]
  15. Схеми апаратної логіки [ правити | правити код ]
  16. Використання в програмуванні [ правити | правити код ]

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 }} Замість одиночних бітів ми можемо розглянути вектори з фіксованої кількості бітів (в програмуванні їх називають регістрами), наприклад,   байти , Де N - кількість бітів в регістрі.

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

2-адіческая інтерпретація [ правити | правити код ]

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

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

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

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

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

Фізична реалізація бітових операцій [ правити | правити код ]

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

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

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

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

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

Схеми апаратної логіки [ правити | правити код ]

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

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

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

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

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

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

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

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

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

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

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