Что является результатом действия побитового оператора

Побитовые операторы

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

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

Формат 32-битного целого числа со знаком

Побитовые операторы в JavaScript работают с 32-битными целыми числами в их двоичном представлении.

Это представление называется «32-битное целое со знаком, старшим битом слева и дополнением до двойки».

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

• Что такое двоичная система счисления, вам, надеюсь, уже известно. При разборе побитовых операций мы будем обсуждать именно двоичное представление чисел, из 32 бит.
• Старший бит слева – это научное название для самого обычного порядка записи цифр (от большего разряда к меньшему). При этом, если больший разряд отсутствует, то соответствующий бит равен нулю. Примеры представления чисел в двоичной системе:

a = 0; // 00000000000000000000000000000000 a = 1; // 00000000000000000000000000000001 a = 2; // 00000000000000000000000000000010 a = 3; // 00000000000000000000000000000011 a = 255;// 00000000000000000000000011111111

00000000000000000000000100111010

Чтобы получить -314 , первый шаг – обратить биты числа: заменить 0 на 1 , а 1 на 0 :

11111111111111111111111011000101

Второй шаг – к полученному двоичному числу прибавить единицу, обычным двоичным сложением: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 . Итак, мы получили:

-314 = 11111111111111111111111011000110

Список операторов

В следующей таблице перечислены все побитовые операторы. Далее операторы разобраны более подробно.

Оператор	Использование	Описание
Побитовое И (AND)	a & b	Ставит 1 на бит результата, для которого соответствующие биты операндов равны 1.
Побитовое ИЛИ (OR)	a | b	Ставит 1 на бит результата, для которого хотя бы один из соответствующих битов операндов равен 1.
Побитовое исключающее ИЛИ (XOR)	a ^ b	Ставит 1 на бит результата, для которого только один из соответствующих битов операндов равен 1 (но не оба).
Побитовое НЕ (NOT)	~a	Заменяет каждый бит операнда на противоположный.
Левый сдвиг	a	Сдвигает двоичное представление a на b битов влево, добавляя справа нули.
Правый сдвиг, переносящий знак	a >> b	Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты.
Правый сдвиг с заполнением нулями	a >>> b	Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты и добавляя нули слева.

Побитовые операторы работают следующим образом:

1. Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
2. Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
3. Получившаяся в результате последовательность бит интерпретируется как обычное число.

Посмотрим, как работают операторы, на примерах.

Вспомогательные функции parseInt, toString

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

• parseInt(«11000», 2) – переводит строку с двоичной записью числа в число.
• n.toString(2) – получает для числа n запись в 2-ной системе в виде строки.

let access = parseInt("11000", 2); // получаем число из строки alert( access ); // 24, число с таким 2-ным представлением let access2 = access.toString(2); // обратно двоичную строку из числа alert( access2 ); // 11000

Без них перевод в двоичную систему и обратно был бы куда менее удобен. Более подробно они разбираются в главе Числа.

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

Выполняет операцию И над каждой парой бит.

Результат a & b равен единице только когда оба бита a и b равны единице.

Таблица истинности для & :

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 & 9 (по осн. 10) = 00000000000000000000000000001000 (по осн. 2) = 8 (по осн. 10)

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

Выполняет операцию ИЛИ над каждой парой бит. Результат a | b равен 1, если хотя бы один бит из a,b равен 1.

Таблица истинности для | :

a	b	a | b
0	0	0
0	1	1
1	0	1
1	1	1

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 | 9 (по осн. 10) = 00000000000000000000000000001111 (по осн. 2) = 15 (по осн. 10)

^ (Исключающее ИЛИ)

Выполняет операцию «Исключающее ИЛИ» над каждой парой бит.

a Исключающее ИЛИ b равно 1, если только a=1 или только b=1 , но не оба одновременно a=b=1 .

Таблица истинности для исключающего ИЛИ:

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

