Побитовые операторы и битовые манипуляции для интервью

Этот урок изначально был опубликован на https://algodaily.com, где я веду курс технических собеседований и пишу аналитические статьи для амбициозных разработчиков.

Десятичный и двоичный

Как мы обычно представляем числа? Мы используем десятичную систему счисления (также известную как Base 10), которая обеспечивает десять уникальных цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Чтобы сформировать числа, мы комбинируем эти цифры в определенной последовательности, так что каждая десятичная цифра представляет собой значение, умноженное на определенную степень 10.

Например, в десятичном формате 152 = 100 + 50 + 2 = 1 × 10 2+ 5 × 10 1+ 2 × 10 0.

Десятичные числа больше всего нравятся людям. Компьютерам больше всего нравятся двоичные числа (также известные как Основание 2), в которых доступны только 2 цифры: 0 и 1. Таким образом, двоичное число представляет собой последовательность единиц и нулей, например 011101001, 1100110 или 110. В двоичном числе каждая цифра обозначается как бит, а каждый бит представляет степень десятичного числа 2.

Для людей чтение (и понимание) двоичных чисел включает преобразование их в десятичную форму. Преобразуем двоичное число 110 в десятичную запись. Мы знаем, что три цифры в числе представляют степени десятичной двойки. Чтобы перейти от меньших степеней двойки к более высоким, мы прочитаем двоичные цифры в нашем числе справа налево:

(Основание 2) 110 = (Основание 10) 0×20 + 1×21 + 1 ×22 = 0 + 2 + 4 = 6

Давайте попробуем преобразовать большее двоичное число: 10011000. Помните, мы читаем двоичные цифры справа налево.

(Основание 2) 10011011 = (Основание 10) 1×20 + 1×21 + 0 ×22 + 1×23 + 1×24 + 0×25 + 0×26 + 1×27 = 1 + 2 + 0 + 8 + 16 + 0 + 0 + 128 = 155.

Так что же такого особенного в двоичных числах?

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

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

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

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

Введите побитовые операторы

Побитовый оператор принимает одно или несколько значений, обрабатывает их как последовательности битов и выполняет операции с этими битами, а не с «человекочитаемыми» значениями.

Побитовые операторы доступны в большинстве языков программирования. Для наших целей давайте рассмотрим, как они реализованы в JavaScript.

Побитовые логические операторы в JavaScript

Всего JavaScript поддерживает 7 побитовых операторов:

4 побитовых логических оператора: & (побитовое И), | (побитовое ИЛИ), ^ (побитовое исключающее ИЛИ) и ~ (побитовое НЕ).
3 оператора побитового сдвига: << (сдвиг влево), >> (сдвиг вправо с распространением знака) и >>> (сдвиг вправо с нулевым заполнением).

Побитовые операторы JavaScript обрабатывают свои операнды как двоичные числа — последовательности из 32 битов — но возвращают десятичные числа.

Вот алгоритм, которому следуют побитовые логические операторы JavaScript:

Операнды преобразуются в 32-битные целые числа.
Если есть два операнда, отдельные биты из операндов сопоставляются в пары: первый бит первого операнда с первым битом второго операнда, второй бит со вторым битом и так далее.
Оператор применяется к каждой битовой паре, что дает двоичный результат.
Двоичный результат преобразуется обратно в десятичную форму.

Возможные операнды и возвращаемые значения побитовых операций часто иллюстрируются так называемыми таблицами истинности. Вот таблица истинности для всех 4 побитовых логических операторов, доступных в JavaScript:

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

0000000000000000000000000001001 представляет все 32 бита числа. Эта форма слишком длинная для большинства случаев, но мы будем использовать ее, когда будем говорить о двоичных сдвигах.
1001 — это краткая форма того же числа. Здесь мы включаем биты от первого бита, установленного в 1, до самого правого бита. Мы будем использовать эту форму в большинстве примеров.
0b1001 — это формат для выражения двоичных чисел в исходном коде JavaScript. Кроме префикса 0b в этом нет ничего необычного. Мы будем использовать эту форму в некоторых примерах кода.

