Взлом битов — это то, что вы делаете, когда читаете или записываете отдельные биты большего числа. Чтение и запись байтов довольно тривиальны, но байт — это наименьший фрагмент, для которого большинство языков предоставляют функции. Если вы хотите получить доступ к битам, вам придется использовать так называемые побитовые операторы, такие как or, and, xor, not или shift. Поскольку мы возимся с числами, оператор для получения того, что мы хотим, не так прост, как имя функции. И это кажется низким уровнем, отсюда и термин «битовый взлом».

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

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

Я полагаю, что было бы неплохо прояснить разницу между «логическими» операторами и их «битовой» эквивалентной частью, потому что в программировании высокого уровня мы больше подвержены первому. Например, у нас часто есть оператор if, и 2 условия должны быть true.

if itIsTime and foodIsWarm:
  eat()

То, как «правдивость» определяется в каждом языке программирования, не обязательно является постоянным и является источником споров, но в отношении чисел общее правило таково: «0» — это false, а любое другое число — это true. В то время как побитовые операторы будут делать то же самое, но с каждым битом числа.

Сначала мы увидим, что они делают. Начнем с not, так как у него только один операнд. Обычно он представлен символом тильды ~ и в основном инвертирует все биты операнда.

~ 01010101
  --------
= 10101010

Если бы вместо этого мы использовали «логическое» not, результат был бы false или 00000000, поскольку ненулевое значение равно true.

Теперь побитовое and обычно представляется одним &. Каждый бит в результате будет равен «1», если тот же бит в каждом операнде также равен «1».

  01010101
& 11000011
  --------
= 01000001

Побитовое or обычно представляется одним |. Каждый бит в результате будет равен «1», если хотя бы в одном из операндов один и тот же бит установлен в «1».

  01010101
| 11000011
  --------
= 11010111

Побитовое xor обычно представляется как ^. Это похоже на or, за исключением того, что каждый бит в результате будет равен «1», если один из операндов имеет один и тот же бит, но не оба. Отсюда и название «исключающее или».

  01010101
| 11000011
  --------
= 10010110

Последние 2 оператора — это shift операторов, у вас shift слева и shift справа. Это в основном перемещает биты влево или вправо. Есть исключения, особенно для чисел со знаком, но, вообще говоря, когда биты перемещаются за пределы длины числа, они теряются, а введенные биты устанавливаются в «0». Тем не менее, существует способ сделать «круговой» сдвиг, при котором биты, сдвинутые наружу в одном направлении, возвращаются с другой стороны. Мы увидим это позже в учебнике.

Операторы смен представлены << и >>. Второй операнд представляет количество сдвигов.

Shift 1 time to the left
   00111100
<< 00000001
   --------
=  01111000
Shift 2 times to the right
   00111100
>> 00000010
   --------
=  00001111

Теперь, когда это ясно. Давайте посмотрим на некоторые примеры из реальной жизни.

Установите и объедините флаги

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

Возьмем очень простой пример из жизни. Права доступа к файлу на компьютере обычно представлены числом с 3 флажками для вашего личного доступа к нему: право на чтение, запись и выполнение файла (в указанном порядке). Например, если у вас есть права на чтение и выполнение файла, но нет права на запись в него, флаги в виде двоичного числа будут 101, потому что включены только первый и третий флаги. В большинстве языков программирования это записывается как 0b101, что равно 5 в десятичном виде (0b указывает на двоичное число). Если вам разрешено только читать, это будет 0b100.

Типичный способ использования этого состоит в том, чтобы каждая опция была представлена ​​числом, у которого включен только один бит, и установка опций с помощью or. Вот пример псевдокода:

READ =    0b100 # 4
WRITE =   0b010 # 2
EXECUTE = 0b001 # 1

setFilePermissions( 
    "/path/to/file.txt", 
    READ | EXECUTE 
)

