6.3. Битовые операции

Всем известны логические операции and, or, xor, not. Они из двух boolean-значений делают одно: \(true \text{ or } false = true\) и т.п.. Существуют аналогичные операции для чисел, которые выполняют соответствующие действия побитово. В паскале эти действия записываются теми же операторами, что и логические. Таким образом, например, \(3 \text{ or } 5= 7\), так как \(3=\dots00011_2\), а \(5=\dots00101_2\), поэтому, если про-or-ить побитово (т.е. столбиком, т.е. младший бит с младшим и т.д.), то получится \(\dots00111_2=7\). Аналогично \(3 \text{ and } 5 = 1\) и \(3 \text{ xor } 5 = 6\) (xor — исключающее ИЛИ, т.е. равно 1, только если ровно один бит из двух равен единице, или, что то же самое, если два бита различны).

С побитовым not немного хитрее: т.к. каждый бит инвертируется, то результат зависит от того, сколько всего бит было в числе, т.е. от типа, в котором вы проводите вычисления. Например, в byte будет, видимо, \(\text{not } 5= 250\).

Задача 6.5:

Поэкспериментируйте с операцией not в других типах. В частности, верно ли, что в знаковых типах (shortint, integer, longint) not может давать отрицательные значения? Должен бы.

Кроме этих операций, есть ещё две довольно полезных: shr и shl. Операция shr (shift-right) осуществляет сдвиг битовой записи «вправо» [1] на указанное количество бит, при этом младшие биты отбрасываются (т.е. операция эквивалентна делению на степень двойки): \(2=4 \text{ shr } 1=8 \text{ shr } 2=16\text{ shr } 3=32\text{ shr } 4\) (т.е. \(32 \text{ shr } 4\) — это 32 сдвинуть на 4 бита вправо). Кроме того, \(2=5\text{ shr } 1=11\text{ shr } 2=18\text{ shr } 3=40\text{ shr } 4\), и \(5\text{ shr } 4=0\), т.к. младшие биты отбрасываются. Операция shl сдвигает битовую запись влево, дополняя младшие разряды нулями (т.е. эквивалентно умножению на степень двойки). Старшие разряды, вылезающие за тип, видимо, отбрасываются. Результат, конечно же, зависит от типа. Пример: в любом типе \(2\text{ shl } 1=4\), \(5\text{ shl } 4=80\); если влезет в тип, то \(1\text{ shl } k=2^k\).

Задача 6.6:

Поэкспериментируйте с операцией shl в других типах. В частности, верно ли, что в знаковых типах (shortint, integer, longint) shl может давать отрицательные значения? Вроде действительно может давать.

Примечание

В частности, например, возведение двойки в степень писать как \(1\text{ shl } k\) намного проще, чем циклом, и работать будет быстрее. (Только ВНИМАНИЕ: стандартная ошибка — написать тут 2 вместо 1: например для деления на 2 написать shr 2 по аналогии с div 2 :) вместо верного shr 1, аналогично можно случайно написать \(2\text{ shl } k\) для возведения 2 в степень \(k\). Это, конечно, приведёт к неправильному результату.)

Битовые операции вы применяете, обычно, тогда, когда вам действительно надо что-то сделать, связанное с битами. Например, число из \(k\) единиц (\(11\dots1_2\)) можно получить как \(1\text{ shl } k-1\). Входит ли \(k\)-я степень двойки в двоичное представление числа \(n\) можно проверить так: \((n \text{ shr } k) \text{ and } 1=1\) или — второй способ — \(n \text{ and } (1 \text{ shl } k)<>0\). В частности, проверить, чётно или нечётно число можно, посмотрев, чему равно \(n \text{ and } 1\), и т.п.

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

Задача 6.7:

Как быстро с помощью битовых операций вычислить максимальную степень двойки, на которую делится данное число? Ответ должен быть просто арифметическим выражением, без всяких циклов и т.п. и, например, для числа 40 давать ответ 8.

Ещё частое употребление — если вы числом \(n\) кодируете последовательность нулей и единиц (закрашенных и незакрашенных клеток, используемых и не используемых объектов и т.п.), и вам надо что-то с ней сделать (определить, закрашена ли та или иная клетка), то почти всегда подобные действия можно перевести на язык битовых операций.

Кроме того, раньше битовые операции использовались для ускорения программы: делить на 2 через shr 1 было намного быстрее, чем через div 2. Но современные компиляторы это умеют прекрасно оптимизировать (т.е. видя в программе деление на 2, сами заменяют его на shr), поэтому сейчас нет особого смысла это делать.

[1]Кавычки потому, что не очень-то ясно, где здесь право, а где лево :). Младший разряд — это правый или левый?