Ещё немного магии в битах

вротмненогидэвидблейн

Помимо измерения расстояния между словами вообще бывает иногда надо спуститься ещё ниже – к самым битам. Туда, где происходит настоящая магия компьютеров. Там прям, можно сказать, актуальны настоящие заклинания битовых волшебников.

Битовые операции короткие, непонятные на первый взгляд, но с мощным эффектом:

🧙‍♂ Найти самую правую единичку
x & -x
(операция побитового И между числом и отрицанием самого числа)

Например, для 01101000 результат будет 000001000. Но тут тайное знание битовых волшебников немного: надо знать как работают отрицательные числа.

🧙‍♂ Понять, является ли число степенью двойки
(x & (x-1)) == 0
(вычесть из числа единичку, взять побитовое И с самим собой, сравнить с нулём)

Это заклинание работает, потому что в степенях двойки (1, 2, 4, 8...) всегда только один бит активен, а в (x-1) этот бит сброшен, и все биты справа от него включены. Ну когда мы делаем побитовое И то вырубаем все эти биты получается, если у нас правда исходное число это степень двойки

🧙‍♂ Обнуление самой правой единички делается похожим заклинанием
x & (x-1)

Тут проще на конкретике. Для 01101000 получим 01100000 (самая правая единица исчезла)

🧙‍♂ установка всех битов справа от младшего включенного бита тоже похожим пассом, следите за руками
x | (x-1)
(побитовое ИЛИ между собой и "собой минус 1")

Для 00010000 получим 00011111

И там очень много таких прикольных пассов, на мой взгляд показывающих наглядно что весь этот Computer Science вполне себе математика, просто и понято.

А самая мощная из битовых операций – исключающее ИЛИ (XOR). Вот её помощью можно творить настоящие чудеса и побеждать драконов 🐉

XOR имеет удивительное свойство: a ^ a = 0 и a ^ 0 = a. Это значит, что любое число, XOR'нутое само на себя, даёт ноль, а XOR с нулём даёт исходное число. На этом основывается мой любимый трюк для обмена значений двух переменных (ну типа если a=5 а b=60 то сделать так чтобы стало a=60 и b=5):

a = a ^ b
b = a ^ b  // b будет =a
a = a ^ b  // a будет исходное b

Каждый раз когда это пишу немножко не верю, что это работает и всегда проверяю себя. Прям шаг за шагом:

1. a = a ^ b
   → a содержит (исходное a) XOR (исходное b)

2. b = a ^ b
   → b содержит ((исходное a) XOR (исходное b)) XOR (исходное b) = исходное a

3. a = a ^ b
   → a содержит ((исходное a) XOR (исходное b)) XOR (исходное a) = исходное b

Чистая магия! 🧚

Есть мнение что битовые операции – это ближе всего к тому, что можно назвать поэзией в программировании. Книжки с такими задачками и трюками всегда называются очень мечтательно, типа "битовые трюки: искусство программирования". Короткие, элегантные, немного загадочные. В мире, где компьютерные программы становятся всё абстрактнее и дальше от железа, эти трюки – напоминание о том, что в основе всего лежат простые биты, и с ними можно творить чудеса. Приятно, знаете ли, об этом вспоминать периодически!