Как видно, оно даёт 1, если ЛИБО слева 1 , ЛИБО справа 1 , но не одновременно. Поэтому его и называют «исключающее ИЛИ».

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 ^ 9 (по осн. 10) = 00000000000000000000000000000111 (по осн. 2) = 7 (по осн. 10)

Исключающее ИЛИ в шифровании

Исключающее или можно использовать для шифрования, так как эта операция полностью обратима. Двойное применение исключающего ИЛИ с тем же аргументом даёт исходное число.

Иначе говоря, верна формула: a ^ b ^ b == a .

Пусть Вася хочет передать Пете секретную информацию data . Эта информация заранее превращена в число, например строка интерпретируется как последовательность кодов символов.

Вася и Петя заранее договариваются о числовом ключе шифрования key .

• Вася берёт двоичное представление data и делает операцию data ^ key . При необходимости data бьётся на части, равные по длине key , чтобы можно было провести побитовое ИЛИ ^ для каждой части. В JavaScript оператор ^ работает с 32-битными целыми числами, так что data нужно разбить на последовательность таких чисел.
• Результат data ^ key отправляется Пете, это шифровка.

Например, пусть в data очередное число равно 9 , а ключ key равен 1220461917 .

Данные: 9 в двоичном виде 00000000000000000000000000001001 Ключ: 1220461917 в двоичном виде 01001000101111101100010101011101 Результат операции 9 ^ key: 01001000101111101100010101010100 Результат в 10-ной системе (шифровка): 1220461908

• Петя, получив очередное число шифровки 1220461908 , применяет к нему такую же операцию ^ key .
• Результатом будет исходное число data .

Полученная шифровка в двоичной системе: 9 ^ key = 1220461908 01001000101111101100010101010100 Ключ: 1220461917 в двоичном виде: 01001000101111101100010101011101 Результат операции 1220461917 ^ key: 00000000000000000000000000001001 Результат в 10-ной системе (исходное сообщение): 9

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

~ (Побитовое НЕ)

Производит операцию НЕ над каждым битом, заменяя его на обратный ему.

Таблица истинности для НЕ:

a	~a
0	1
1	0

 9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) -------------------------------- ~9 (по осн. 10) = 11111111111111111111111111110110 (по осн. 2) = -10 (по осн. 10)

Из-за внутреннего представления отрицательных чисел получается так, что ~n == -(n+1) .

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

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

Принцип работы

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

Битовые операторы И [math](AND,\ \&)[/math] , ИЛИ [math](OR,\ \mid)[/math] , НЕ [math](NOT,\ \sim)[/math] и исключающее ИЛИ [math](XOR,\ $\textasciicircum$,\ \oplus)[/math] используют те же таблицы истинности, что и их логические эквиваленты.

Побитовое И

Побитовое И используется для выключения битов. Любой бит, установленный в [math]0[/math] , вызывает установку соответствующего бита результата также в [math]0[/math] .

&
	11001010 11100010
11000010

Побитовое ИЛИ

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в [math]1[/math] , вызывает установку соответствующего бита результата также в [math]1[/math] .

|
	11001010 11100010
11101010

Побитовое НЕ

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

~
	11001010
00110101

Побитовое исключающее ИЛИ

Исключающее ИЛИ устанавливает значение бита результата в [math]1[/math] , если значения в соответствующих битах исходных переменных различны.

^
	11001010 11100010
00101000

Побитовые сдвиги

Операторы сдвига [math]\lt \lt [/math] и [math]<\gt \gt >[/math] сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7 // 00000111 (7) x = x >> 1 // 00000011 (3) x = x // 00000110 (6) x = x // 11000000 (-64) x = x >> 2 // 11110000 (-16) 

В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\gt \gt \gt [/math] . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

x = 7 // 00000111 (7) x = x // 11100000 (-32) x = x >>> 2 // 00111000 (56) 

Применение

Сложные операции

Определение знака числа

