Какой логической побитовой операции нет в python

Если нужно помножить число на 16, то нужно сдвинуть это число на 4 бита влево. Если нужно разделить число на 8, то нужно сдвинуть это число на 3 бита вправо. Скорость выполнения операций сдвига выше в сравнении с операциями умножения и деления на числа кратные 2 в степени N ( N – количество сдвинутых бит).

Пример.

# Операции сдвига влево > x = 5 # сдвиг влево на 3 знака, умножение на 2**3 = 8 y = x # y = x*2**3 = 40 print('x = ', x) print('y = x, y) x = 25 y = x >> 2 # y = 6 print('x = ', x) print('y = x>>2 = ', y) # Для отрицательных чисел x = -10 y = x # y = -20 print('x = ', x) print('y = x, y) x = -100 y = x >> 3 # y = -13 print('x = ', x) print('y = x>>3 = ', y)

Результат работы программы

x = 5 y = x x = 25 y = x>>2 = 6 x = -10 y = x x = -100 y = x>>3 = -13

4. Битовый оператор & (И, AND). Пример

Битовый оператор И (AND) есть бинарным и выполняет побитовое «И» для каждой пары битов операндов, которые размещаются слева и справа от знака оператора & . Общая форма оператора следующая

op1 & op2

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

Каждый целочисленный операнд рассматривается как набор бит, над любым из которых выполняется побитовая операция «И».

На рисунке 2 показана работа битовой операции «И».

Рисунок 2. Битовый оператор & «И»

Как видно из рисунка, бит в позиции 0 первого операнда ( x ) вычисляется с битом в позиции 0 второго операнда ( y ), соответственно бит в позиции 1 первого операнда ( x ) вычисляется с битом в позиции 1 второго операнда ( y ) и т.д. При таких вычислениях результирующее значение любого бита определяется по следующим формулам:

0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 = 1

Пример.

# Битовая операция & (И, AND) x = 37 y = 58 z = x & y # z = 32 print('x = ', x) print('y = ', y) print('z = ', z)

Результат работы программы

x = 37 y = 58 z = 32

5. Битовый оператор ^ (исключающее ИЛИ, XOR). Пример

Битовый оператор исключительное ИЛИ обозначается символом ^ и выполняет операцию сложения по модулю 2 для любого бита операндов. Общая форма оператора следующая

op1 ^ op2

где op1 , op2 – целочисленные операнды.

Оператор исключающего ИЛИ (XOR) оперирует двоичными разрядами. Каждый операнд рассматривается как последовательность бит. Результат побитового исключающего ИЛИ определяется по следующим формулам

0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0

На рисунке 3 отображен пример битового исключающего ИЛИ для двух операндов.

Рисунок 3. Битовый оператор «исключающее ИЛИ»

Пример.

# Битовый оператор - исключающее ИЛИ (XOR) x = 37 y = 58 z = x ^ y # z = 31 print('x = ', x) print('y = ', y) print('z = ', z)

Результат работы программы

x = 37 y = 58 z = 31

6. Битовый оператор | ИЛИ (OR). Пример

Битовый оператор ИЛИ (OR) есть бинарным и обозначается символом | . Оператор реализует побитовое логическое сложение по образцу операторов & и ^ (см. п.п. 4, 5).

Общая форма битового оператора | следующая

op1 | op2

где op1 , op2 – операнды, которые могут быть переменными или числами целого типа.

Для двух операндов op1 , op2 битовое ИЛИ выполняется в соответствии со следующими правилами

0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1

На рисунке 4 продемонстрирована работа битового оператора ИЛИ на примере двух произвольных операндов

Рисунок 4. Битовый оператор ИЛИ

Пример.

# Битовое ИЛИ (OR) x = 37 y = 58 z = x | y # z = 63 print('x = ', x) print('y = ', y) print('z = ', z)

Результат работы программы

x = 37 y = 58 z = 63

7. Примеры использования битовых операторов

Пример 1. Вытянуть из числа 4,5,6 биты и определить их целочисленное значение.

# Вытянуть 4,5,6 биты целого числа # ввести целое число number = int(input('Input number: ')) # фильтр на 4,5,6 биты number &= 0b1110000 # сдвинуть на 4 разряда вправо number >>= 4 print('number = ', number)

Результат работы программы

Input number: 95 number = 5

Пример 2. Умножить значения двух чисел. В первом числе взять биты, которые размещенные в позициях 0-5. Во втором числе взять биты, которые размещены в позициях 0-7.