Подобные бинарные параметры довольно часто устанавливаются, особенно в языках низкого уровня, таких как C. Я мог бы написать число 5 или 0b101 вместо READ | EXECUTE, но цель здесь состоит в том, чтобы раз и навсегда дать имя параметрам, а затем использовать этот уровень абстракции, чтобы сделать код разборчивым.

Каждое число имеет только одну «1» и представляет только один флаг. Поэтому, когда вы используете побитовый оператор or, вы в основном комбинируете флаги. Но по большому счету принцип заключается в том, что если вы хотите «включить» определенный бит в числе, вы просто or используете число, в котором включен только этот бит. Например, если вы хотите убедиться, что третий бит числа включен, вы or используете 0b100.

Кстати, я сказал, что мы сделали код более «разборчивым». Это правда, но что-то вводит в заблуждение, и именно здесь термин «взлом» раскрывает весь свой потенциал. Хотя это более разборчиво, чем «5», оно все же выглядит как «READ or EXECUTE», где вы фактически устанавливаете оба, и заманчиво использовать вместо этого and. Поверьте мне, вы привыкнете к этому, но один из способов увидеть это как список того, что я могу делать: «Я могу читать или выполнять».

В булевой алгебре or часто представляется со знаком +, а and со знаком умножения ., что вроде как помогает, но это главным образом потому, что правила сокращения уравнения, соответственно, очень похожи.

Битовая маскировка

Как вы можете видеть на странице Википедии о битовой маскировке, большинство побитовых операторов можно рассматривать как своего рода маскировку, но я думаю, что с оператором and это более очевидно. Обычно мы используем его для фильтрации определенного бита или части битов с помощью так называемой маски. И тогда вы можете проверить, не равно ли значение нулю. Если это так, это означает, что бит включен. Давайте снова воспользуемся нашим примером прав доступа к файлам. У меня есть разрешение в виде числа, и я хочу проверить, есть ли у меня разрешение на его чтение.

READ =    0b100 # 4
WRITE =   0b010 # 2
EXECUTE = 0b001 # 1

filePermission = getPermission("/path/to/file.txt")

if (filePermission & READ) != 0:
  print "yes"
else:
  print "no"

Вот что произойдет, если разрешение файла 0b101:

  101
& 100
  ---
= 100

Вы можете видеть, что третий бит, начинающийся справа, является единственным битом в обоих числах. Поскольку он находится в первом and втором числе, этот бит устанавливается в результате. И как следствие не '0'.

А вот что произойдет, если права доступа к файлу будут 0b011:

  011
& 100
  ---
= 000

Здесь операнд не имеет общего бита, поэтому результат везде содержит «0».

Теперь вы можете видеть, как второе число действует как маска. Каждый бит, равный «0» в маске, будет равен «0» в результате. Мне нравится думать о них как о «выброшенных». Биты, установленные на «1» в маске, сохраняются точно так же, как и в первом числе. Мне нравится думать о них как о «законсервированных».

Допустим, я хотел оставить только 4 младших бита байта, я мог and с маской 0b00001111.

  10100011
& 00001111
  --------
= 00000011

Видеть? Он «отбрасывает» из исходного числа все биты, равные «0» в маске.

Компактные данные

Допустим, мы хотели сохранить числа в файл, и мы хотим, чтобы этот файл был как можно более компактным. Мы знаем, что эти числа могут быть только от 0 до 15. Вы можете представить число от 0 до 15 всего 4 битами. Поэтому, если мы хотим сделать его компактным, мы можем сохранить 2 числа в 1 байте.

Способ добиться этого состоит в том, чтобы shift одно из чисел 4 раза влево, а затем использовать or для их объединения. Поскольку оба числа меньше или равны 15, мы знаем, что любой бит выше 4-го бита обязательно не имеет значения и равен нулю. Следовательно, сдвиг одного из чисел на 4 бита влево позволяет нам объединить 2 числа без перекрытия. Все значащие биты каждого числа находятся в его собственной половине.

