Побитовая операция и использование

Рассмотрим этот код:

x = 1        # 0001
x << 2       # Shift left 2 bits: 0100
# Result: 4

x | 2        # Bitwise OR: 0011
# Result: 3

x & 1        # Bitwise AND: 0001
# Result: 1

Я могу понимать арифметические операторы в Python (и других языках), но я никогда не понимал достаточно хорошо «побитовые» операторы. В приведенном выше примере (из книги Python) я понимаю левый сдвиг, но не два других.

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

Поразрядные операторы - это операторы, которые работают с многобитными значениями, но концептуально по одному за раз.

• ANDравен 1, только если оба его входа равны 1, в противном случае - 0.
• ORравен 1, если один или оба его входа равны 1, в противном случае - 0.
• XORравен 1, только если ровно один из его входов равен 1 , в противном случае - 0.
• NOT равен 1, только если его вход равен 0, в противном случае - 0.

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

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+-----    ---+----     ----+----    ----+----
 0  | 0 0      0 | 0 1       0 | 0 1        | 1 0
 1  | 0 1      1 | 1 1       1 | 1 0

Одним из примеров является то, что если вам нужны только младшие 4 бита целого числа, вы И его с 15 (двоичный 1111), поэтому:

    201: 1100 1001
AND  15: 0000 1111
------------------
 IS   9  0000 1001

Нулевые биты в 15 в этом случае эффективно действуют как фильтр, заставляя биты в результате также быть нулевыми.

Кроме того, >>и <<часто включаются как побитовые операторы, и они «сдвигают» значение соответственно вправо и влево на определенное количество бит, отбрасывая биты, которые катятся на конце, к которому вы смещаетесь, и вводя нулевые биты в другой конец.

Так, например:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Обратите внимание, что левый сдвиг в Python необычен тем, что он не использует фиксированную ширину, при которой отбрасываются биты - в то время как многие языки используют фиксированную ширину в зависимости от типа данных, Python просто расширяет ширину для обслуживания дополнительных бит. Чтобы получить поведение отбрасывания в Python, вы можете следовать за левым сдвигом с побитовым сдвигом, andнапример, в 8-битном значении, сдвигающем влево четыре бита:

bits8 = (bits8 << 4) & 255

Имея это в виду, другой пример побитовых операторов: если у вас есть два 4-битных значения, которые вы хотите упаковать в 8-битное, вы можете использовать все три своих оператора ( left-shift, andи or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)

• & 15Операция будет убедиться , что оба значения имеют только младшие 4 бита.
• Это << 44-битный сдвиг влево для перехода val1к верхним 4 битам 8-битного значения.
• |Просто объединяет эти два вместе.

Если val17 и val24:

                val1            val2
                ====            ====
 & 15 (and)   xxxx-0111       xxxx-0100  & 15
 << 4 (left)  0111-0000           |
                  |               |
                  +-------+-------+
                          |
| (or)                0111-0100

Типичное использование:

| используется для установки определенного бита в 1

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

• Установите бит (где n - номер бита, а 0 - младший бит):

  unsigned char a |= (1 << n);

• Немного проясни:

  unsigned char b &= ~(1 << n);

• Немного переключить:

  unsigned char c ^= (1 << n);

• Протестируйте немного:

  unsigned char e = d & (1 << n);

Возьмем, к примеру, случай из вашего списка:

x | 2используется для установки бита 1 xв 1

x & 1используется для проверки того, xравен ли бит 0 значения 1 или 0

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

Одним из наиболее распространенных способов использования побитовых операций является анализ шестнадцатеричных цветов.

Например, вот функция Python, которая принимает строку типа String #FF09BEи возвращает кортеж ее значений Red, Green и Blue.

def hexToRgb(value):
    # Convert string to hexadecimal number (base 16)
    num = (int(value.lstrip("#"), 16))

    # Shift 16 bits to the right, and then binary AND to obtain 8 bits representing red
    r = ((num >> 16) & 0xFF)

    # Shift 8 bits to the right, and then binary AND to obtain 8 bits representing green
    g = ((num >> 8) & 0xFF)

    # Simply binary AND to obtain 8 bits representing blue
    b = (num & 0xFF)
    return (r, g, b)

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

Думаю, что вторая часть вопроса:

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

Решено лишь частично. Это мои два цента по этому поводу.

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

