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

Не следует путать с булевой функцией.

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

Побитовые логические операции

Ряд источников по языкам низкого уровня называет побитовые логические операции просто логическими,^[1][2] но в терминологии программирования на языках высокого уровня в названиях битовых операций присутствуют прилагательные битовый, побитовый (например: «побитовое логическое И», оно же «побитовое умножение»), поразрядный.

В некоторых языках программирования названия операторов, соответствующих логическим и побитовым логическим операциям, похожи. Кроме того, язык программирования может допускать неявное приведение числового типа к логическому и наоборот. В таких языках программирования необходимо внимательно следить за использованием логических и побитовых операций, перемешивание которых может привести к ошибкам. Например, в C++ результатом выражения «2 && 1» (логическое И) является булево значение true, а результатом выражения «2 & 1» (побитовое И) — целое 0.

Побитовое отрицание (NOT)

Побитовое отрицание (или побитовое НЕ, или дополнение) — это унарная операция, действие которой эквивалентно применению логического отрицания к каждому биту двоичного представления операнда. Другими словами, на той позиции, где в двоичном представлении операнда был 0, в результате будет 1, и, наоборот, где была 1, там будет 0. Например:

НЕ	01
	10

Побитовое И (AND)

Побитовое И — это бинарная операция, действие которой эквивалентно применению логического И к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0.

Пример:

И	0011
	0101
	0001

Побитовое ИЛИ (OR)

Побитовое ИЛИ — это бинарная операция, действие которой эквивалентно применению логического ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1.

Пример:

ИЛИ	0011
	0101
	0111

Сложение по модулю два (XOR)

Основная статья: Сложение по модулю два

Сложение по модулю два (или двухместная операция исключающее ИЛИ) — это бинарная операция, результат действия которой равен 1, если число складываемых единичных битов нечетно, если же их число четно, то результат равен 0.

Пример:

Искл. ИЛИ	0011
	0101
	0110

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

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

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

Другие побитовые логические операции

В распространенных языках программирования встроенными средствами реализуются только четыре побитовые логические операции: И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных, и, более того, как следует из теории булевых функций, можно ограничиться ещё меньшим набором базовых операций. Есть также языки программирования, где существует встроенная возможность выполнить любую бинарную логическую операцию побитово. Например, в PL/I есть встроенная функция BOOL, третий аргумент которой предназначен для указания произвольной логической операции, которую необходимо побитово применить к первым двум аргументам^[3].

Битовые сдвиги

Основная статья: Битовый сдвиг

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

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

Логический сдвиг

Арифметический сдвиг (правый)

Циклический сдвиг

Циклический сдвиг через перенос

Логический сдвиг

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

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

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

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

Циклический сдвиг

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

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

В языках программирования

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

Язык	НЕ	И	ИЛИ	Искл. ИЛИ	Сдвиг влево	Сдвиг вправо	Другие
C/С++, Java, C#[4]	~	&	|	^	<<	>>
Pascal[5]	not	and	or	xor	shl	shr
PL/I[6]	INOT	IAND	IOR	IEOR			BOOL
	¬	&	|	¬
Prolog[7]	\	/\	\/

В теории сложности алгоритмов

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

Битовая операция в теории алгоритмов запись знаков 0, 1, плюс, минус, скобка; сложение, вычитание и умножение двух битов (числа записаны в двоичной системе счисления)^[8][9]. Используется для оценки сложности алгоритма.

Связь с другими науками

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

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

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

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

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

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

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

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

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

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

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

С точки зрения применения отдельная битовая операция мало интересна. Поэтому практическое применение основывается на способах комбинирования различных битовых операций, для реализации более сложного вычисления. Можно отметить два аспекта:

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

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

Реализация битовых операций может в принципе быть любой: механической (в том числе гидравлической и пневматической), химической, тепловой,^[10] электрической, магнитной и электромагнитной (диапазоны — ИК, видимый оптический, УФ и далее по убыванию длин волн), а также в виде комбинаций, например, электромеханической.

В первой половине XX века до изобретения транзисторов применяли электромеханические реле и электронные лампы.

В пожароопасных и взрывоопасных условиях до сих пор применяют пневматические логические устройства (пневмоника).

Наиболее распространены электронные реализации битовых операций при помощи транзисторов, например резисторно-транзисторная логика (РТЛ), диодно-транзисторная логика (ДТЛ), эмиттерно-связанная логика (ЭСЛ), транзисторно-транзисторная логика (ТТЛ), N-МОП логика, КМОП логика и др.

Одной из причин, из-за которой базовые (основные) логические элементы строят на инверторах, а повторители являются дополнительными элементами, было то, что в электронике инверторы (ОЭ) мощнее повторителей (ОК). Но основной причиной является то, что два инвертора заменяют один повторитель, а на повторителях инвертор не построить.

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

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

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

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

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

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

Регистровая операция И используется для:

• проверки бита на 0 или 1
• установки 0 в указанный бит (сброса бита)

Регистровая операция ИЛИ используется:

• установки 1 в указанный бит

Регистровая операция исключающее ИЛИ используется для инвертирования битов регистра по маске Сдвиг влево/вправо используется для умножения/целочисленного деления на 2 и выделения отдельных битов.

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

См. также

• Бит
• Битовое поле
• Двоичная система счисления
• Двоичная логика
• Комбинационная логика

Примечания

1. ↑ ЯЗЫК АССЕМБЛЕРА МИКРОПРОЦЕССОРА 8086
2. ↑ Умножение и деление // Справочник по системе программирования Турбо Ассемблер / Под ред. Орлова С. Б..
3. ↑ PL/I Language Reference — с. 393
4. ↑ The Java Language Specification. Integer Operations
5. ↑ Free Pascal: Reference guide. Logical operators
6. ↑ PL/I Language Reference
7. ↑ GNU-Prolog Manual. Arithmetic
8. ↑ Карацуба Е. А. Быстрые алгоритмы и метод БВЕ — 2008
9. ↑ Ященко В. В. (ред.) Введение в криптографию — 2000
10. ↑ Создан логический вентиль для теплового компьютера // Lenta.ru. — В. 05.11.2007.