Пусть дано число [math]x[/math] . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа [math]x[/math] можно определить, выполнив сдвиг вправо на всю длину переменной:

int32 getSign(x: int32): if x != 0: mask = 1 else: mask = 0 return mask | (x >> 31) // результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно 

Используя побитовые операции можно также узнать, различны ли знаки двух переменных [math]x[/math] и [math]y[/math] . Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство [math](x \oplus y) \lt 0[/math] будет верно в том случае, если числа [math]x[/math] и [math]y[/math] разного знака.

Вычисление модуля числа без использования условного оператора

Пусть дано число [math]x[/math] . Если [math]x[/math] положительно, то [math]mask = 0[/math] , и [math](x + mask) \oplus mask = x[/math] . В случае, если [math]x[/math] отрицательно, [math]mask = -1[/math] . Тогда получается, что мы работаем с числом [math]x[/math] так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение [math]1[/math] для отрицательных чисел, а [math]0[/math] — для положительных.

int32 abs1(x: int32): mask = x >> 31 return (x + mask) XOR mask int32 abs2(x: int32): mask = x >> 31 return (x + mask) XOR mask

Нахождение минимума и максимума из двух чисел без использования условного оператора

Этот способ корректен только если можно утверждать, что величина [math](x — y)[/math] лежит между граничными значениями типа int.

