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

Question

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

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) я понимаю сдвиг влево, но не два других.

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

Answer 1

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

• 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 бита.
• << 4 - это 4-битный сдвиг влево для перемещения val1 в верхние 4 бита 8-битного значения.
• | просто объединяет эти два.

Если val1 равно 7, а val2 равно 4:

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

Answer 2

Одно типичное использование:

| используется для установки определенного бита на 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 используется для проверки, равен ли бит 0 из x 1 или 0

Answer 3

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

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

Например, вот функция Python который принимает строку типа #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)

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

Answer 4

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

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

Был рассмотрен только частично. Это мои два цента по этому вопросу.

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

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

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

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

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

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

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

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

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

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

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

Answer 5

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

x | 2

0001 //x
0010 //2

0011 //result = 3

---

x & 1

0001 //x
0001 //1

0001 //result = 1

Answer 6

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

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

Answer 7

Думайте о 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) Если ни один из битов не перекрывается (что в данном случае верно) | действует как сложение.

Answer 8

Этот пример покажет вам операции для всех четырех 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]

Answer 9

Наборы

Наборы могут быть объединены с использованием математических операций.

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

Попробуйте сами:

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}

Answer 10

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

Хорошим и довольно простым примером этого является общее решение игры Nim. Взгляните на код Python на странице Википедии . Это делает интенсивное использование побитового эксклюзива или, ^.