Java Language
Бит-манипуляция

замечания

Упаковка / распаковка значений в виде фрагментов

Обычно производительность памяти сводит несколько значений в одно примитивное значение. Это может быть полезно для передачи различной информации в одну переменную.

Например, можно упаковать 3 байта - например, цветовой код в RGB - в один int.

Упаковка значений

// Raw bytes as input
byte[] b = {(byte)0x65, (byte)0xFF, (byte)0x31};

// Packed in big endian: x == 0x65FF31
int x = (b[0] & 0xFF) << 16  // Red
      | (b[1] & 0xFF) <<  8  // Green
      | (b[2] & 0xFF) <<  0; // Blue

// Packed in little endian: y == 0x31FF65
int y = (b[0] & 0xFF) <<  0
      | (b[1] & 0xFF) <<  8
      | (b[2] & 0xFF) << 16;

Распаковка значений

// Raw int32 as input
int x = 0x31FF65;

// Unpacked in big endian: {0x65, 0xFF, 0x31}
byte[] c = {
    (byte)(x >> 16),
    (byte)(x >>  8),
    (byte)(x & 0xFF)
};

// Unpacked in little endian: {0x31, 0xFF, 0x65}
byte[] d = {
    (byte)(x & 0xFF),
    (byte)(x >>  8),
    (byte)(x >> 16)
};

Проверка, настройка, очистка и переключение отдельных битов. Использование длинной битовой маски

Предполагая, что мы хотим изменить бит n целочисленного примитива, i (байт, короткий, char, int или long):

(i & 1 << n) != 0 // checks bit 'n'
i |= 1 << n;      // sets bit 'n' to 1
i &= ~(1 << n);   // sets bit 'n' to 0
i ^= 1 << n;      // toggles the value of bit 'n'

Использование long / int / short / byte в качестве битовой маски:

public class BitMaskExample {
    private static final long FIRST_BIT = 1L << 0;
    private static final long SECOND_BIT = 1L << 1;
    private static final long THIRD_BIT = 1L << 2;
    private static final long FOURTH_BIT = 1L << 3;
    private static final long FIFTH_BIT = 1L << 4;
    private static final long BIT_55 = 1L << 54;

    public static void main(String[] args) {
        checkBitMask(FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55);
    }

    private static void checkBitMask(long bitmask) {
        System.out.println("FIRST_BIT: " + ((bitmask & FIRST_BIT) != 0));
        System.out.println("SECOND_BIT: " + ((bitmask & SECOND_BIT) != 0));
        System.out.println("THIRD_BIT: " + ((bitmask & THIRD_BIT) != 0));
        System.out.println("FOURTh_BIT: " + ((bitmask & FOURTH_BIT) != 0));
        System.out.println("FIFTH_BIT: " + ((bitmask & FIFTH_BIT) != 0));
        System.out.println("BIT_55: " + ((bitmask & BIT_55) != 0));
    }
}

Печать

FIRST_BIT: true
SECOND_BIT: false
THIRD_BIT: true
FOURTh_BIT: false
FIFTH_BIT: true
BIT_55: true

который соответствует этой маске мы прошли в качестве checkBitMask параметра: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Выражая силу 2

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

Синтаксис в основном:

int pow2 = 1<<n;

Примеры:

int twoExp4 = 1<<4; //2^4
int twoExp5 = 1<<5; //2^5
int twoExp6 = 1<<6; //2^6
...
int twoExp31 = 1<<31; //2^31

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

int twoExp4 = 0x10; //hexadecimal
int twoExp5 = 0x20; //hexadecimal
int twoExp6 = 64; //decimal
...
int twoExp31 = -2147483648; //is that a power of 2?

Простым методом вычисления мощности int 2 будет

int pow2(int exp){
    return 1<<exp;
}

Проверка того, является ли число мощностью 2

Если целое число x равно 2, устанавливается только один бит, тогда как x-1 имеет все биты, установленные после этого. Например: 4 равно 100 и 3 равно 011 как двоичное число, которое удовлетворяет вышеупомянутому условию. Ноль не равен 2 и должен быть проверен явно.