Пусть даны числа [math]x[/math] и [math]y[/math] разрядности [math]n[/math] . Тогда если [math]x \lt y[/math] , то [math]((x — y) \gt \gt (n — 1)) = -1[/math] , а если [math]x \geqslant y[/math] , то [math]((x — y) \gt \gt (n — 1)) = 0[/math] . Выражение [math]((x — y) \& ((x — y) \gt \gt (n — 1))[/math] принимает значение [math]0[/math] , если [math]x \geqslant y[/math] , и [math](x — y)[/math] , если [math]x \lt y[/math] .

int32 min(x, y: int32): return y + ((x - y) & ((x - y) >> 31)) int32 max(x, y: int32): return x - ((x - y) & ((x - y) >> 31))

Проверка на то, является ли число степенью двойки

Пусть дано число [math]x[/math] . Тогда, если результатом выражения [math](x\ \&\&\ !(x\ \&\ (x — 1)))[/math] является единица, то число [math]x[/math] — степень двойки.

Правая часть выражения [math](!(x\ \&\ (x — 1)))[/math] будет равна единице, только если число [math]x[/math] равно [math]0[/math] или является степенью двойки. Если число [math]x[/math] является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: [math]1\underbrace_[/math] , где [math]n[/math] — показатель степени. Соответственно, выражение [math](x — 1)[/math] будет иметь вид [math]\underbrace_[/math] , и [math]x\ \&\ (x — 1)[/math] равно [math]0[/math] .

Операция логического И в данном выражении отсекает тот случай, когда [math](x = 0)[/math] и не является степенью двойки, но при этом правая часть [math](!(x\ \&\ (x — 1)))[/math] равна единице.

Нахождение младшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его младший единичный бит.

Применим к числу [math]x[/math] побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом [math]x[/math] , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа [math](x\ \&\ (\sim x + 1))[/math] .

К такому же результату можно прийти, если сначала отнять от числа [math]x[/math] единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в [math]1[/math] , затем инвертировать результат и применить побитовое И с исходным числом [math](x\ \&\ \sim (x — 1))[/math] .

Нахождение старшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его старший единичный бит.

Рассмотрим некоторое число, представим его как [math]0\dots01b \dots b[/math] , где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на [math]1[/math] и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат [math]0\dots011b \dots b[/math] . Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на [math]2[/math] , то получим [math]0\dots01111b \dots b[/math] . При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида [math]0\dots01\dots1[/math] . Тогда результатом выполнения действий [math]x — (x \texttt< \gt \gt >1)[/math] будет число, состоящее только из старшего бита исходного числа.

int32 greatestBit(x: int32): power = 1 for i = 1 [math] \ldots\log_2[/math]: x |= x >> power power return x - (x >> 1)

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

Пусть дано число [math]x[/math] и надо совершить циклический сдвиг его битов на величину [math]d[/math] . Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на [math]d[/math] и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int32 rotateLeft(x, d: int32): return (x >> (32 - d)) int32 rotateRight(x, d: int32): return (x >>> d) | (x 
Подсчет количества единичных битов
Для подсчета количества единичных битов в числе [math]x[/math] можно воспользоваться следующим алгоритмом:
// Для чисел других разрядностей необходимо использовать соответствующие константы. int16 setBitsNumber(x: int16): x = x - ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F return (x * 0x0101) >>> 8
Поскольку [math]5555_[/math] равно [math]01010101 01010101_[/math] , результатом операции [math]x\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют нечетным битам числа [math]x[/math] . Аналогично, результатом операции [math](x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют четным битам [math]x[/math] . Четные биты результата в обоих случаях равны нулю.
Мысленно разобьем двоичную запись нашего числа [math]x[/math] на группы по [math]2[/math] бита. Результатом операции [math]x\ \&\ 5555_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа [math]x[/math] .
Аналогично, число [math]3333_[/math] равно [math]00110011 00110011_[/math] и операция [math]x = (x\ \&\ 3333_) + (x\ \texttt<\gt \gt \gt >\ 2\ \&\ 3333_)[/math] , примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по [math]4[/math] . В свою очередь, число [math]\texttt_[/math] равно [math]00001111 00001111_[/math] и операция [math]x = (x\ \&\ \texttt_) + (x\ \texttt<\gt \gt \gt >\ 4\ \&\ \texttt_)[/math] позволяет подсчитать число единичных бит в блоках по [math]8[/math] .
Теперь необходимо просуммировать числа, записанные в блоках по [math]8[/math] битов, чтобы получить искомую величину. Это можно сделать, домножив результат на [math]0101_[/math] [math](1 00000001_)[/math] . Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на [math]8[/math] (для шестнадцатибитных чисел), мы получим долгожданный ответ.
int16 setBitsNumber(x: int16): x = (x & 0x5555) + ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F) return (x * 0x0101) >>> 8
Заметим, что операция [math]x\ \&\ 55_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] равносильна операции [math]x - (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] , в чем легко убедиться, рассмотрев все числа из двух бит.
В свою очередь, операцию [math](x\ \&\ \texttt_) + ((x\ \texttt<\gt \gt \gt >\ 4)\ \&\ \texttt_)[/math] можно заменить на [math](x + (x\ \texttt<\gt \gt \gt >\ 4))\ \&\ \texttt_[/math] . Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.






Таким образом, мы получили код, приведенный в начале раздела.
Разворот битов
Чтобы получить биты числа [math]x[/math] , записанные в обратном порядке, применим следующий алгоритм.
// Для чисел других разрядностей нужны соответствующие константы. int16 reverseBits(x: int16): x = ((x & 0x5555) >> 1) & 0x5555) // Четные и нечетные биты поменялись местами. x = ((x & 0x3333) >> 2) & 0x3333) // Биты "перетасовываются" группами по два. x = ((x & 0x0F0F) >> 4) & 0x0F0F) // Биты "перетасовываются" группами по четыре. x = ((x & 0x00FF) >> 8) & 0x00FF) // Биты "перетасовываются" группами по восемь. return x
Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе подсчет количества единичных битов.
Применение для решения задач
Работа с битовыми масками
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [math](\sim mask)[/math] , пересечение [math](mask_1\ \&\ mask_2)[/math] , объединение [math](mask_1 \mid mask_2)[/math] множеств, установить бит по номеру [math](mask \mid (1\ \texttt<\lt \lt >\ x))[/math] , снять бит по номеру [math](mask\ \&\ \sim(1\ \texttt<\lt \lt >\ x))[/math] .
Битовые маски используются, например, при решении некоторых задач [1] динамического программирования.
Алгоритм Флойда
Основная статья: Алгоритм Флойда
Алгоритм Флойда–Уоршелла (англ. the Floyd–Warshall algorithm) — алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма [math] \Theta(n^3) [/math] , также требует [math] \Theta(n^2) [/math] памяти.
Дерево Фенвика
Основная статья: Дерево Фенвика






Дерево Фенвика (англ. Binary indexed tree) — структура данных, которая может выполнять следующие операции:

изменять значение любого элемента в массиве,
выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] \circ [/math] на отрезке [math] [i, j] [/math] .

