Би́товая опера́ция — математическая операция над одной или несколькими цепочками битов. Обычно такими битовыми цепочками являются числа, представленные в двоичной системе счисления. Битовые операции применяются в программировании и цифровой технике, изучаются в дискретной математике и математической логике.
Введение[]
Булевы операции и математическая логика[]
Булевы операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 "истина" и 0 "ложь". При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний. Однако, связкам математической логики более соответствуют логические операции в том числе в программировании, нежели собственно битовые операции.
Булевы операции как основа цифровой техники[]
Булевы операции лежат в основе обработки цифровых сигналов. А именно, посредством них мы можем из одного или нескольких сигналов на входе получить новый сигнал, который в свою очередь может быть подан на вход одной или нескольким таким операциям. По сути, именно булевы операции в сочетании с запоминающими элементами (напр. триггерами) реализуют всё богатство возможностей современной цифровой техники. == Список битовых операций == ==Нульарные операции (константы)== ==Сводная таблица нульарных операций (констант)== {| class="standard" ! ||||Названия операций|| ||Обозначения |- ! |||| ||Англ.||Знаковые |- |f(0,1,0)2||0 ||тождественный ноль, тождественная ЛОЖЬ ||FALSE ||f(0,1,0)10 = |- |f(0,1,1)2||1 ||тождественная единица, тождественная ИСТИНА ||TRUE ||f(0,1,1)10 = |- |} В номере операции (функции):
первое число - число входов,
второе число - число выходов,
третье число - номер операции (функции), он же результат действия операции (функции).
Двоичный номер операции равен результату операции из таблицы истиности.
== Унарные операции == == Таблица истинности унарных булевых функций == {| class="standard" !Операнды и операции || || ||Названия || ||Обозначения || |- !x ||1||0|| ||Рус. ||Англ. ||Знаковые |- |f(1,1,00)2(x) ||0||0||тождественный ноль ||ЛОЖЬ ||FALSE||f(1,1,0)10(x) = 0(x) = |- |f(1,1,01)2(x) ||0||1||отрицание (негация, инверсия) операнда ||НЕ x ||NOT ||f(1,1,1)10(x) = НЕ(x) = NOT(x) = x' = = = ~x |- |f(1,1,10)2(x) ||1||0||повторение операнда ||ДА x ||YES ||f(1,1,2)10(x)= ДА(x) = YES(x) = x |- |f(1,1,11)2(x) ||1||1||тождественная единица ||ИСТИНА ||TRUE ||f(1,1,3)10(x)= 1(x) = |- |} Двоичный номер операции равен результату операции из таблицы истиности, при этом, порядковый номер двоичного разряда в номере операции равен значению операнда.
В номере операции (функции):
первое число - число входов,
второе число - число выходов,
третье число - номер операции (функции), он же результат действия операции (функции).
=== 0 === Тождественный "0"
f(1,1,00)2(x)=f(1,1,0)10(x)
=== НЕ, НЕТ ===
Инвертор
«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике. Реализующий её элемент называется инвертором (негатором, отрицателем).
f(1,1,01)2(x)=f(1,1,1)10(x)
==== ДА ====
Повторитель (буфер)
"(Логическое) ДА" (yes), повторение — аналог тождественной функции в булевой логике. {| class="wide" align="center" |В булевой логике: |В языке C: |В языке Pascal: |} Данная унарная операция (с одним входом) повторяет входное значение, 0, если 0, 1, если 1. Реализующий её элемент называется повторителем или буферным усилителем.
f(1,1,10)2(x)=f(1,1,2)10(x)
==== 1 ==== Тождественная "1"
f(1,1,11)2(x)=f(1,1,3)10(x)
=== Бинарные операции === === Таблица истинности бинарных булевых функций === {| class="standard" !Операнды и операции || || || || || || || || |- !первый, x ||1||0||1||0||Название ||||Обозначения || |- !второй, y ||1||1||0||0|| ||Рус. ||Англ. ||Знаковые |- |f(10,1,0000)2(x,y)= ||0||0||0||0||тождественный ноль ||0 ||FALSE ||f(2,1,0)10(x,y) = 0(x,y) = |- |f(10,1,0001)2(x,y)= ||0||0||0||1||НЕ-2ИЛИ, 2ИЛИ-НЕ, отрицание (негация, инверсия) 2ИЛИ, стрелка Пирса ||НЕ-2ИЛИ, 2ИЛИ-НЕ ||2NOR ||f(2,1,1)10(x,y) = = = (~x)&(~y) |- |f(10,1,0010)2(x,y)= ||0||0||1||0||больше, инверсия прямой импликации ||БОЛЬШЕ, Б ||GT ||f(2,1,2)10(x,y) = = = x>y |- |f(10,1,0011)2(x,y)= ||0||0||1||1||отрицание (негация, инверсия) второго операнда ||НЕ y ||NOT y||f(2,1,3)10(x,y) = = = = ~y |- |f(10,1,0100)2(x,y)= ||0||1||0||0||меньше, инверсия обратной импликации ||МЕНЬШЕ, М ||LT ||f(2,1,4)10(x,y) = = = x<y |- |f(10,1,0101)2(x,y)= ||0||1||0||1||отрицание (негация, инверсия) первого операнда||НЕ x ||NOT x||f(2,1,5)10(x,y) = = = = ~x |- |f(10,1,0110)2(x,y)=||0||1||1||0||НЕ РАВНО, 2Искл.ИЛИ, сложение по модулю 2, ЛИБО||НЕ РАВНО, 2ИСКЛ. ИЛИ, ЛИБО, ЛБ ||2XOR ||f(2,1,6)10(x,y) = x� y = = |- |f(10,1,0111)2(x,y)=||0||1||1||1||НЕ-2И, 2И-НЕ, отрицание (негация, инверсия) 2И, штрих Шеффера ||НЕ-2И, 2И-НЕ ||2NAND||f(2,1,7)10(x,y) = = ~(x&y) |- |f(10,1,1000)2(x,y)=||1||0||0||0||2И, конъюнкция, минимум ||2И||2AND ||f(2,1,8)10(x,y) = = = = x&y = x&&y = x&y = min(x,y) |- |f(10,1,1001)2(x,y)=||1||0||0||1||равенство, эквивалентность ||РАВНО, Р ||EQ ||f(2,1,9)10(x,y) = (x=y) |- |f(10,1,1010)2(x,y)=||1||0||1||0||повтор первого операнда ||ДА1 ||YES1 ||f(2,1,10)10(x,y) = ДА1(x,y) = YES1(x,y) = x |- |f(10,1,1011)2(x,y)=||1||0||1||1||больше или равно, обратная импликация, инверсия от "обнаружен переход от 0 к 1" ||БР ||GE ||f(2,1,11)10(x,y) = = = = (x>=y) |- |f(10,1,1100)2(x,y)=||1||1||0||0||повтор второго операнда ||ДА2 ||YES2 ||f(2,1,12)10(x,y) = ДА2(x,y) = YES2(x,y) = y |- |f(10,1,1101)2(x,y)=||1||1||0||1||меньше или равно, прямая импликация, инверсия от "обнаружен переход от 1 к 0" ||МР ||LE ||f(2,1,13)10(x,y) = = = = (x<=y) = (~x)vy |- |f(10,1,1110)2(x,y)=||1||1||1||0||2ИЛИ, дизъюнкция, максимум ||2ИЛИ ||2OR ||f(2,1,14)10(x,y) = max(x,y) = (xvy) = (x+y) = |- |f(10,1,1111)2(x,y)=||1||1||1||1||тождественная единица ||1 ||TRUE ||f(2,1,15)10(x,y) = 1(x,y) = |} Двоичный номер операции равен результату операции из таблицы истиности, при этом, порядковый номер двоичного разряда в номере операции равен значению операндов (первый операнд - младший значащий разряд, второй операнд - старший значащий разряд).
В номере операции (функции):
первое число - число входов,
второе число - число выходов,
третье число - номер операции (функции), он же результат действия операции (функции),
четвёртое число - основание системы счисления.
=== 2И, 2И-ДА ===
"(Логическое) И" (and) — аналог конъюнкции в логике. Иногда называется логическим умножением. {| class="wide" align="center" |В булевой логике: |В языке C: & |В языке Pascal: and |} Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.
f(10,1,1000)2(x,y)=f(2,1,8)10(x,y)
=== 2ИЛИ, 2ИЛИ-ДА ===
"(Логическое) ИЛИ" (or) — аналог дизъюнкции в логике. {| class="wide" align="center" |В булевой логике: |В языке C: | |В языке Pascal: or |} Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (то есть при замене 0 и 1 местами) «И» и "ИЛИ" взаимно превращается друг в друга.
f(10,1,1110)2(x,y)=f(2,1,14)10(x,y)
=== Исключающее ИЛИ ===
"Исключающее ИЛИ" (xor), "сложение по модулю 2" — аналог исключающего ИЛИ в логике. {| class="wide" align="center" |В булевой логике: |В языке C: ^ |В языке Pascal: xor |} Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата "ИЛИ" только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов "исключается"). Ещё в русской грамматике значение данной логической связки передаётся союзом "либо". Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и "ИЛИ" данная операция является обратимой, или инволютивной: . В графике "исключающее ИЛИ" применяется при выводе спрайтов на картинку — повторное её применение убирает спрайт с картинки. Благодаря инволютивности же эта операция нашла применение в криптографии как простейшая реализация идеального шифра (шифра Вернама). "Исключающее ИЛИ" также может использоваться для обмена двух переменных, используя алгоритм обмена при помощи исключающего ИЛИ.
f(10,1,0110)2(x,y)=f(2,1,6)10(x,y)
===2ИЛИ-НЕТ, 2ИЛИ-НЕ=== "ИЛИ-НЕ" (nor), она же "стрелка Пирса".
{| class="wide" align="center" |В булевой логике: |} Стрелка Пирса является результатом инвертирования результата "ИЛИ" своих аргументов, выдаёт значение 1 только когда оба входа 0.
f(10,1,0001)2(x,y)=f(2,1,1)10(x,y)
=== 2И-НЕТ, 2И-НЕ === "И-НЕ" (nand), или "штрих Шеффера".
{| class="wide" align="center" |В булевой логике: |} Двойственная стрелке Пирса операция: является результатом инвертирования результата «И» своих аргументов, выдаёт значение 0 только когда оба входа 1. Известна простотой реализации в ТТЛ.
f(10,1,0111)2(x,y)=f(2,1,7)10(x,y)
====Эквиваленция==== Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата "исключающего ИЛИ" своих аргументов. Она же и двойственна исключающему "ИЛИ" в вышеописанном смысле.
f(10,1,1001)2(x,y)=f(2,1,9)10(x,y)
====Импликация==== ("если-то") — аналог импликации в логике. {| class="wide" align="center" |В булевой логике: |} Совпадает с "ИЛИ" с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое (меньше или равно).
f(10,1,1101)2(x,y)=f(2,1,13)10(x,y)
== Тринарные операции == Операции «И», "ИЛИ" и "исключающее ИЛИ" являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).
При число битовых операций равно . Им соответствует 256 двоичных трёхвходовых (тернарных, тринарных, трёхоперандных) логических элемента. Из них наибольшую значимость имеют: f(11,1,10010110)2(x,y,z)=f(3,1,150)10(x,y,z) - трёхоперандное (тринарное) логическое сложение по модулю 2 и f(11,1,11101000)2(x,y,z)=f(3,1,232)10(x,y,z) - разряд переноса при трёхоперандном (тринарном) сложении по модулю 2. {| class="standard" !x||1||0||1||0||1||0||1||0|| || |- !y||1||1||0||0||1||1||0||0|| || |- !z||1||1||1||1||0||0||0||0||названия ||обозначения |- |f(11,1,00000000)2(x,y,z)= ||0||0||0||0||0||0||0||0||тождественная ложь, тождественное "НЕТ"||f(3,1,0)10(x,y,z) = 0(x,y,z) = 0 |- |f(11,1,00000001)2(x,y,z)= ||0||0||0||0||0||0||0||1||3ИЛИ-НЕ, операция Вебба, операция Даггера, стрелка Пирса ||f(3,1,1)10(x,y,z) = xyz = (x,y,z) = Webb2(x,y,z) |- |f(11,1,00001111)2(x,y,z)= ||0||0||0||0||1||1||1||1||Инверсия третьего операнда ||f(3,1,15)10(x,y,z) = z' = |- |f(11,1,00101111)2(x,y,z)= ||0||0||1||0||1||1||1||1||Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией||f(3,1,47)10(x,y,z) = |- |f(11,1,00110011)2(x,y,z)= ||0||0||1||1||0||0||1||1||Инверсия второго операнда ||f(3,1,51)10(x,y,z) = y' = |- |f(11,1,01010101)2(x,y,z)= ||0||1||0||1||0||1||0||1||Инверсия первого операнда ||f(3,1,85)10(x,y,z) = x' = |- |f(11,1,01111110)2(x,y,z)= ||0||1||1||1||1||1||1||0||Неравенство операндов||f(3,1,126)10(x,y,z) = (x� y� z) = [� (x,y,z)] |- |f(11,1,01111111)2(x,y,z)= ||0||1||1||1||1||1||1||1||3И-НЕ, штрих Шеффера ||f(3,1,127)10(x,y,z) = xyz = (x,y,z) |- |f(11,1,10000000)2(x,y,z)= ||1||0||0||0||0||0||0||0||3И, минимум ||f(3,1,128)10(x,y,z) = (x&y&z) = &(x,y,z) = min(x,y,z) |- |f(11,1,10000001)2(x,y,z)= ||1||0||0||0||0||0||0||1||Равенство операндов||f(3,1,129)10(x,y,z) = (x=y=z) = [=(x,y,z)] |- |f(11,1,10010110)2(x,y,z)= ||1||0||0||1||0||1||1||0||Тринарное сложение по модулю 2||f(3,1,150)10(x,y,z) = x⊕2y⊕2z = x+2y+2z = ⊕2(x,y,z) = +2(x,y,z) |- |f(11,1,10101010)2(x,y,z)= ||1||0||1||0||1||0||1||0||Повторение первого операнда ||f(3,1,170)10(x,y,z) = да(x) = x |- |f(11,1,11001100)2(x,y,z)= ||1||1||0||0||1||1||0||0||Повторение второго операнда ||f(3,1,204)10(x,y,z) = да(y) = y |- |f(11,1,11010000)2(x,y,z)= ||1||1||0||1||0||0||0||0||переключатель по большинству, 3ППБ, мажоритарный клапан||f(3,1,208)10(x,y,z) = [>=2(x,y,z)] |- |f(11,1,11011000)2(x,y,z)= ||1||1||0||1||1||0||0||0||Разряд переноса при тринарном вычитании ||f(3,1,216)10(x,y,z) |- |f(11,1,11101000)2(x,y,z)= ||1||1||1||0||1||0||0||0||Разряд переноса при тринарном сложении ||f(3,1,232)10(x,y,z) |- |f(11,1,11110000)2(x,y,z)= ||1||1||1||1||0||0||0||0||Повторение третьего операнда ||f(3,1,240)10(x,y,z) = да(z) = z |- |f(11,1,11111110)2(x,y,z)= ||1||1||1||1||1||1||1||0||3ИЛИ, максимум ||f(3,1,254)10(x,y,z) = (x+y+z) = +(x,y,z) = max(x,y,z) |- |f(11,1,11111111)2(x,y,z)= ||1||1||1||1||1||1||1||1||тождественная истина, тождественное "ДА", тавтология||f(3,1,255)10(x,y,z) = 1(x,y,z) = 1 |}
В номере операции:
первое число - число входов,
второе число - число выходов,
третье число - номер операции (функции), он же результат действия операции (функции),
четвёртое число - основание системы счисления.
Двоичный номер операции равен результату действия операции из таблицы истиности. Порядковый номер разряда в номере операции определяется значениями операндов, первый аргумент - нулевой разряд, второй аргумент - первый разряд, третий аргумент - второй разряд номера результата действия операции в номере операции. ==Тетрарные операции и операции от многих аргументов== {| class="standard" !x||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0|||||| |- !y||1||1||0||0||1||1||0||0||1||1||0||0||1||1||0||0|||||| |- !z||1||1||1||1||0||0||0||0||1||1||1||1||0||0||0||0|||||| |- !v||1||1||1||1||1||1||1||1||0||0||0||0||0||0||0||0||||названия||обозначения |- |f(4,1,0)10(x,y,z,v) ||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||f(100,1,0000000000000000)2(x,y,z,v) ||тождественная ложь, тождественное "НЕТ"||0 |- |f(4,1,1)10(x,y,z,v) ||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||1||f(100,1,0000000000000001)2(x,y,z,v)||4ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса ||xyzv, (x,y,z,v), Webb2(x,y,z,v) |- |f(4,1,255)10(x,y,z,v) ||0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1||f(100,1,0000000011111111)2(x,y,z,v)||Инверсия четвёртого операнда || |- |f(4,1,3855)10(x,y,z,v) ||0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1||f(100,1,0000111100001111)2(x,y,z,v)||Инверсия третьего операнда || |- |f(4,1,13107)10(x,y,z,v) ||0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1||f(100,1,0011001100110011)2(x,y,z,v)||Инверсия второго операнда || |- |f(4,1,21845)10(x,y,z,v) ||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||f(100,1,0101010101010101)2(x,y,z,v)||Инверсия первого операнда || |- |f(4,1,32766)10(x,y,z,v) ||0||1||1||1||1||1||1||1||1||1||1||1||1||1||1||0||f(100,1,0111111111111110)2(x,y,z,v)||Неравенство ||x� y� z� v, � (x,y,z,v) |- |f(4,1,32767)10(x,y,z,v) ||0||1||1||1||1||1||1||1||1||1||1||1||1||1||1||1||f(100,1,0111111111111111)2(x,y,z,v)||4И-НЕ, штрих Шеффера ||xyzv, (x,y,z,v) |- |f(4,1,32768)10(x,y,z,v) ||1||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||f(100,1,1000000000000000)2(x,y,z,v) ||4И, минимум ||x&y&z&v, &(x,y,z,v), min(x,y,z,v) |- |f(4,1,32769)10(x,y,z,v) ||1||0||0||0||0||0||0||0||0||0||0||0||0||0||0||1||f(100,1,1000000000000001)2(x,y,z,v)||Равенство ||x=y=z=v, =(x,y,z,v) |- |f(4,1,27030)10(x,y,z,v) ||0||1||1||0||1||0||0||1||1||0||0||1||0||1||1||0||f(100,1,0110100110010110)2(x,y,z,v) ||Тетрарное сложение по модулю 2 ||x⊕2y⊕2z⊕2v, x+2y+2z+2v, ⊕2(x,y,z,v), +2(x,y,z,v) |- |f(4,1,43690)10(x,y,z,v) ||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||f(100,1,1010101010101010)2(x,y,z,v)||Повторение первого операнда ||да(x), x |- |f(4,1,52428)10(x,y,z,v) ||1||1||0||0||1||1||0||0||1||1||0||0||1||1||0||0||f(100,1,1100110011001100)2(x,y,z,v)||Повторение второго операнда ||да(y), y |- |f(4,1,61680)10(x,y,z,v) ||1||1||1||1||0||0||0||0||1||1||1||1||0||0||0||0||f(100,1,1111000011110000)2(x,y,z,v)||Повторение третьего операнда ||да(z), z |- |f(4,1,65280)10(x,y,z,v) ||1||1||1||1||1||1||1||1||0||0||0||0||0||0||0||0||f(100,1,1111111100000000)2(x,y,z,v)||Повторение четвёртого операнда ||да(v), v |- |f(4,1,65534)10(x,y,z,v) ||1||1||1||1||1||1||1||1||1||1||1||1||1||1||1||0||f(100,1,1111111111111110)2(x,y,z,v)||4ИЛИ, максимум ||x+y+z+v, +(x,y,z,v), max(x,y,z,v) |- |f(4,1,65535)10(x,y,z,v) ||1||1||1||1||1||1||1||1||1||1||1||1||1||1||1||1|| f(100,1,1111111111111111)2(x,y,z,v) || тождественная истина, тождественное "ДА", тавтология||1 |}
== Операции над битовыми векторами == === Обобщение операций на булеву алгебру === Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов (в программировании их называют регистрами), например, байты. В программировании регистры рассматривают как двоичное разложение целого числа: , где N — количество битов в регистре. Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операции от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и�т. д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из −1 (~x == -1-x). Однако, они очень полезны в программировании. === Битовые сдвиги ===
К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов�— логический, арифметический и циклический, в зависимости от обработки крайних битов. Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).
Логический сдвиг
Арифметический сдвиг (правый)
Циклический сдвиг
Циклический сдвиг через перенос
==== Логический сдвиг ==== При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение. Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно. ==== Арифметический сдвиг ==== Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому. ==== Циклический сдвиг ==== При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса). Также различают циклический сдвиг через бит переноса — при нём первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса. === 2-адическая интерпретация === Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории p-адических чисел при . Множество целых 2-адических чисел (то есть произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования. == Практические применения == === Физическая реализация битовых операций === Реализация битовых операций может в принципе быть любой: механической (в том числе гидравлической и пневматической), химической, тепловой [1], электрической, магнитной и электромагнитной (диапазоны — ИК, видимый оптический, УФ и далее по убыванию длин волн), а также в виде комбинаций, например, электромеханической. В первой половине XX века до изобретения транзисторов применяли электромеханические реле и электронные лампы. В пожароопасных и взрывоопасных условиях до сих пор применяют пневматические логические устройства (пневмоника). Наиболее распространены электронные реализации битовых операций при помощи транзисторов, например резисторно-транзисторная логика (РТЛ), диодно-транзисторная логика (ДТЛ), эмиттерно-связанная логика (ЭСЛ), транзисторно-транзисторная логика (ТТЛ), N-МОП логика, КМОП логика и др.. Одной из причин, из-за которой базовые (основные) логические элементы строят на инверторах, а повторители являются дополнительными элементами, было то, что в электронике инверторы (ОЭ) мощнее повторителей (ОК). Но основной причиной является то, что два инвертора заменяют один повторитель, а на повторителях инвертор не построить. В квантовых вычислениях из перечисленных булевых операций реализуются только НЕ и искл. ИЛИ (с некоторыми оговорками). Квантовых аналогов И, ИЛИ и�т. д. не существует. === Схемы аппаратной логики === Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой. Битовые операции применяются в знакогенераторах и графических адаптерах; особенно велика была их роль в адаптере EGA в режимах с 16 цветами�— хитроумное сочетание аппаратной логики адаптера с логическими командами центрального процессора позволяет рассматривать EGA как первый в истории графический ускоритель. === Использование в программировании === Благодаря реализации в арифметическом логическом устройстве (АЛУ) процессора многие их регистровые битовые операции аппаратно доступны в языках низкого уровня. В большинстве процессоров реализованы в качестве инструкции регистровый НЕ; регистровые двухаргументные И, ИЛИ, исключающее ИЛИ; проверка равенства нулю (см. выше); три типа битовых сдвигов, а также циклические битовые сдвиги. Регистровая операция И используется для сброса конкретных битов по битовой маске, ИЛИ — для установки, исключающее ИЛИ — для инвертирования битов регистра по маске. Так, например, в сетевых интернет-технологиях операция И между значением IP-адреса и значением маски подсети используется для определения принадлежности данного адреса к подсети. == См. также == * Булева алгебра * Булевы функции * Алгебра логики * Бит * Битовое поле * Двоичная система счисления * Двоичная логика * Комбинационная логика * Логический вентиль * Логические элементы * Секвенциальная логика
Примечания[]
Ссылки[]
- http://digital.sibsutis.ru/digital/logic.htm Логические элементы
Шаблон:Технологии CPU