Викия

Математика

Битовые операции

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Битовые операции, иногда также булевы или логические операции[1] — операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике.

ВведениеПравить

Булевы операции и математическая логикаПравить

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

Однако, связкам математической логики более соответствуют логические операции в т.ч. в программировании, нежели собственно битовые операции.

Булевы операции как основа цифровой техникиПравить

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


Перечисление битовых операцийПравить

ИПравить

Файл:ANDGate2.png

«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.

В булевой логике: \land В языке C: &

Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.


НЕПравить

Файл:NOTGate2.png

«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике.

В булевой логике: \neg В языке C: ~

Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.


ИЛИПравить

Файл:ORGate2.png

«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.

В булевой логике: \lor В языке C: |

Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.

Исключающее ИЛИПравить

Файл:XOR.jpg

«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.

В булевой логике: \oplus В языке C: ^

Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».

Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ» данная операция является обратимой, или инволютивной: (x\oplus y)\oplus y = x.

В графике «исключающее ИЛИ» применяется при выводе спрайтов на картинку — повторное её применение убирает спрайт с картинки. Благодаря инволютивности же эта операция нашла применение в криптографии как простейшая реализация идеального шифра.


Операции от многих аргументовПравить

Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).


Прочие бинарные операцииПравить

Файл:NOR.jpg

«ИЛИ-НЕ» (nor), она же «стрелка Пирса».

См. также основную статью: Стрелка Пирса
В булевой логике: \downarrow

Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.


Файл:NAND.jpg

«И-НЕ» (nand), она же «штрих Шеффера».

В булевой логике: \mid

Двойственная стрелке Пирса операция: является результатом инвертирования результата «И» своих аргументов, выдаёт значение 0 только когда оба входа 1. Известна простотой реализации в ТТЛ.


Импликация («если-то») — аналог импликации в логике.

В булевой логике: \subset

Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое \le (меньше или равно).


Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.

Сводная таблица истинности булевых операцийПравить

Название И/AND НЕ/NOT ИЛИ/OR искл. ИЛИ/XOR импл. стрелка
Пирса
штрих
Шеффера
x y & (x\land y) ~x (\neg) | (x\lor y) ^ (x\oplus y) x\to y (x\subset y) x\downarrow y x\mid y
0 0 0 1 0 0 1 1 1
0 1 0 1 1 1 1 0 1
1 0 0 0 1 1 0 0 1
1 1 1 0 1 0 1 0 0

Операции над битовыми векторамиПравить

Обобщение операций на булеву алгебруПравить

Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов (в программировании их называют регистрами), например, байты. В программировании регистры рассматривают как двоичное разложение целого числа: b = b_0 + 2 b_1 + 2^2 b_2 + ... + 2^{N-1} b_{N-1}, где N — количество битов в регистре.

Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операция от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т.д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из -1 (~x == -1-x). Однако, они очень полезны в программировании.

Битовые сдвиги Править

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

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

Файл:Rotate right logically.svg
Файл:Rotate right arithmetically.svg
Файл:Rotate right.svg
Файл:Rotate right through carry.svg

Логический сдвиг Править

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

Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.

Арифметический сдвиг Править

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

Циклический сдвиг Править

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

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

2-адическая интерпретацияПравить

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

Практические примененияПравить

Физическая реализация битовых операцийПравить

Наиболее распространены электронные реализации битовых операций при помощи транзисторов, например транзисторно-транзисторная логика и КМОП; в первой половине XX века вместо транзисторов применяли электронные лампы. Однако, реализация битовых операций может в принципе быть любой: механической, электромеханической, гидравлической или пневматической, оптической и даже химической.

В квантовых вычислениях из перечисленных булевых операций реализуются только НЕ и искл. ИЛИ (с некоторыми оговорками). Квантовых аналогов И, ИЛИ и т.д. не существует.


Схемы аппаратной логикиПравить

Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой.

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


Использование в программированииПравить

Благодаря реализации в схеме процессора, ряд регистровых битовых операций программно доступен в языках низкого уровня, а также в языке C. В большинстве процессоров реализованы в качестве элементарной операции регистровый НЕ, регистровые двухаргументные И, ИЛИ, искл. ИЛИ, проверка равенства нулю (см. выше), все три типа битовых сдвигов (а заодно и циклические битовые сдвиги).

Регистровая операция И используется для сброса конкретного бита, ИЛИ — для установки, искл. ИЛИ — для инвертирования (т.е. для проведения операции НЕ над конкретным битом с сохранением остальных нетронутыми). Регистровый И с последующей проверкой равенства нулю используется для чтения значения конкретного бита.

Операция И также используется для наложения маски — например, в IP-адресации (хотя не только).


Примечания Править

Шаблон:Reflist

СсылкиПравить

cs:Bitový operátoreo:Laŭbita logikovi:Phép toán thao tác bit
Ошибка цитирования Для существующего тега <ref> не найдено соответствующего тега <references/>

Викия-сеть

Случайная вики