Данная структура требует [math] O(n) [/math] памяти, а выполнение каждой операции происходит за [math] O(\log n) [/math] .
Функция, позволяющая делать операции вставки и изменения элемента за [math] O(\log n) [/math] , задается следующей формулой [math] F(i) = (i \And (i + 1)) [/math] . Пусть дан массив [math] A = [a_0, a_1, \ldots, a_][/math] . Деревом Фенвика называется массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_^ a_k[/math] , где [math] i = 0\ldots n - 1 [/math] и [math] F(i) [/math] — функция, которую мы определили ранее.
См. также

Определение булевой функции
Сумматор
Триггеры

Примечания
Источники информации

Онлайн справочник программиста на С и С++
Побитовые операторы
Bit Twiddling Hacks by Sean Eron Anderson
Habrahabr — Алгоритмы поиска старшего бита
STP's blog — Counting the number of set bits in an integer

Документация
 
Побитовые операторы позволяют вам манипулировать отдельными битами необработанных данных внутри структуры данных. Они часто используются в низкоуровневом программировании, например программирование графики или создание драйвера для устройства. Побитовые операторы также могут быть полезны, когда вы работаете с необработанными данными из внешних ресурсов, например, шифрование или дешифрование данных для связи через собственный протокол.
Swift поддерживает все побитовые операторы, которые были основаны в C о которых мы поговорим далее.
Побитовый оператор NOT
Побитовый оператор NOT ( ~ ) инвертирует все битовые числа:







Побитовый оператор NOT является префиксным оператором и ставится прямо перед значением (без пробела), над которым он оперирует.
let initialBits: UInt8 = 0b00001111 let invertedBits = ~initialBits // равен 11110000
Целые числа типа UInt8 имеют восемь бит и могут хранить значения от 0 до 255 . В этом примере инициализируем число типа UInt8 , которое имеет бинарное значение 00001111 , которое имеет первые четыре бита равные 0 , а вторая четверка битов равна 1. Это эквивалент числа 15 .
Далее используем побитовый оператор NOT для создания новой константы invertedBits , которая равна initialBits , но только с перевернутыми битами. То есть теперь все единицы стали нулями, а нули единицами. Значение числа invertedBits равно 11110000 , что является эквивалентом 240 .
Побитовый оператор AND
Побитовый оператор AND ( & ) комбинирует два бита двух чисел. Он возвращает новое число, чье значение битов равно 1 , если только оба бита из входящих чисел были равны 1 :

В примере ниже, значения firstSixBits и lastSixBits имеют четыре бита по середине равными 1. Побитовый оператор AND комбинирует их для создания числа 001111100 , которое равно беззнаковому целому числу 60 :






let firstSixBits: UInt8 = 0b11111100 let lastSixBits: UInt8 = 0b00111111 let middleFourBits = firstSixBits & lastSixBits // равен 00111100
Побитовый оператор OR
Побитовый оператор OR ( | ) сравнивает биты двух чисел. Оператор возвращает новое число, чьи биты устанавливаются на 1 , если один и пары битов этих двух чисел имеет бит равный 1 :