number1 = 0b00001010 # 10
number2 = 0b00001100 # 12
shifted1 = number1 << 4 # 0b10100000
combined = shifted1 | number2 # 0b10101100

Затем вы можете сохранить эти цифры в файл, и это займет вдвое меньше места. Чтобы прочитать их из файла . Вы можете использовать and, чтобы замаскировать соответствующую часть и сдвинуть первую в противоположном направлении.

combined = 0b10101100
number1 = (combined & 0b11110000) >> 4 # 0b00001010
number2 = combined & 0b00001111 # 0b00001100

На самом деле этот процесс похож на то, как вы печатаете байты в шестнадцатеричном формате (например, «A0»), потому что каждый символ находится точно между 0 и 15. Он разделен на 2 символа. Поэтому вы должны сначала извлечь оба шестнадцатеричных числа, а затем напечатать их символы между «0» и «F».

Круговой сдвиг

Как упоминалось ранее, существует способ сделать shift "циклическим", то есть shift, где биты, которые переполняются на одной стороне, возвращаются на другую сторону. Вот как бы вы сделали shift слева из 3:

number = 0b11110000
circLeftShifted = 
    (number << 3) | (number >> (8 - 3)) # 0b10000111

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

XOR Космический шериф

Я уверен, вы заметите, что я оставил xor в конце. Честно говоря, я изо всех сил пытался найти хороший вариант использования для xor, который не был бы ни слишком простым, ни слишком сложным. Но на самом деле для этого есть веская причина: xor на самом деле волшебник из всех. Я имею в виду, что все побитовые операторы по-своему волшебны, но xor — самый интригующий. Вероятно, поэтому в его честь назван X-OR, один из величайших космических шерифов всех времен (во французском варианте). Поэтому вместо подробных примеров сосредоточимся на его интересных свойствах.

На простом конце спектра вы обнаружите, что мы можем использовать xor так же, как мы используем or в нашем примере с правами доступа к файлам, за исключением того, что вместо установки бита в «1» он переключается. Это уже очень интересное свойство. In фактически делает то же самое, что и оператор not, за исключением того, что вы можете контролировать, какие биты инвертируются. Вы маскируете с помощью «1» биты, которые хотите инвертировать/переключить.

Еще одна особенность xor заключается в том, что если вы xor число с самим собой, оно возвращает все 0. Вот почему он используется в контрольных суммах для сравнения чисел. Он также используется с графикой, хешированием, сжатием, криптографией. Во многих случаях используется один особенно интересный аспект xor, который заключается в том, что вероятность распределения его вывода составляет 50%, чего нельзя сказать о or и and.

Давайте проверим таблицу истинности или эти операторы, чтобы визуализировать это:

a | b | a AND b
---------------
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
a | b | a OR b
--------------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
a | b | a XOR b
---------------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Как видите, выход and имеет больше шансов быть 0, а вывод or больше шансов быть 1. Только выход xor сбалансирован. Это делает его интересным для хеш-функций. Вы можете комбинировать числа, и благодаря сбалансированному выходу вы уменьшаете вероятность столкновения двух клавиш.

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

hashForPin = 4 ^ 2 ^ 9 ^ 6
hashForDad = 'd' ^ 'a' ^ 'd'

Пожалуйста, имейте в виду, что с этим связана большая проблема, поэтому не используйте его в своем коде, если не знаете последствий. Он хорошо справляется с предотвращением коллизий (вывод остается таким же для других чисел или слов), но не принимает во внимание порядок. То есть, если вы смешаете слово «папа» и слово «добавить», результат будет одинаковым для обоих. Вот почему существует множество алгоритмов хеширования, которые намного сложнее, чем просто xorобработка чисел. Но для них это строительный материал.

Очевидно, что тот факт, что порядок не имеет значения, также может быть использован. Это может быть именно то, что вы хотите.

Вывод

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