# Умножить 0-5 биты первого числа на 0-7 биты второго числа # ввести целые числа x = int(input('x = ')) y = int(input('y = ')) # фильтр на 0-5 биты x &= 0b11111 # фильтр на 0-7 биты y &= 0b1111111 # умножить z = x*y print('x = ', x) print('y = ', y) print('z = ', z)

Результат работы программы

x = 234234253 y = 322797987 x = 13 y = 35 z = 455

Связанные темы

• Математические (арифметические) операторы. Примеры
• Операторысравнения

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

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

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

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

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

Побитовое И

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

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

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

Побитовое НЕ

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

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

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

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

Операторы сдвига [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

Какой логической побитовой операции нет в python
Для начала представим себе, что данные в компьютерах хранятся в ячейках-"битах", каждое из которых может принимать 10 разных значений. В таком случае очень легко хранить положительные целые числа: каждое число по цифрам записывается в ячейки памяти. Реальный процессор может выполнять арифметические с такими числами, но есть проблема: чем больше цифр в числах, которые он сможет складывать за одну операцию (такт), тем сложнее его проектировать, тем больше тепла он выделяет и энергии потребляет. Поэтому необходимо выбрать некоторое фиксированную "стандартную" длину чисел так, чтобы с одной стороны для большей части основных задач числа туда помещались, с другой стороны были наиболее короткими. Например, можно выбрать длину в 10 цифр для "обычных" чисел и длину 20 для "длинных" (операций с длинными целыми числами за один такт процессора будет выполняться меньше). Кстати, нам потребуется хранить ещё и знак числа. Как лучше всего это сделать — вопрос очень хороший.
В реальности используется несколько подходов к хранению знака числа, вернее даже к хранению просто целых чисел. Самый "популярный" в данный момент называется "дополнение до двойки" (two’s complement), что для нашего воображаемого десятичного процессора превращается в "дополнение до десятки". Основная идея подхода состоит в следующем. Так как наши числа ограничены 10-ю цифрами, то если в результате арифметической операции возникнет перенос через разряд в 11-ю цифру, то он будет потерян. В таких случаях говорят, что вычисления производятся по модулю $10^$. Пусть у нас есть два числа: отрицательное $x$ и положительное $y$, и нам нужно вычислить $x+y$. Заметим, что по замечанию выше $x+y\equiv (10^+x) + y$ (ведь добавление лишнего $10^$ ничего не меняет, у нас нет "места", чтобы хранить эту цифру). Но число $(10^+x)$ уже заведомо положительное.
Итак, ровно в этом состоит идея: для хранения отрицательного числа $x$ используется положительное число $(10^+x)$. Неотрицательные числа от 0000000000 до 4999999999 хранятся как есть. А числа от 5000000000 до 9999999999 отдаются отрицательным числам, причём $-1$ превращается в $10^-1 = 9999999999$, $-2$ превращается в $10^-2 = 9999999998$, и так далее, $-5000000000$ превращается в. в $-5000000000$. Заметим, что отрицательных чисел "поместилось" на одно больше, чем положительных.
Вот примеры: сложим $8\,512$ и $-3\,628$. $$10^-3628 = 9\,999\,996\,372.$$ Далее $$8\,512 + (-3\,628) \equiv 8\,512 + 9\,999\,996\,372 = 10\,000\,004\,884 \equiv 4\,884.$$ 
Сложим $-6\,460$ и $-9\,290$. $$(-6\,460) + (-9\,290) \equiv (10^-6\,460) + (10^-9\,290) = 9\,999\,993\,540 + 9\,999\,990\,710 = $$ $$= 19\,999\,984\,250 \equiv 9\,999\,984\,250 \equiv 9\,999\,984\,250 - 10^ = (-15\,750).$$
В чём выгода такого подхода? Во-первых, используются все возможные значения (если знак хранить в первой цифре, то будут "потеряны" 80% чисел). Во-вторых, с таким подходом отрицательные числа ничем не отличаются от положительных и не требуется усложнения схем для организации арифметических операций с ними. По модулю $10^$ отлично работают все арифметические операции, поэтому работать будут и вычитание, и умножение.
В реальных чипах используется двоичная система счисления, но в остальном всё устроенно именно так. Один бит — это двоичная цифра. И существуют числа разной длины — в 8, 16, 32 и 64 двоичных цифры. Это зависит от реальных чипов.
Битовое представление целых чисел и битовые операции
Итак, переменные типа int хранятся в двоичной системе счисления в виде последовательности двоичных цифр — бит. Биты нумеруются от 0, биты будем записывать справа налево (то есть бит с номером 0 будет записан самым правым, а самый старший бит — самым левым).
a = 0 # 0b0 a = 1 # 0b1 a = 2 # 0b10 a = 10 # 0b1010 a = 255 # 0b11111111
Например, если a = 10 , то в битовой записи a биты с номерами 1 и 3 равны 1, а остальные биты равны 0.
В программах на языке Питон числа в двоичной системе счисления можно записывать в виде последовательностей из 0 и 1, предваряя их префиксом 0b . Например, допустимо присваивание a = 0b101 .
Для двух переменных одинакового скалярного типа определены битовые операции: 
& битовое И (AND) 
| битовое ИЛИ (OR) 
^ битовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) 
~ битовое ОТРИЦАНИЕ (NOT) — унарная операция.
Битовые операторы работают следующим образом. Берутся два операнда, и к каждой паре соответствующих бит для левого и правого операнда применяется данная операция, результатом будет переменная того же типа, каждый бит которой есть результат применения соответствующей логической операции к соответствующим битам двух операндов. Рассмотрим пример:
a = 5 # 0b101 b = 6 # 0b110 c = a & b # 0b100 == 4 d = a | b # 0b111 == 7 e = a ^ b # 0b11 == 3 f = ~ a # 0b1. 11111010 == -6
Битовое отрицание числа (величина f в последнем примере) — это число, полученное из исходного заменой всех нулей на единицы и наоборот.
Применение побитового отрицания к неотрицательному числу даст отрицательное число, что связано с особенностями представления отрицательных чисел в виде дополнительного кода. Про это чуть ниже.
Есть еще две операции, работающие с битами: это битовые сдвиги. Их два: сдвиг влево и вправо. Оператор a >> n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например:
a = 43 # 0b101011 b = a >> 1 # 0b10101 == 21 c = a >> 2 # 0b1010 == 10 d = a >> 3 # 0b101 == 5 e = a >> 5 # 0b1 == 1
Понятно, что для положительных чисел битовый сдвиг числа вправо на n равносилен целочисленному делению на 2 n . Для отрицательных чисел в языке Питон операции битового сдвига неприменимы.
Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2 n и осуществляется при помощи оператора 
a = 5 # 0b101 b = a 
Если необходимо применить битовую операцию к переменной и результат сохранить в ней же, то можно использовать стандартные конструкции
n &= k n |= k n ^= k n >= k
Тонкости битового представления целых чисел в Python
Как вам уже известно, целые числа в питоне ограничены лишь объёмом оперативной памяти, то есть могут быть весьма и весьма большими. В этом случае можно представлять себе битовую запись целых чисел так. Если число положительно, то слева от записи числа идёт бесконечное количество 0. А если число отрицательно, то слева идёт бесконечное количество 1. Число -1 записывается как последовательность из одних лишь единиц: -1 = . 111 , а число 0 — из одних лишь нулей 0 = . 000 . То есть 21, это не просто 10101 , а . 00010101 . Таким образом, ~21 — это число вида . 11101010 , то есть бесконечное количество 1, а затем 01010 .
Как понять, какому целому числу соответствует такая запись? Если слева нули, то число положительно, и всё просто: отбрасываем ведущие нули, получаем число в двоичной записи. А если слева единицы? Для этого найдём самую правую 1, после которой слева идут только 1. В нашем примере получится вот такая единица: 100000 . Очевидно, что в двоичной записи после такой единицы сразу идёт 0 (кроме случая, когда в двоичной записи вообще только 1, то есть кроме числа -1). Таким образом, число разбивается на бесконечную «голову» единиц . 11100000 и хвост после первого нуля (возможно пустой) — 1010 . Итоговое число равно их разности: . 11101010 = 0b1010 - 0b100000 = -22 .
Заметим, что для любого целого числа x сумма x + ~x — это бесконечная последовательность единиц. Это то самое число -1. То есть в питоне ~x = -1 - x .
Упражнения
Во всех упражнениях (если не оговорено иное) нельзя использовать арифметические операторы сложения, умножения, вычитания, деления, взятия остатка. Вместо них используем побитовые операторы & , | , ~ , ^ , > .
A: 2 k
Дано число k, 0⩽k⩽31. Запишите число 2 k , то есть число, у которого k-й бит равен 1, а остальные — нули.


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

Betternet что это
Как открыть несколько файлов в python
Как разместить форму по центру html
Почему впн не меняет местоположение