В примере ниже значения someBits и moreBits имеют разные биты со значениями 1. Побитовый оператор OR комбинирует их для создания числа 11111110 , что равно беззнаковому целому числу 254 :
let someBits: UInt8 = 0b10110010 let moreBits: UInt8 = 0b01011110 let combinedbits = someBits | moreBits // равен 11111110
Побитовый оператор XOR
Побитовый оператор XOR или “оператор исключающего OR” ( ^ ), который сравнивает биты двух чисел. Оператор возвращает число, которое имеет биты равные 1 , когда биты входных чисел разные, и возвращает 0 , когда биты одинаковые:

В примере ниже, значения firstBits и otherBits каждый имеет один бит в том месте, где у другого 0. Побитовый оператор XOR устанавливает оба этих бита в качестве выходного значения. Все остальные биты повторяются, поэтому оператор возвращает 0 :
let firstBits: UInt8 = 0b00010100 let otherBits: UInt8 = 0b00000101 let outputBits = firstBits ^ otherBits // равен 00010001
Операторы побитового левого и правого сдвига
Оператор побитового левого сдвига ( > ) двигают все биты числа влево или вправо на определенное количество мест, в зависимости от правил, которые определены ниже.






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

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

Такой подход называется логическим сдвигом.
Иллюстрация внизу отображает результат смещения 11111111 > 1 (что означает 11111111 сдвинутые на 1 вправо). Голубые цифры — сдвинутые, серые — отброшенные, оранжевые — вставленные:

Вот как выглядит побитовый сдвиг в виде Swift кода:
let shiftBits: UInt8 = 4 // 00000100 бинарный вид shiftBits > 2 // 00000001
Вы можете использовать побитовый сдвиг для шифрования и дешифрования значений внутри других типов данных:






let pink: UInt32 = 0xCC6699 let redComponent = (pink & 0xFF0000) >> 16 // redComponent равен 0xCC, или 204 let greenComponent = (pink & 0x00FF00) >> 8 // greenComponent равен 0x66, или 102 let blueComponent = pink & 0x0000FF // blueComponent равен 0x99, или 153
Этот пример использует UInt32 , который называется pink , для хранения значения розового цвета из файла CSS. Значение розового цвета # CC6699 , что записывается в виде шестнадцатеричном представлении Swift как 0xCC6699 . Этот цвет затем раскладывается на его красный( CC ), зеленый ( 66 ) и голубой ( 99 ) компоненты при помощи побитового оператора AND ( & ) и побитового оператора правого сдвига ( >> ).
Красный компонент получен с помощью побитового оператора AND между числами 0xCC6699 и 0xFF0000 . Нули в 0xFF0000 фактически являются “маской” для третьего и четвертого бита в 0xCC6699 , тем самым заставляя игнорировать 6699 , и оставляя 0xCC0000 в качестве результата.
После этого число сдвигается на 16 позиций вправо ( >> 16 ). Каждая пара символов в шестнадцатеричном числе использует 8 битов, так что сдвиг вправо на 16 позиций преобразует число 0xCC0000 в 0x0000CC . Это то же самое, что и 0xCC , которое имеет целое значение равное 204 .
Аналогично с зеленым компонентом, который получается путем использования побитового оператора AND между числами 0xCC6699 и 0x00FF00 , который в свою очередь дает нам выходное значение 0x006600 . Это выходное значение затем сдвигается на восемь позиций вправо, давая нам значение 0x66 , что имеет целое значение равное 102 .
Ну а теперь последний синий компонент, который получается при использовании побитового оператора AND между числами 0xCC6699 и 0x0000FF , что в свою очередь дает нам выходное значение равное 0x000099 . Таким образом, нам не нужно сдвигать это вправо, так как 0x000099 уже равно 0x99 , что имеет целое значение равное 153 .
Поведение побитового сдвига для знаковых целых чисел
Поведение побитового сдвига для знаковых целых чисел более сложное, чем для беззнаковых, из-за того, как они представлены в бинарном виде. (Пример ниже основан на восьми битовом знаковом целом числе для простоты примера, однако этот принцип применим к знаковым целым числам любого размера).
Знаковые целые числа используют первый бит (известный как знаковый бит) для индикации того, является ли число положительным или отрицательным. Значение знакового бита равное 0 свидетельствует о положительном числе, 1 — отрицательном.