boolean isPowerOfTwo(int x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Использование левого и правого сдвига

Предположим, у нас есть три вида разрешений: READ , WRITE и EXECUTE . Каждое разрешение может варьироваться от 0 до 7. (Предположим, что система с четырьмя битами)

RESOURCE = READ WRITE EXECUTE (12-разрядное число)

RESOURCE = 0100 0110 0101 = 4 6 5 (12-разрядное число)

Как мы можем получить разрешения (12-разрядного номера), установленные выше (12-разрядное число)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Таким образом, мы можем получить разрешения EXECUTE RESOURCE . Теперь, что, если мы хотим получить READ- разрешения RESOURCE ?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Правильно? Вероятно, вы это принимаете? Но разрешения приведены в 1024. Мы хотим получить только разрешения READ для ресурса. Не волнуйтесь, поэтому у нас были операторы смены. Если мы увидим, разрешения READ на 8 бит превысят фактический результат, поэтому, если применить некоторый оператор сдвига, который приведет к разрешению READ до самого правильного результата? Что делать, если мы это сделаем:

0100 0000 0000 >> 8 => 0000 0000 0100 (потому что это положительное число, замененное на 0, если вы не заботитесь о знаке, просто используйте беззнаковый оператор сдвига вправо)

Теперь у нас есть разрешения READ, которые равны 4.

Теперь, например, нам предоставлены разрешения READ , WRITE , EXECUTE для RESOURCE , что мы можем сделать, чтобы сделать разрешения для этого РЕСУРСА ?

Давайте сначала рассмотрим пример двоичных разрешений. (Все еще предполагая систему с 4-разрядными номерами)

READ = 0001

WRITE = 0100

EXECUTE = 0110

Если вы думаете, что мы просто сделаем это:

READ | WRITE | EXECUTE , вы несколько правы, но не совсем. Смотрите, что произойдет, если мы будем выполнять READ | НАПИСАТЬ | ВЫПОЛНИТЬ

0001 | 0100 | 0110 => 0111

Но разрешения фактически представлены (в нашем примере) как 0001 0100 0110

Итак, чтобы сделать это, мы знаем, что READ размещен на 8 бит позади, WRITE помещается на 4 бита, а PERMISSIONS помещается последним. Система номеров, используемая для разрешений RESOURCE, на самом деле составляет 12 бит (в нашем примере). Он может (будет) отличаться в разных системах.

(READ << 8) | (WRITE << 4) | (EXECUTE)

0000 0000 0001 << 8 (READ)

0001 0000 0000 (сдвиг влево на 8 бит)

0000 0000 0100 << 4 (WRITE)

0000 0100 0000 (сдвиг влево на 4 бита)

0000 0000 0001 (ВЫПОЛНИТЬ)

Теперь, если мы добавим результаты вышеперечисленного, это будет нечто подобное;

0001 0000 0000 (READ)

0000 0100 0000 (ЗАПИСЬ)

0000 0000 0001 (ВЫПОЛНИТЬ)

0001 0100 0001 (РАЗРЕШЕНИЯ)

Класс java.util.BitSet

Начиная с версии 1.7 существует класс java.util.BitSet, который обеспечивает простой и удобный интерфейс хранения и манипулирования битами:

final BitSet bitSet = new BitSet(8); // by default all bits are unset

IntStream.range(0, 8).filter(i -> i % 2 == 0).forEach(bitSet::set); // {0, 2, 4, 6}

bitSet.set(3); // {0, 2, 3, 4, 6}

bitSet.set(3, false); // {0, 2, 4, 6}

final boolean b = bitSet.get(3); // b = false

bitSet.flip(6); // {0, 2, 4}

bitSet.set(100); // {0, 2, 4, 100} - expands automatically

BitSet реализует Clonable и Serializable , а под капотом все значения бит хранятся в long[] words поле long[] words , которое автоматически расширяется.

Он также поддерживает целые логические операции and , or , xor , andNot :

bitSet.and(new BitSet(8));
bitSet.or(new BitSet(8));
bitSet.xor(new BitSet(8));
bitSet.andNot(new BitSet(8));

Подписанный беззнаковый сдвиг

В Java все примитивы числа подписаны. Например, int всегда представляет значения из [-2 ^ 31 - 1, 2 ^ 31], сохраняя первый бит для подписи значения - 1 для отрицательного значения, 0 для положительного.

Операторы основного сдвига >> и << являются операторами-операторами. Они сохранят знак ценности.

Но программисты часто используют номера для хранения значений без знака . Для int это означает смещение диапазона до [0, 2 ^ 32 - 1], чтобы иметь в два раза большее значение, чем с подписанным int.

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

                initial value:               4 (                                100)
     signed left-shift: 4 << 1               8 (                               1000)
    signed right-shift: 4 >> 1               2 (                                 10)
 unsigned right-shift: 4 >>> 1               2 (                                 10)
                initial value:              -4 (   11111111111111111111111111111100)
    signed left-shift: -4 << 1              -8 (   11111111111111111111111111111000)
   signed right-shift: -4 >> 1              -2 (   11111111111111111111111111111110)
unsigned right-shift: -4 >>> 1      2147483646 (    1111111111111111111111111111110)

Почему нет <<< ?

Это исходит из предполагаемого определения сдвига вправо. Когда он заполняет опустошенные места слева, нет никакого решения принять бит за знак. Как следствие, нет необходимости в двух разных операторах.

См. Этот вопрос для более детального ответа.