4.2. Побитовые маски и сдвиги

Побитовые операции – когда целые числа рассматриваются как наборы бит, где 0 и 1 играют роли логического нуля и логической единицы. При этом все логические операции для двух чисел осуществляются поразрядно – k-тый разряд первого числа с k-тым разрядом второго. Для простоты мы будем рассматривать четырёхбитовые ячейки, хотя реально самая малая по размеру ячейка восьмибитовая и соответствует типу byte.

а) установка в числе a нужных бит в 1 с помощью маски m операцией a|m (арифметический, или, что то же, побитовый оператор OR).

Пусть число a = a₃*2³ + a₂*2² + a₁*2¹ + a₀*2⁰ , где значения a_i – содержание соответствующих бит числа (то есть либо нули , либо единицы).

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

б) установка в числе a нужных бит в 0 с помощью маски m операцией a&m (арифметический, или, что то же, побитовый оператор AND):

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

в) инверсия (замена единиц на нули, а нулей на единицы) в битах числа a , стоящих на задаваемых маской m местах, операцией a^m (арифметический, или, что то же, побитовый оператор XOR):

Видно, что если в бите, где маска m имеет единицу, у числа a происходит инверсия: если стоит 1, в результате будет 0, а если 0 – в результате будет 1. В остальных битах значение не меняется.

Восстановление первоначального значения после операции XOR – повторное XOR с той же битовой маской:

Видно, что содержание ячейки приняло то же значение, что было первоначально в ячейке a. Очевидно, что всегда (a ^ m) ^ m = a, так как повторная инверсия возвращает первоначальные значения в битах числа. Операция XOR часто используется в программировании для инверсии цветов частей экрана с сохранением в памяти только информации о маске. Повторное XOR с той же маской восстанавливает первоначальное изображение. - Имеется команда перевода вывода графики в режим XOR при рисовании, для этого используется команда graphics.setXORMode(цвет).

Ещё одна область, где часто используется эта операция – криптография.

Инверсия всех битов числа осуществляется с помощью побитового отрицания ~a.

Побитовые сдвиги “<<”, “>>” и “>>>” приводят к перемещению всех бит ячейки, к которой применяется оператор, на указанное число бит влево или вправо. Сначала рассмотрим действие операторов на положительные целые числа.

Побитовый сдвиг на n бит влево m<<n эквивалентен быстрому целочисленному умножению числа m на 2ⁿ. Младшие биты (находящиеся справа), освобождающиеся после сдвигов, заполняются нулями. Следует учитывать, что старшие биты (находящиеся слева), выходящие за пределы ячейки, теряются, как и при обычном целочисленном переполнении.

Побитовые сдвиги на n бит вправо m>>n или m>>>n эквивалентны быстрому целочисленному делению числа m на 2ⁿ. При этом для положительных m разницы между операторами “>>” и “>>>” нет.

Рассмотрим теперь операции побитовых сдвигов для отрицательных чисел m. Поскольку они хранятся в дополнительном коде, их действие нетривиально. Как и раньше, для простоты будем считать, что ячейки четырёхбитовые, хотя на деле побитовые операции проводятся только для ячеек типа int или long, то есть для 32-битных или 64-битных чисел.

Пусть m равно -1. В этом случае m=1111₂. Оператор m<<1 даст m=11110₂, но из-за четырёхбитности ячейки старший бит теряется, и мы получаем m=1110₂=-2. То есть также получается полная эквивалентность умножению m на 2ⁿ.

Иная ситуация возникает при побитовых сдвигах вправо. Оператор правого сдвига “>>” для положительных чисел заполняет освободившиеся биты нулями, а для отрицательных – единицами. Легко заметить, что этот оператор эквивалентен быстрому целочисленному делению числа m на 2ⁿ как для положительных, так и для отрицательных чисел. Оператор m>>>n, заполняющий нулями освободившиеся после сдвигов биты, переводит отрицательные числа в положительные. Поэтому он не может быть эквивалентен быстрому делению числа на 2ⁿ. Но иногда такой оператор бывает нужен для манипуляции с наборами бит, хранящихся в числовой ячейке. Само значение числа в этом случае значения не имеет, а ячейка используется как буфер соответствующего размера.

Например, можно преобразовать последовательность бит, образующее некое целое значение, в число типа float методом Float.intBitsToFloat(целое значение) или типа double методом Double.intBitsToDouble (целое значение). Так, Float.intBitsToFloat(0x7F7FFFFF) даст максимальное значение типа float.