Остальные биты (известные как биты значения) хранят фактическое значение. Положительные числа хранятся в точности так же как и беззнаковые целые числа, считая от 0. Вот как выглядят биты внутри Int8 для числа 4 :

Знаковый бит равен 0 (число положительное), остальные семь битов означают число 4 , записанное в бинарной форме.
Однако отрицательные числа хранятся иначе. Они хранятся путем вычитания их абсолютного значения из 2 в степени n, где n — количество битов значения.
Вот как выглядит биты внутри Int8 для числа — 4 :

В этот раз, знаковый бит равен 1 (число отрицательное), а остальные семь знаковых бита имеют бинарное значение числа 124 (что означает 128 — 4):







Шифрование отрицательных чисел известно под названием дополнение до двух. Это может показаться необычным способом для отображения отрицательных чисел, но в нем есть несколько преимуществ.
Первое. Вы можете добавить — 1 к — 4 , просто выполняя стандартное сложение всех восьми битов (включая и восьмой бит), и отбрасывая все, что не поместится в ваши восемь бит:

Второе. Представление “дополнения до 2” так же позволяет вам сдвигать биты отрицательных чисел влево и вправо, как в случае с положительными, и все так же умножая их при сдвиге влево или уменьшая их в два раза, при сдвиге на 1 место вправо. Для того чтобы обеспечить такое поведение при движении знаковых чисел вправо, мы должны применить дополнительное правило:

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


Эти действия гарантируют вам, что знаковые числа имеют тот же знак, после того как они сдвинуты вправо, и эти действия известны как арифметический сдвиг.
Из-за такого способа хранения положительных и отрицательных чисел, сдвиг вправо двигает их значение ближе к нулю. Оставляя знаковый бит тем же самым в течение побитового сдвига, означает, что ваше отрицательное число, так же и остается отрицательным, в то время как его значение так же движется к нулю.
Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.
Битовые операторы
& Оператор выполнит двоичный И, где бит копируется , если она существует в обоих операндов. Это означает:
 # 0 & 0 = 0 # 0 & 1 = 0 # 1 & 0 = 0 # 1 & 1 = 1 # 60 = 0b111100 # 30 = 0b011110 60 & 30 # Out: 28 # 28 = 0b11100 bin(60 & 30) # Out: 0b11100 
Побитовое ИЛИ
| Оператор выполнит двоичное «или», где бит копируется, если он существует в любом из операндов. Это означает:
 # 0 | 0 = 0 # 0 | 1 = 1 # 1 | 0 = 1 # 1 | 1 = 1 # 60 = 0b111100 # 30 = 0b011110 60 | 30 # Out: 62 # 62 = 0b111110 bin(60 | 30) # Out: 0b111110 
Побитовое XOR (исключающее ИЛИ)
^ Оператор будет выполнять двоичный XOR , в котором двоичный 1 копируется тогда и только тогда , когда это значение ровно один операнд. Другой способ задания этого является то , что результат 1 только если операнды разные. Примеры включают в себя:
 # 0 ^ 0 = 0 # 0 ^ 1 = 1 # 1 ^ 0 = 1 # 1 ^ 1 = 0 # 60 = 0b111100 # 30 = 0b011110 60 ^ 30 # Out: 34 # 34 = 0b100010 bin(60 ^ 30) # Out: 0b100010 
Побитовый сдвиг влево
 # 2 = 0b10 2  