Во всех приложениях, которым необходимо отправлять данные между двумя узлами, например:

• компьютерные сети;

• телекоммуникационные приложения (сотовые телефоны, спутниковая связь и т. д.).

На более низком уровне связи данные обычно отправляются так называемыми кадрами . Фреймы - это просто строки байтов, которые отправляются по физическому каналу. Эти кадры обычно содержат фактические данные плюс некоторые другие поля (закодированные в байтах), которые являются частью того, что называется заголовком . Заголовок обычно содержит байты, которые кодируют некоторую информацию, относящуюся к состоянию связи (например, с флагами (битами)), счетчиками кадров, кодами исправления и обнаружения ошибок и т. Д. Для получения переданных данных в кадре и для построения кадры для отправки данных, которые вам понадобятся для выполнения побитовых операций.

В общем, при работе с такими приложениями доступен API, поэтому вам не нужно разбираться со всеми этими деталями. Например, все современные языки программирования предоставляют библиотеки для подключений к сокетам, поэтому вам на самом деле не нужно создавать фреймы связи TCP / IP. Но подумайте о хороших людях, которые запрограммировали эти API для вас, им наверняка приходилось иметь дело с конструкцией фреймов; использование всевозможных поразрядных операций для перехода от низкоуровневой связи к высокоуровневой.

В качестве конкретного примера представьте, что кто-то дает вам файл, содержащий необработанные данные, которые были захвачены непосредственно телекоммуникационным оборудованием. В этом случае, чтобы найти фреймы, вам нужно будет прочитать необработанные байты в файле и попытаться найти какие-то слова синхронизации, побитно просканировав данные. После определения слов синхронизации вам нужно будет получить фактические кадры и при необходимости ПЕРЕМЕСТИТЬ их (и это только начало истории), чтобы получить фактические данные, которые передаются.

