2 Битовые сдвиги
Основная статья: Битовый сдвиг
К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.
Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).
Логический сдвиг
Арифметический сдвиг (правый)
Циклический сдвиг
Циклический сдвиг через перенос
Логический сдвиг
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
Арифметический сдвиг
Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом, представленным в дополнительном коде. Так, при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.
Циклический сдвиг
При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).
Также различают циклический сдвиг через бит переноса — при нём первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.
3 В языках программирования
В следующей таблице для некоторых языков программирования приведены встроенные операторы и функции, реализующие побитовые логические операции и их обозначения.
Язык |
НЕ |
И |
ИЛИ |
Искл. ИЛИ |
Сдвиг влево |
Сдвиг вправо |
Другие |
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] используется для оценки сложности алгоритма.
4 Связь с другими науками
Битовые операции и математическая логика
Битовые операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.
Однако, связкам математической логики более соответствуют логические операции в том числе в программировании, нежели собственно битовые операции.
Обобщение операций на булеву алгебру
Вместо одиночных
битов мы можем рассмотреть векторы из
фиксированного количества битов (в
программировании их называют регистрами),
например, байты.
В программировании регистры рассматривают
как двоичное разложение целого числа:
,
где N —
количество битов в регистре.
Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операции от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т. д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из −1 (~x == -1-x). Однако, они очень полезны в программировании.
2-адическая интерпретация
Целое число,
записанное (в дополнительном коде) в
бесконечный (в сторону положительных
степеней двойки) двоичный регистр
является естественным объектом для
теории p-адических
чисел при
.
Множество целых 2-адических чисел (то
есть произвольных бесконечных битовых
последовательностей) может быть
рассмотрено как булева алгебра, точно
так же, как и множество значений битового
регистра конечной длины. Все
вышеперечисленные битовые операции
оказываются непрерывными
отображениями.
Хотя практическое программирование не
располагает регистрами бесконечной
длины, это не мешает использовать данный
теоретический факт в криптографии
для создания быстродействующих алгоритмов
шифрования.
Битовые операции как основа цифровой техники
Битовые операции лежат в основе обработки цифровых сигналов. А именно, посредством них мы можем из одного или нескольких сигналов на входе получить новый сигнал, который в свою очередь может быть подан на вход одной или нескольким таким операциям. По сути, именно битовые операции в сочетании с запоминающими элементами (напр. триггерами) реализуют всё богатство возможностей современной цифровой техники.