Выполнение левого разрядное смещение 1 эквивалентно умножению на 2 :
Выполнение левого разрядного смещения n эквивалентно умножения на 2**n :
Побитовый сдвиг вправо
>> оператор выполняет побитовое «сдвиг вправо» , где значение левого операнда перемещается вправо на число битов данных в правом операнде.
 # 8 = 0b1000 8 >> 2 # Out: 2 # 2 = 0b10 bin(8 >> 2) # Out: 0b10 
Выполнение правильного битового смещения 1 эквивалентно целочисленного деления на 2 :
 36 >> 1 # Out: 18 15 >> 1 # Out: 7 
Выполнение правильного битового смещения n эквивалентно целочисленное деление на 2**n :
 48 >> 4 # Out: 3 59 >> 3 # Out: 7 
Побитовое НЕ
~ Оператор переворачивает все биты числа. Поскольку компьютеры используют прямой код - прежде всего, в дополнении до двух обозначений для кодирования отрицательных двоичных чисел , где отрицательные числа записываются с ведущим один (1) вместо ведущего нуля (0).
Это означает , что если вы используете 8 бит для представления номера вашего дополнительного кода комплемента, вы бы относиться к модели от 0000 0000 до 0111 1111 для представления чисел от 0 до 127 и резервного 1xxx xxxx для представления отрицательных чисел.
Восьмиразрядные числа с двумя дополнительными числами
Биты Значение без знака Значение двух дополнений 0000 0000 0 0 0000 0001 1 1 0000 0010 2 2 0111 1110 126 126 0111 1111 127 127 1000 0000 128 -128 1000 0001 129 -127 1000 0010 130 -126 1111 1110 254 -2 1111 1111 255 -1
По существу, это означает , что в то время как 1010 0110 имеет беззнаковое значение 166 (прибыл в путем добавления (128 * 1) + (64 * 0) + (32 * 1) + (16 * 0) + (8 * 0) + (4 * 1) + (2 * 1) + (1 * 0) ), оно имеет значение дополнительного код дополнение -90 (прибыли в добавлении (128 * 1) - (64 * 0) - (32 * 1) - (16 * 0) - (8 * 0) - (4 * 1) - (2 * 1) - (1 * 0) , и дополняя значение).
Таким образом, отрицательные числа в диапазоне до -128 ( 1000 0000 ). Ноль (0) представляется в виде 0000 0000 , и минус один (-1) , как 1111 1111 .
В целом, однако, это означает , ~n = -n - 1 .
 # 0 = 0b0000 0000 ~0 # Out: -1 # -1 = 0b1111 1111 # 1 = 0b0000 0001 ~1 # Out: -2 # -2 = 1111 1110 # 2 = 0b0000 0010 ~2 # Out: -3 # -3 = 0b1111 1101 # 123 = 0b0111 1011 ~123 # Out: -124 # -124 = 0b1000 0100 
Обратите внимание, что общий эффект этой операции при нанесении на положительные числа можно суммировать:
И затем, применительно к отрицательным числам, соответствующий эффект:
Следующие примеры иллюстрируют это последнее правило .
 # -0 = 0b0000 0000 ~-0 # Out: -1 # -1 = 0b1111 1111 # 0 is the obvious exception to this rule, as -0 == 0 always # -1 = 0b1000 0001 ~-1 # Out: 0 # 0 = 0b0000 0000 # -2 = 0b1111 1110 ~-2 # Out: 1 # 1 = 0b0000 0001 # -123 = 0b1111 1011 ~-123 # Out: 122 # 122 = 0b0111 1010 
Операции на месте
Все операторы Побитового (кроме ~ ) имеет свои собственные места версии
a = 0b001 a &= 0b010 # a = 0b000 a = 0b001 a |= 0b010 # a = 0b011 a = 0b001 a >= 2 # a = 0b001 a = 0b101 a ^= 0b011 # a = 0b110


Похожие публикации:

Как обновить термекс
Как поставить режим read only
Сколько стоит яндекс практикум английский язык
Что такое open al