Еще одно совершенно другое семейство приложений низкого уровня - это когда вам нужно управлять оборудованием с помощью некоторых (древних) портов, таких как параллельные и последовательные порты. Эти порты управляются установкой нескольких байтов, и каждый бит этих байтов имеет определенное значение с точки зрения инструкций для этого порта (см., Например, http://en.wikipedia.org/wiki/Parallel_port ). Если вы хотите создать программное обеспечение, которое что-то делает с этим оборудованием, вам потребуются побитовые операции для преобразования инструкций, которые вы хотите выполнить, в байты, которые понимает порт.

Например, если у вас есть какие-то физические кнопки, подключенные к параллельному порту для управления другим устройством, это строка кода, которую вы можете найти в программном приложении:

read = ((read ^ 0x80) >> 4) & 0x0f; 

Надеюсь, это поможет.

Надеюсь, это проясняет эти два:

x | 2

0001 //x
0010 //2

0011 //result = 3

x & 1

0001 //x
0001 //1

0001 //result = 1

Считайте 0 ложным, а 1 истинным. Затем побитовое и (&) и или (|) работают так же, как и обычные и, за исключением того, что они обрабатывают все биты в значении одновременно. Обычно вы увидите, что они используются для флагов, если у вас есть 30 параметров, которые можно установить (скажем, как стили рисования в окне), вы не хотите передавать 30 отдельных логических значений для установки или отключения каждого из них, поэтому вы используете | для объединения параметров в одно значение, а затем вы используете &, чтобы проверить, установлена ​​ли каждая опция. Этот стиль передачи флагов широко используется OpenGL. Поскольку каждый бит является отдельным флагом, вы получаете значения флагов по степени двойки (например, числа, у которых установлен только один бит) 1 (2 ^ 0) 2 (2 ^ 1) 4 (2 ^ 2) 8 (2 ^ 3) степень двойки сообщает вам, какой бит установлен, если флаг установлен.

Также обратите внимание, что 2 = 10, поэтому x | 2 равно 110 (6), а не 111 (7) Если ни один из битов не перекрывается (что в данном случае верно) | действует как дополнение.

Я не видел этого, упомянутого выше, но вы также увидите, что некоторые люди используют сдвиг влево и вправо для арифметических операций. Сдвиг влево на x эквивалентен умножению на 2 ^ x (если он не переполняется), а сдвиг вправо эквивалентен делению на 2 ^ x.

Недавно я видел людей, использующих x << 1 и x >> 1 для удвоения и уменьшения вдвое, хотя я не уверен, просто ли они пытаются быть умными или действительно есть явное преимущество перед обычными операторами.

Наборы

Наборы можно комбинировать с помощью математических операций.

• Оператор объединения |объединяет два набора, чтобы сформировать новый, содержащий элементы в любом из них.
• Оператор пересечения &получает элементы только в обоих.
• Оператор разницы -получает элементы в первом наборе, но не во втором.
• Оператор симметричной разности ^получает элементы в любом наборе, но не в обоих.

Попробуй сам:

first = {1, 2, 3, 4, 5, 6}
second = {4, 5, 6, 7, 8, 9}

print(first | second)

print(first & second)

print(first - second)

print(second - first)

print(first ^ second)

Результат:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

{4, 5, 6}

{1, 2, 3}

{8, 9, 7}

{1, 2, 3, 7, 8, 9}

Этот пример покажет вам операции для всех четырех 2-битных значений:

10 | 12

1010 #decimal 10
1100 #decimal 12

1110 #result = 14

10 & 12

1010 #decimal 10
1100 #decimal 12

1000 #result = 8

Вот один из примеров использования:

x = raw_input('Enter a number:')
print 'x is %s.' % ('even', 'odd')[x&1]

Другой распространенный вариант использования - это управление / тестирование прав доступа к файлам. См. Модуль статистики Python: http://docs.python.org/library/stat.html .

Например, чтобы сравнить разрешения файла с желаемым набором разрешений, вы можете сделать что-то вроде:

import os
import stat

#Get the actual mode of a file
mode = os.stat('file.txt').st_mode

#File should be a regular file, readable and writable by its owner
#Each permission value has a single 'on' bit.  Use bitwise or to combine 
#them.
desired_mode = stat.S_IFREG|stat.S_IRUSR|stat.S_IWUSR

#check for exact match:
mode == desired_mode
#check for at least one bit matching:
bool(mode & desired_mode)
#check for at least one bit 'on' in one, and not in the other:
bool(mode ^ desired_mode)
#check that all bits from desired_mode are set in mode, but I don't care about 
# other bits.
not bool((mode^desired_mode)&desired_mode)

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

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

Хороший и довольно простой пример этого - общее решение игры Ним. Взгляните на код Python на странице Википедии . Он широко использует побитовое исключающее или, ^.

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

import numpy as np
a=np.array([1.2, 2.3, 3.4])
np.where((a>2) and (a<3))      
#Result: Value Error
np.where((a>2) & (a<3))
#Result: (array([1]),)

Я не видел, чтобы это упоминалось, этот пример покажет вам десятичную операцию (-) для 2-битных значений: AB (только если A содержит B)

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

111 #decimal 7
-
100 #decimal 4
--------------
011 #decimal 3

с python: 7 & ~ 4 = 3 (удалите из 7 биты, которые представляют 4)

001 #decimal 1
-
100 #decimal 4
--------------
001 #decimal 1

с python: 1 & ~ 4 = 1 (удалите из 1 биты, которые представляют 4 - в этом случае 1 не содержит 4) ..

Хотя манипулирование битами целого числа полезно, часто для сетевых протоколов, которые могут быть указаны с точностью до бита, может потребоваться манипулирование более длинными последовательностями байтов (которые нелегко преобразовать в одно целое число). В этом случае полезно использовать библиотеку битовых цепочек, которая позволяет выполнять побитовые операции с данными - например, можно импортировать строку 'ABCDEFGHIJKLMNOPQ' как строку или как шестнадцатеричный и сдвинуть ее бит (или выполнить другие побитовые операции):

>>> import bitstring
>>> bitstring.BitArray(bytes='ABCDEFGHIJKLMNOPQ') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')
>>> bitstring.BitArray(hex='0x4142434445464748494a4b4c4d4e4f5051') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')

следующие побитовые операторы: & , | , ^ и ~ возвращают значения (в зависимости от их ввода) точно так же, как логические элементы влияют на сигналы. Вы можете использовать их для имитации схем.

Чтобы перевернуть биты (например, дополнение / инвертирование до 1), вы можете сделать следующее:

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

In Binary
a=1010 --> this is 0xA or decimal 10
then 
c = 1111 ^ a = 0101 --> this is 0xF or decimal 15
-----------------
In Python
a=10
b=15
c = a ^ b --> 0101
print(bin(c)) # gives '0b101'