& (побитовое И)

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

Для каждой пары битов побитовое И возвращает 1, только если оба бита равны 1. Во всех остальных случаях возвращается 0.

Давайте посмотрим, что здесь происходит. Предположим, мы хотим применить побитовое И к двум числам, 13 и 11:

› а и б

Что происходит, когда эта строка выполняется?

Во-первых, два значения преобразуются из десятичной формы в двоичную: 13, представленное в двоичной системе, равно 1101, а 11 становится 1011.
Затем каждый бит первого числа сопоставляется с соответствующим битом второго числа:

3. Теперь к каждой битовой паре применяется знакомое логическое И:

1101 & 1011 == 1001

4. После вычисления результата 1001 JavaScript преобразует его обратно в десятичное значение 9 и возвращает:

> 13 & 11 9

| (Побитовое ИЛИ)

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

С побитовым ИЛИ a | b возвращает 1, если a или b равно 1. Опять же, думайте об этом как о применении старого доброго логического ИЛИ (||) к набору битовых пар.

Например, если мы применяем побитовое ИЛИ к одним и тем же двум числам — 13 | 11 — числа сначала преобразуются в двоичную форму, в результате чего получаются 1101 и 1011 соответственно, а затем для каждой пары результирующее 1 возвращается каждый раз, когда хотя бы один раз бит в паре содержит 1:

Результат 1111 преобразуется в десятичную форму, и возвращается десятичное число 15:

> 13 | 11
15

^ (побитовое исключающее ИЛИ)

Для любой заданной пары битов побитовое исключающее ИЛИ (также известное как побитовое исключающее ИЛИ) возвращает 1 только в том случае, если два бита в паре различны. Во всем остальном он работает точно так же, как побитовое И и побитовое ИЛИ:

~ (побитовое НЕ)

Побитовое НЕ немного отличается, так как применяется к одному операнду, а не к двум. То, что он делает, тривиально: после преобразования операнда в двоичный код он просто инвертирует его биты.

Однако есть одна особенность. Как мы уже говорили, перед применением побитовых операторов JavaScript преобразует операнд в 32-битную последовательность. Крайний левый бит в этой последовательности используется для хранения знака числа: 0 в крайнем левом бите означает положительный результат, а 1 означает отрицательный.

Поскольку побитовое НЕ инвертирует все 32 бита своего операнда, оно также инвертирует его знак: отрицательный становится положительным, и наоборот.

Например, вот вся 32-битная последовательность, представляющая десятичное число 9:

00000000000000000000000000001001

Вызов побитового НЕ (~9) изменяет все биты, что приводит к:

11111111111111111111111111110110

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

А пока вы хотите знать, что десятичное представление результирующего числа — -10. На самом деле, применение побитового НЕ к любому числу x возвращает -(x + 1). Например, ~9 возвращает -10, ~-8 возвращает 7 и так далее.

Операторы побитового сдвига в JavaScript

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

Сдвиг влево (`<<`) сдвигает биты первого операнда влево. Значение второго операнда определяет, на сколько позиций сдвигаются биты. Биты, смещенные влево, отбрасываются. Позиции, которые освобождаются справа, заполняются нулевыми битами.

Давайте рассмотрим пример: что именно делает `7<<2` в JavaScript?

Первый (левый) операнд преобразуется в двоичную форму: `7` в двоичном виде равно `111`. На самом деле все двоичное число состоит из 32 бит, но все остальные биты слева — нули:

`0000000000000000000000000000111`

2. Поскольку второй операнд равен 2, два крайних левых бита теперь удаляются, оставляя нам 30 бит:

`-0000000000000000000000000000111 +00000000000000000000000000111`

3. Чтобы заполнить освободившиеся 2 бита, в две крайние правые позиции вставляются нули:

`-00000000000000000000000000111 +0000000000000000000000000011100`

4. Результат `11100` преобразуется в десятичное число `28` и возвращается.

Как правило, применение сдвига влево к `x` на `y` бит возвращает `x`, умноженное на `y`-ю степень числа 2:

В нашем примере выше это правило переводится как:

›› (перенос знака вправо)

Сдвиг вправо с распространением знака (>>) сдвигает биты первого операнда вправо на количество позиций, определяемое вторым операндом. Биты, сдвинутые вправо, отбрасываются. Позиции битов, которые освобождаются слева, заполняются копиями бита, который ранее был крайним слева.

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

-0000000000000000000000011110010
+0000000000000000000000000011110

››› (сдвиг вправо с нулевым заполнением)

Подобно предыдущему оператору, сдвиг вправо с заполнением нулями (>>>) сдвигает биты первого операнда вправо на количество позиций, определяемое вторым операндом. Однако свободные битовые позиции слева заполняются нулями. Это имеет два последствия:

Результат всегда будет положительным, потому что ноль в крайнем левом бите означает положительное число.
Для положительных чисел оба оператора сдвига вправо, >> и >>>, всегда возвращают один и тот же результат.

Для (несколько дикого) примера -9 >>> 2 возвращает... 1073741821:

-11111111111111111111111111110111
+00111111111111111111111111111101

Впрочем, хватит теории, давайте поговорим о практике.

Является ли прямая манипуляция битами обычной отраслевой практикой?

Сегодня вы не увидите, чтобы побитовые операции использовались очень часто. Это потому что:

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

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

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

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

Побитовые операторы в вопросах интервью

Как бы мало их ни было в производственном коде, побитовые операторы часто всплывают в вопросах на собеседованиях с разработчиками. Ниже приведена краткая подборка вопросов для интервью, в которых ожидаемое решение связано с использованием побитовых операторов.

Поменять местами два числа без использования промежуточной переменной

Одна из распространенных задач, которые могут быть поставлены перед вами на собеседовании, заключается в следующем: имея две переменные, поменять местами их значения, не вводя третью переменную.

Эту задачу можно быстро решить с помощью 3 операций побитового ИЛИ, используя алгоритм замены XOR. Вот последовательность этих операций:

x = x ^ y;
y = x ^ y;
x = x ^ y;

Попробуем поменять местами 2 и 5:

let x = 2 // 0010
let y = 5 // 0101

x = x ^ y; // x is now 7 (0111), y is still 5 (0101)
y = x ^ y; // x is still 7 (0111), y is now 2 (0010), 
x = x ^ y; // x becomes 5 (0101), y becomes 2 (0010)

Проверьте, является ли целое число четным или нечетным, не используя деление

Это территория побитового И: для заданного целого числа x выражение x & 1 вернет 1, если целое число нечетное, и 0, если оно четное. Это связано с тем, что у всех нечетных чисел самый правый бит равен 1, а 1 & 1 = 1. Вот как вы проверяете 5 на странность:

> 0b0101 & 0b0001 // same as 5 & 1
1

Ради удобочитаемости вы можете даже создать красивую оболочку для этой простой операции:

const isNumberOdd = number => {
    return Boolean(number & 1);
}

Проверить, является ли положительное целое число степенью двойки без ветвления

В двоичном представлении любой степени (десятичной) 2 одному биту присваивается значение 1, а всем следующим битам присваивается значение 0:

Binary 10 = Decimal 2 Binary 100 = Decimal 4 Binary 1000 = Decimal 8 Binary 10000000000 = Decimal 1024

Когда мы вычитаем 1 из любого такого числа, мы получаем число, в котором единицы и нули перевернуты. Например, сравните двоичные представления десятичных чисел 8 и 7:

Binary 1000 = Decimal 8
Binary 0111 = Decimal 7

Если мы теперь применим побитовое И к этим двум числам, результат будет равен нулю. Этот результирующий нуль гарантирует, что мы имеем дело со степенью двойки.

(Обратите внимание, что вам не нужно заключать number - 1 в круглые скобки, потому что вычитание имеет более высокий приоритет, чем побитовое И.)

const isPowerOfTwo = number => {
    return (number & number - 1) == 0;
}

Где узнать больше

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