Битовая операция — это операция, с которой мы часто сталкиваемся в программировании, но все еще есть много разработчиков, которые не понимают битовую операцию, что приводит к «отступлению» при встрече с битовой операцией. На самом деле битовая операция не так уж сложна, пока мы понимаем основы ее работы и правила работы операторов, мы можем освоить знание битовой операции. Далее, давайте вместе узнаем о битовых операциях.
Числа в программе существуют в двоичной форме в памяти компьютера, а битовая операция заключается в непосредственном управлении соответствующими двоичными битами целого числа в памяти.
Примечание. В этой статье обсуждаются только целочисленные операции, а десятичные операции в эту статью не включены.
Основы битовых операций
наш обычный3,5Равные числа представлены в десятичном виде, а битовые операции основаны на двоичном. То есть люди используют десятичные числа, а машины используют двоичные.Чтобы глубже понять битовые операции, вам необходимо понять метод преобразования и соответствующие отношения между десятичным и двоичным числами.
бинарный
При преобразовании из десятичного числа в двоичное используйте метод «разделить на 2, взять остаток и расположить в обратном порядке»:
- Разделите десятичное число на 2, чтобы получить частное и остаток;
- Разделите частное на 2, чтобы получить новое частное и остаток;
- Повторяйте шаги 1 и 2, пока частное не станет равным 0;
- Возьмите остаток, полученный первым, как старший порядок двоичного числа, а остаток, полученный позже, как младший порядок двоичного числа;
Результатом сортировки является двоичное представление десятичного числа. например десятичное число101Процесс вычисления для преобразования в двоичные числа выглядит следующим образом:
101 % 2 = 50 余 1
50 % 2 = 25 余 0
25 % 2 = 12 余 1
12 % 2 = 6 余 0
6 % 2 = 3 余 0
3 % 2 = 1 余 1
1 % 2 = 0 余 1
Обратный порядок, то есть сортировка от старшего к младшему в двоичном коде, дает7Битовое двоичное число1100101, если вы хотите преобразовать в8Битовое двоичное число, нужно заполнить старший бит0. то есть десятичное число8Битовое двоичное число01100101.
Полный процесс показан на следующем рисунке:
Некоторые пользователи сети составили общую таблицу сравнения базы и кода ASCII, содержание которой выглядит следующим образом:
управляющие символы ASCII
Отображаемые символы ASCII
дополнять
Теперь мы изучили метод преобразования между двоичным и десятичным числом и имеем базовую таблицу сравнения. Но прежде чем мы начнем изучать побитовые операторы, нам также нужно узнать о дополнении до двух.
Есть положительные и отрицательные значения, тогда только0и1Как представить положительное и отрицательное в двоичном формате?
Люди установили, что старший бит в двоичном коде равен0представляет собой положительное, для1представляет собой отрицательный. Например0000 1100Соответствующее десятичное число12,и1000 1100Соответствующее десятичное число-12. Это представление называется исходным кодом. Но возникла новая проблема: старший бит исходного двоичного файла всегда0, чтобы указать положительное и отрицательное, есть еще1, при выполнении операции возникает ошибка. Например,1 + (-2)Бинарная операция выглядит следующим образом:
0000 0001 + 1000 0010
= 1000 0011
= -3
Это, очевидно, проблема, проблема заключается в самом высоком положении, представляющем положительное и отрицательное. Затем люди придумали дополнение до единицы (бинарное положение0и1обмен, напр.0000 1100Обратный код1111 0011). На этом этапе операция будет выглядеть так:
0000 0001 + 1111 1101
= 1111 1110
# 在转换成十进制前，需要再次反码
= 1000 0001
= -1
На этот раз вроде правильно. Но все же есть исключения, давайте посмотрим1 + (-1):
0000 0001 + 1111 + 1110
= 1111 1111
= 1000 0000
= -0
Ноль не делится на положительный и отрицательный, для решения этой проблемы была разработана концепция дополнительного кода. Дополнение до двух состоит в том, чтобы превратить отрицательные числа в положительные числа, которые можно складывать, поэтому负数的补码= 负数的绝对值取反 + 1,Например-1Дополнение:
-1 的绝对值 1
= 0000 0001 # 1 的二进制原码
= 1111 1110 # 原码取反
= 1111 1111 # +1 后得到补码
-1Полный процесс получения дополнения до двух показан на следующем рисунке:
И наоборот, процесс получения исходного кода из дополнительного кода выглядит следующим образом.原码 = 补码 - 1，再求反. Следует отметить, что в процессе инверсии значение старшего бита остается неизменным, чтобы гарантировать, что положительный и отрицательный результат не будет ошибочным. Например1 + (-6)и1 + (-9)Процесс операции выглядит следующим образом:
# 1 的补码 + -6 的补码
0000 0001 + 1111 1010
= 1111 1011 # 补码运算结果
= 1111 1010 # 对补码减 1，得到反码
= 1000 0101 # 反码取反，得到原码
= -5 # 对应的十进制
# 1 的补码 + -9 的补码
0000 0001 + 1111 0111
= 1111 1000 # 补码运算结果
= 1111 0111 # 对补码减 1，得到反码
= 1000 1000 # 反码取反，得到原码
= -8 # 对应的十进制
Следует отметить, что дополнение положительных чисел такое же, как и исходный код, и никаких дополнительных операций не требуется. Можно также сказать, что появление дополнительного кода должно решить проблему знака в операции с отрицательным числом.
Жизнь слишком коротка, я использую Python.
Цуй Цинцай | Цзин Ми приглашает вас обратить внимание на паблик WeChat: Coder of Attack
Введение оператора
Существует 6 типов битовых операций, это:
| название | символ |
|---|---|
| побитовое И | & |
| побитовое ИЛИ | | |
| Побитовое исключающее ИЛИ | ^ |
| побитовое отрицание | ~ |
| работа влево | << |
| правое переключение | >> |
побитовое И
Побитовая операция И И двоичные биты, соответствующие двум числам, участвующим в операции, когда соответствующие двоичные биты1, бит результата1, иначе бит результата0. Побитовый оператор И&, числа, участвующие в операции, появляются в дополнении. Например, число5и цифры8Выполнение побитовой операции И на самом деле5соответствующий двоичный файл0000 0101и цифры8соответствующий двоичный файл0000 1000Выполните побитовую операцию И, т.е.:
0000 0101
&
0000 1000
По правилу побитового И сравниваются числа в каждой позиции. Процесс операции выглядит следующим образом:
0000 0101
&
0000 1000
---- ----
0000 0000
Поскольку нет «оба» в соответствующих позициях1", так что результат0000 0000. номер5и8Полный процесс побитовой операции И выглядит следующим образом:
Преобразовав результат в десятичную форму, получим0,Сейчас5&8 = 0.
побитовое ИЛИ
Побитовая операция ИЛИ будет выполнять операцию ИЛИ соответствующих двоичных битов двух чисел, участвующих в операции, если соответствующие двоичные биты имеют1, бит результата1, иначе бит результата0. Побитовый оператор ИЛИ|, числа, участвующие в операции, появляются в дополнении. Например, число3и цифры7Побитовая операция ИЛИ на самом деле является числом3соответствующий двоичный файл0000 0011и цифры7соответствующий двоичный файл0000 0111Выполните побитовую операцию ИЛИ, т.е.:
0000 0011
|
0000 0111
По правилу побитового ИЛИ сравниваются числа в каждой позиции. Процесс операции выглядит следующим образом:
0000 0011
|
0000 0111
---- ----
0000 0111
Окончательный результат0000 0111. Преобразовав результат в десятичную форму, получим7,Сейчас3|7 = 7.
Побитовое исключающее ИЛИ
Побитовая операция XOR выполняет XOR соответствующих двоичных битов двух чисел, участвующих в операции.Когда соответствующие двоичные биты имеют разные значения, бит результата1, иначе бит результата0. Побитовый оператор XOR^, числа, участвующие в операции, появляются в дополнении. Например, число12и цифры7Выполнить побитовую операцию XOR, фактически число12соответствующий двоичный файл0000 1100и цифры7соответствующий двоичный файл0000 0111Выполните побитовую операцию XOR, т.е.:
0000 1100
^
0000 0111
По правилу побитового исключающего ИЛИ сравниваются числа в каждой позиции. Процесс операции выглядит следующим образом:
0000 1100
^
0000 0111
---- ----
0000 1011
Окончательный результат0000 1011. Преобразовав результат в десятичную форму, получим11,Сейчас12^7 = 11.
побитовое отрицание
Операция побитового отрицания преобразует каждый бит двоичного числа в0заменить1,1заменить0. Побитовый оператор отрицания~, числа, участвующие в операции, появляются в дополнении. Например, для чисел9Выполнить операцию побитовой инверсии, фактически число9соответствующий двоичный файл0000 1001Выполните побитовую операцию отрицания, то есть:
～0000 1001
= 0000 1001 # 补码，正数补码即原码
= 1111 1010 # 取反
= -10
Окончательный результат-10. Давайте посмотрим на другой пример,-20Процесс побитовой инверсии выглядит следующим образом:
～0001 0100
= 1110 1100 # 补码
= 0001 0011 # 取反
= 19
Окончательный результат19. Мы нашли закономерность из примера, а результат побитового отрицания представляется математической формулой:
Мы можем применить его к9и-20начальство:
～9 = -(9 + 1) = -10
~(-20) = -((-20) + 1) = 19
Это правило распространяется и на числа.0вверх, то есть~0 = -(0 + 1) = -1.
работа влево
Операция сдвига влево сдвигает все соответствующие двоичные биты влево на несколько битов, старшие биты отбрасываются, а младшие биты дополняются.0. Оператор операции сдвига влево<<. Например, число5сдвиг влево4бит, который на самом деле является числом5соответствующий двоичный файл0000 0101сдвинуть бинарник влево4биты, то есть:
5 << 4
= 0000 0101 << 4
= 0101 0000 # 高位丢弃，低位补 0
= 80
номер5сдвиг влево4Полный процесс работы биты выглядит следующим образом:
Окончательный результат80. Это эквивалентно:
Другими словами, правило операции сдвига влево:
правое переключение
Операция сдвига вправо сдвигает все соответствующие двоичные биты вправо на определенное количество битов. Для пустого места слева, если это положительное число, то заполнить его0, отрицательные числа могут дополнять0или1(Turbo C и многие компиляторы предпочитают дополнять1). Оператор сдвига вправо>>. Например, число80переместить вправо4бит, который на самом деле является числом80соответствующий двоичный файл0101 0000переместить двоичный файл вправо4биты, то есть:
80 >> 4
= 0101 0000 >> 4
= 0000 0101 # 正数补0，负数补1
= 5
Окончательный результат5. Это эквивалентно:
Другими словами, правило операции сдвига вправо:
Следует отметить, что когда оно не делится, берется целое число. Правила деления и округления здесь аналогичныPYTHONПол языка кроме.
Cool Life Я использую Rust
Wei Shidong | Quinn предлагает обратить внимание на паблик WeChat: The Zen of Rust
Применение битовых операций
Освоив знания о битовых операциях, мы можем попробовать использовать их в разработке. Ходили слухи, что битовые операции эффективны и быстры, но они никогда не были доказаны в литературе, поэтому в этой статье вопросы эффективности и скорости не обсуждаются. Если вы читаете статью и у вас есть соответствующая литература, пожалуйста, оставьте сообщение, чтобы сообщить, спасибо.
Оценка цифрового паритета
Обычно мы судим, является ли число нечетным или четным, взяв остаток. Например, судить101Используемый метод паритета:
# python
if 101 % 2:
print('偶数')
else:
print('奇数')
Мы также можем реализовать оценку четности с помощью побитового И в битовых операциях, например:
# python
if 101 & 1:
print('奇数')
else:
print('偶数')
Это связано с тем, что младший двоичный бит нечетного числа всегда1, а двоичный минимум четных чисел всегда0. Таким образом, независимо от любого нечетного числа с1который0000 0001что вы получаете1, с ним суммируется любое четное число0.
своп переменной
В языке C обмен двумя переменными должен осуществляться через третью переменную. Псевдокод выглядит следующим образом:
# 伪代码
a = 3, b = 5
c = a
a = b
b = a
--------
a = 5, b = 3
В языке PYTHON это не так хлопотно и можно обмениваться напрямую. Соответствующий код PYTHON выглядит следующим образом:
# python
a, b = 3, 5
a, b = b, a
print(a, b)
Результат выполнения кода5 3. Однако большинство языков программирования не поддерживают метод записи PYTHON, в этом случае мы можем реализовать обмен переменными через побитовое XOR в битовой операции. Соответствующий псевдокод выглядит следующим образом:
# 伪代码
a = 3, b = 5
a = a ^ b
b = a ^ b
a = a ^ b
Наконец,a = 5, b = 3. Мы можем использовать язык C и язык PYTHON для проверки, соответствующий код PYTHON выглядит следующим образом:
# python
a, b = 3, 5
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b)
Результат выполнения кода5 3, указывая на то, что обмен переменными прошел успешно. Соответствующий код C выглядит следующим образом:
#include<stdio.h>
void main()
{
int a = 3, b = 5;
printf("交换前：a=%d , b=%d\n",a,b);
a = a^b;
b = a^b;
a = a^b;
printf("交换后：a=%d , b=%d\n",a, b);
}
Результат выполнения кода следующий:
交换前：a=3 , b=5
交换后：a=5 , b=3
Это означает, что обмен переменными прошел успешно.
Найдите n-й продукт x и 2
Пусть число будетx, попрошайничествоxи2изnПродукт питания. Это очень просто вычислить математически:
В битовой операции для достижения этого требования нужно использовать только операцию сдвига влево, а именноx << n.
взять k-й бит x
взять номерxсоответствующее двоичное числоkДвоичное значение бита. Предположим, что число5, его соответствующий двоичный файл0000 0101, возьми первыйkПобитовые операции над двоичными значениямиx >> k & 1. Мы можем проверить код PYTHON:
# python
x = 5 # 0000 0101
for i in range(8):
print(x >> i & 1)
Результат выполнения кода следующий:
1
0
1
0
0
0
0
0
Это показывает, что алгоритм битовой операции правильный и может удовлетворить наши потребности.
Назначение решения
if a == x:
x = b
else:
x = a
равноx = a ^ b ^ x. Мы можем проверить это с помощью кода PYTHON:
# python
a, b, x = 6, 9, 6
if a == x:
x = b
else:
x = a
print(a, b, x)
Результат выполнения кода699, эквивалентный код выглядит следующим образом:
# python
a, b, x = 6, 9, 6
x = a ^ b ^ x
print(a, b, x)
Это экономитif elseсудебное заявление.
вместо демонтажа пола
Двоичный поиск является одним из наиболее часто используемых алгоритмов, но он имеет определенные предварительные условия: цель двоичного поиска должна иметь последовательную структуру хранения, а элементы расположены по порядку. Например, упорядоченные списки в PYTHON. Оптимальная сложность бинарного поиска равнаO(1), наихудшая временная сложностьO(log n). В качестве примера, допустим, нам нужно начать со списка[1, 3, 5, 6, 7, 8, 12, 22, 23, 43, 65, 76, 90, 543]Найдите индекс указанного элемента в , и соответствующий код PYTHON выглядит следующим образом:
# python
def search(lis: list, x: int) -> int:
"""非递归二分查找
返回指定元素在列表中的索引
-1 代表不存在"""
mix_index = 0
max_index = len(lis) - 1
while mix_index <= max_index:
midpoint = (mix_index + max_index) // 2
if lis[midpoint] < x:
mix_index = mix_index + 1
elif lis[midpoint] > x:
max_index = max_index - 1
else:
return midpoint
return -1
lists = [1, 3, 5, 6, 7, 8, 12, 22, 23, 43, 65, 76, 90, 543]
res = search(lists, 76)
print(res)
Оператор, используемый при выборе среднего значения списка,midpoint = (mix_index + max_index) // 2, т.е. поэтажное деление, можно заменить наmidpoint = (mix_index + max_index) >> 1Конечный результат тот же. Это потому, что сдвиг влево1бит эквивалентен умножению на2, при смещении вправо1бит эквивалентен делению на2. Таких случаев много, здесь повторяться не буду.
На данный момент у нас есть определенное понимание битовых операций, и я надеюсь, что вы используете битовые операции в своей работе. БолееSaoperationи знания, отсканируйте QR-код ниже.