1. Обзор
Иногда нам нужно проверить, установлена ли двоичная цифра в числе или нет. Это может быть связано с тем, что мы используем числа как набор флагов, где каждая цифра представляет определенное логическое значение.
В этом руководстве мы рассмотрим различные способы получения бита в определенной позиции из целочисленных значений, таких как byte , short , char , int и long .
2. Тестирование определенного бита
Одной из наиболее распространенных ситуаций является то, что мы хотим проверить определенный бит целочисленного значения с помощью битовой маски .
Например, давайте проверим, установлен ли третий бит в значении байта :
byte val1 = 0b0110_0100;
byte mask = 0b0000_0100;
boolean isSet1 = (val1 & mask) > 0;
assertTrue(isSet1);
Здесь двоичное число 01100100 проверяется, установлен ли третий бит — 00000100 с помощью побитового И. Результат больше нуля, так и есть. Мы также можем проверить, если он не установлен:
byte val2 = 0b0110_0010;
boolean isSet2 = (val2 & mask) > 0;
assertFalse(isSet2);
Этот пример основан на числовом типе byte , и мы можем легко расширить его до значений short , char , int и long .
В этом решении мы жестко запрограммировали битовую маску. Что, если бы мы захотели обобщить решение для проверки любого бита в нашем числе?
3. Использование оператора сдвига
Прежде чем начать, давайте сначала определим диапазон индексов битовых позиций в 32-битном int . Самый левый бит имеет индекс 31, а самый правый бит имеет индекс 0. Это потому, что наши числа идут от самых значащих до самых младших цифр. Например, если бы мы использовали длинные 64-битные числа, крайний левый бит был бы равен 63.
3.1. Сдвиг маски влево
Мы можем сгенерировать битовую маску, взяв значение 1 и переместив его в правильное положение с помощью оператора сдвига влево:
int val = 0b0110_0100;
int pos = 2;
int mask = 1 << pos;
boolean isSet = (val & mask) > 0;
assertTrue(isSet);
Здесь мы установили pos равным 2 , хотя это может быть любая допустимая битовая позиция в нашем числе. Затем мы используем оператор сдвига влево ( << ) для создания нашей битовой маски. Наконец, мы выполняем побитовую операцию AND ( & ) между val и mask .
Если результат больше нуля, это означает, что установлен целевой бит.
3.2. Сдвиг значения влево
Кроме того, есть еще один способ решения этой проблемы.
Вместо создания битовой маски мы можем использовать оператор сдвига влево для тестируемого значения. Вместо того, чтобы фильтровать значение с помощью битовой маски, мы можем сдвинуть его содержимое так, чтобы интересующий бит находился в крайнем левом положении.
Затем все, что нам нужно сделать, это проверить, установлен ли крайний левый бит. Поскольку целое число со знаком представлено как дополнение до двух , мы можем проверить, является ли первая цифра единицей, проверив, является ли результирующее число со сдвинутым битом отрицательным.
int val = 0b0110_0100;
int pos = 2;
boolean isSet = ((val << (31 - pos)) < 0);
assertTrue(isSet);
В приведенном выше примере pos равен 2, а крайняя левая позиция — 31, поэтому мы используем 31 для вычитания pos , что равно 29. Затем мы сдвигаем влево исходное значение на 29-битные позиции и получаем новое значение. В этом новом значении интересующий бит находится в крайнем левом положении. Наконец, мы проверяем, меньше ли новое значение нуля или нет.
3.3. Сдвиг значения вправо
Точно так же мы можем использовать оператор сдвига вправо для проверки части целочисленного значения. После перемещения целевого бита целочисленного значения в крайнее правое положение и использования битовой маски 1 мы можем проверить, равен ли результат единице:
int val = 0b0110_0100;
int pos = 2;
boolean isSet = ((val >> pos) & 1) == 1;
assertTrue(isSet);
4. Оптимизация побитового решения
В тех случаях, когда мы можем выполнять эти вычисления много, мы можем оптимизировать наше решение, чтобы использовать наименьшее количество инструкций ЦП.
Давайте посмотрим на переписывание решения для сдвига влево, которое может помочь нам в этом. Он основан на предположении, что побитовые операции обычно выполняются быстрее, чем арифметические:
boolean isSet = ((val << (~pos & 31)) < 0);
Отметим, что основная идея не изменилась. Просто написание кода немного отличается: мы используем (~pos & 31) для замены предыдущего (31-pos) выражения.
Почему эти два выражения имеют одинаковый эффект? Мы можем вычесть этот процесс:
(31 - pos) = (31 - pos) & 31
= (31 + (-pos)) & 31
= (31 & 31) + ((-pos) & 31)
= (31 & 31) + ((~pos + 1) & 31)
= (31 & 31) + (~pos & 31) + (1 & 31)
= ((31 + 1) & 31) + (~pos & 31)
= (32 & 31) + (~pos & 31)
= 0 + (~pos & 31)
= (~pos & 31)
В начале этого раздела мы упомянули, что крайняя левая позиция — 31, а крайняя правая позиция — 0, поэтому (31 — pos) должно быть положительным числом или нулем. Если мы выполним побитовую операцию И ( & ) между (31 — pos) и 31, результат останется прежним. Затем мы делаем это шаг за шагом. Наконец, мы получаем выражение (~pos & 31) .
В этом процессе нужно объяснить еще один момент: как (-pos) превращается в (~pos + 1) ? Чтобы получить отрицательную нотацию целого числа в дополнении до двух , мы можем выполнить побитовую операцию ДОПОЛНЕНИЕ ( ~ ), а затем добавить единицу к результату.
Еще один шаг вперед, мы можем сделать код немного более кратким:
boolean isSet = ((val << ~pos) < 0);
В приведенном выше примере мы пропустили побитовое И ( & ) и 31. Это потому, что JVM сделает всю работу за нас. Значение int имеет 32 бита, и JVM гарантирует, что его допустимый диапазон сдвига должен быть от 0 до 31. Точно так же длинное значение имеет 64-бит, и JVM также гарантирует, что его допустимый диапазон сдвига должен быть от 0 до 63 . .
5. Использование BigInteger
Хотя приведенная выше двоичная математика является наиболее эффективной с вычислительной точки зрения для встроенных числовых типов, нам может потребоваться проверка битов в числах с более чем 64 битами или может потребоваться более легкий для чтения код.
Класс BigInteger может решить обе эти проблемы. Он поддерживает очень большие числа с огромным количеством битов, а также предоставляет метод testBit :
int val = 0b0110_0100;
int pos = 2;
boolean isSet = BigInteger.valueOf(val).testBit(pos);
assertTrue(isSet);
6. Заключение
В этом уроке мы рассмотрели некоторые распространенные подходы к получению бита в определенной позиции из целочисленных значений.
Как обычно, исходный код этого руководства можно найти на GitHub .