Рубрики
Без рубрики

Руководство по битовому набору на Java

Узнайте, как мы можем использовать набор битов Java для представления вектора битов, познакомьтесь с внутренними элементами набора битов и более подробно изучите его API

Автор оригинала: Ali Dehghani.

1. Обзор

В этом уроке мы увидим, как мы можем использовать BitSet s для представления вектора битов.

Во-первых, мы начнем с обоснования отказа от использования boolean[] . Затем, после ознакомления с BitSet internals, мы более подробно рассмотрим его API.

2. Массив битов

Для хранения и манипулирования массивами битов можно утверждать, что мы должны использовать boolean[] в качестве структуры данных. На первый взгляд это может показаться разумным предложением.

Однако каждый член boolean в boolean[] обычно потребляет один байт вместо одного бита . Поэтому, когда у нас жесткие требования к памяти или мы просто стремимся к сокращению объема памяти, boolean[] далеки от идеала.

Чтобы сделать вопрос более конкретным, давайте посмотрим, сколько места занимает boolean[] с 1024 элементами:

boolean[] bits = new boolean[1024];
System.out.println(ClassLayout.parseInstance(bits).toPrintable());

В идеале мы ожидаем 1024-битный объем памяти от этого массива. Однако Макет объекта Java (JOL) показывает совершенно иную реальность:

[Z object internals:
 OFFSET  SIZE      TYPE DESCRIPTION            VALUE
      0     4           (object header)        01 00 00 00 (00000001 00000000 00000000 00000000) (1)
      4     4           (object header)        00 00 00 00 (00000000 00000000 00000000 00000000) (0)
      8     4           (object header)        7b 12 07 00 (01111011 00010010 00000111 00000000) (463483)
     12     4           (object header)        00 04 00 00 (00000000 00000100 00000000 00000000) (1024)
     16  1024   boolean [Z.                    N/A
Instance size: 1040 bytes

Если мы проигнорируем накладные расходы заголовка объекта, элементы массива потребляют 1024 байта вместо ожидаемых 1024 бит. Это на 700% больше памяти, чем мы ожидали.

Проблемы адресуемости и разрыв слов являются основными причинами, по которым boolean s-это больше, чем просто один бит.

Для решения этой проблемы мы можем использовать комбинацию числовых типов данных (например, long ) и побитовых операций. Вот тут-то и появляется набор битов /.

3. Как работает битовый набор

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

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

начальные-байты

Теперь, если мы хотим установить бит в позиции три в true , мы должны сначала сдвинуть число 1 влево на три:

сдвиг влево

А затем или его результат с текущим байтом значением :

финал-или

Тот же процесс произойдет, если вы решите установить бит в индексе семь:

еще один-набор

Как показано выше, мы выполняем сдвиг влево на семь битов и объединяем результат с предыдущим значением byte с помощью оператора или .

3.1. Получение битового индекса

Чтобы проверить, установлен ли конкретный битовый индекс в true или нет, мы будем использовать оператор и //. Например, вот как мы проверяем, установлен ли индекс три:

  1. Выполнение сдвига влево на три бита по значению один
  2. И в результат с текущим байтом значением
  3. Если результат больше нуля, то мы нашли совпадение, и этот битовый индекс фактически установлен. В противном случае запрашиваемый индекс является чистым или равен false
get-set

На приведенной выше диаграмме показаны шаги операции get для третьего индекса. Однако, если мы спросим о четком индексе, результат будет другим:

получить-очистить

Поскольку результат end равен нулю, индекс четыре ясен.

3.2. Выращивание хранилища

В настоящее время мы можем хранить только вектор из 8 бит. Чтобы выйти за пределы этого ограничения, нам просто нужно использовать массив байт s, а не один байт , вот и все!

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

массив-набор

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

Кроме того, если мы хотим установить здесь индекс выше 15, то BitSet сначала расширит свой внутренний массив. Только после расширения массива и копирования элементов он установит запрошенный бит. Это несколько похоже на то, как ArrayList работает внутренне.

До сих пор мы использовали тип данных byte для простоты. Битовый набор API, однако, использует массив long значений внутри .

4. API набора бит

Теперь, когда мы достаточно знаем о теории, пришло время посмотреть, как выглядит API BitSet .

Для начала давайте сравним объем памяти экземпляра BitSet с 1024 битами с boolean [] , который мы видели ранее:

BitSet bitSet = new BitSet(1024);

System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

Это приведет к печати как мелкого размера экземпляра BitSet , так и размера его внутреннего массива:

[email protected] object externals:
          ADDRESS       SIZE TYPE             PATH         VALUE
        70f97d208         24 java.util.BitSet              (object)
        70f97d220        144 [J               .words       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Как показано выше, он использует long[] с 16 элементами (16 * 64 бита) внутри. В любом случае, этот экземпляр использует в общей сложности 168 байт, в то время как boolean[] использовал 1024 байта .

Чем больше у нас битов, тем больше увеличивается разница в следах. Например, для хранения 1024 * 1024 бит boolean[] потребляет 1 МБ, а экземпляр BitSet потребляет около 130 КБ.

4.1. Построение битовых наборов

Самый простой способ создать экземпляр BitSet -использовать конструктор no-arg :

BitSet bitSet = new BitSet();

Это создаст экземпляр BitSet с long[] размером один . Конечно, при необходимости он может автоматически увеличить этот массив.

Также можно создать набор битов с начальным количеством битов :

BitSet bitSet = new BitSet(100_000);

Здесь во внутреннем массиве будет достаточно элементов, чтобы вместить 100 000 бит. Этот конструктор пригодится, когда у нас уже есть разумная оценка количества битов для хранения. В таких случаях использования он может предотвратить или уменьшить ненужное копирование элементов массива при его увеличении|/.

Можно даже создать BitSet из существующего long[] , byte[] , Long Buffer и ByteBuffer . Например, здесь мы создаем экземпляр BitSet из заданного long[] :

BitSet bitSet = BitSet.valueOf(new long[] { 42, 12 });

Существует еще три перегруженных версии метода value Of() static factory для поддержки других упомянутых типов.

4.2. Установка битов

Мы можем установить значение определенного индекса в true с помощью метода set(index) |/:

BitSet bitSet = new BitSet();

bitSet.set(10);
assertThat(bitSet.get(10)).isTrue();

Как обычно, индексы основаны на нуле. Можно даже установить диапазон битов в true с помощью set(fromInclusive, toExclusive) |/метод :

bitSet.set(20, 30);
for (int i = 20; i <= 29; i++) {
    assertThat(bitSet.get(i)).isTrue();
}
assertThat(bitSet.get(30)).isFalse();

Как видно из подписи метода, начальный индекс является включающим, а конечный-исключающим.

Когда мы говорим “установка индекса”, мы обычно имеем в виду установку его в true . Несмотря на эту терминологию, мы можем установить определенный битовый индекс в false с помощью метода set(index, boolean) :

bitSet.set(10, false);
assertThat(bitSet.get(10)).isFalse();

Эта версия также поддерживает настройку диапазона значений:

bitSet.set(20, 30, false);
for (int i = 20; i <= 29; i++) {
    assertThat(bitSet.get(i)).isFalse();
}

4.3. Очистка битов

Вместо того , чтобы устанавливать определенный битовый индекс в false , мы можем просто очистить его с помощью метода clear(index) |/:

bitSet.set(42);
assertThat(bitSet.get(42)).isTrue();
        
bitSet.clear(42);
assertThat(bitSet.get(42)).isFalse();

Кроме того, мы также можем очистить диапазон битов с помощью clear(от Inclusive до Exclusive) перегруженной версии:

bitSet.set(10, 20);
for (int i = 10; i < 20; i++) {
    assertThat(bitSet.get(i)).isTrue();
}

bitSet.clear(10, 20);
for (int i = 10; i < 20; i++) {
    assertThat(bitSet.get(i)).isFalse();
}

Интересно, что если мы вызовем этот метод без передачи каких-либо аргументов, он очистит все заданные биты :

bitSet.set(10, 20);
bitSet.clear();
for (int i = 0; i < 100; i++) { 
    assertThat(bitSet.get(i)).isFalse();
}

Как показано выше, после вызова метода clear() все биты равны нулю.

4.4. Получение битов

До сих пор мы довольно широко использовали метод get(index) . Когда задан запрошенный битовый индекс, этот метод вернет true . В противном случае он вернет false :

bitSet.set(42);

assertThat(bitSet.get(42)).isTrue();
assertThat(bitSet.get(43)).isFalse();

Аналогично set и clear , мы можем получить диапазон битовых индексов с помощью метода get(fromInclusive, toExclusive) :

bitSet.set(10, 20);
BitSet newBitSet = bitSet.get(10, 20);
for (int i = 0; i < 10; i++) {
    assertThat(newBitSet.get(i)).isTrue();
}

Как показано выше, этот метод возвращает другой Набор битов в диапазоне [20, 30) текущего. То есть индекс 20 переменной BitSet эквивалентен нулевому индексу переменной new BitSet .

4.5. Переворачивание битов

Чтобы отрицать текущее значение битового индекса, мы можем использовать метод flip(index) |///. То есть он превратит true значения в false и наоборот:

bitSet.set(42);
bitSet.flip(42);
assertThat(bitSet.get(42)).isFalse();

bitSet.flip(12);
assertThat(bitSet.get(12)).isTrue();

Аналогично, мы можем достичь того же самого для диапазона значений, используя метод flip(fromInclusive, toExclusive) :

bitSet.flip(30, 40);
for (int i = 30; i < 40; i++) {
    assertThat(bitSet.get(i)).isTrue();
}

4.6. Длина

Существует три метода, подобных длине, для набора битов . Метод size() возвращает количество битов, которые может представлять внутренний массив . Например, поскольку конструктор no-arg выделяет массив long[] с одним элементом, то size() вернет для него 64:

BitSet defaultBitSet = new BitSet();
assertThat(defaultBitSet.size()).isEqualTo(64);

С одним 64-битным числом мы можем представлять только 64 бита. Конечно, это изменится, если мы передадим количество битов явно:

BitSet bitSet = new BitSet(1024);
assertThat(bitSet.size()).isEqualTo(1024);

Кроме того, метод cardinality() представляет количество битов набора в наборе битов :

assertThat(bitSet.cardinality()).isEqualTo(0);
bitSet.set(10, 30);
assertThat(bitSet.cardinality()).isEqualTo(30 - 10);

Сначала этот метод возвращает ноль, так как все биты false . После установки диапазона [10, 30) в true вызов метода cardinality() возвращает 20.

Кроме того, метод length() возвращает один индекс после индекса последнего установленного бита :

assertThat(bitSet.length()).isEqualTo(30);
bitSet.set(100);
assertThat(bitSet.length()).isEqualTo(101);

Сначала последний заданный индекс равен 29, поэтому этот метод возвращает 30. Когда мы устанавливаем индекс 100 в значение true, метод length() возвращает 101. Также стоит упомянуть, что этот метод вернет ноль, если все биты чисты .

Наконец, метод isEmpty() возвращает false , когда в наборе битов имеется хотя бы один бит набора . В противном случае он вернет true :

assertThat(bitSet.isEmpty()).isFalse();
bitSet.clear();
assertThat(bitSet.isEmpty()).isTrue();

4.7. Объединение С Другими Наборами Битов

Метод intersects(BitSet) принимает другой BitSet и возвращает true при двух Набор битов s имеет что-то общее . То есть у них есть по крайней мере один бит набора в одном и том же индексе:

BitSet first = new BitSet();
first.set(5, 10);

BitSet second = new BitSet();
second.set(7, 15);

assertThat(first.intersects(second)).isTrue();

Диапазон [7, 9] задан в обоих BitSet s, поэтому этот метод возвращает true .

Также можно выполнить логическую операцию и на двух Набор битов s :

first.and(second);
assertThat(first.get(7)).isTrue();
assertThat(first.get(8)).isTrue();
assertThat(first.get(9)).isTrue();
assertThat(first.get(10)).isFalse();

Это выполнит логическое и между двумя BitSet s и изменит первую переменную с результатом. Аналогично, мы можем выполнить логическое xor на двух Битный набор s тоже:

first.clear();
first.set(5, 10);

first.xor(second);
for (int i = 5; i < 7; i++) {
    assertThat(first.get(i)).isTrue();
}
for (int i = 10; i < 15; i++) {
    assertThat(first.get(i)).isTrue();
}

Существуют и другие методы, такие как andNot(BitSet) или или(Bit Set) , , которые могут выполнять другие логические операции над двумя BitSet s.

4.8. Разное

Начиная с Java 8, существует метод stream () |/для потоковой передачи всех битов набора BitSet . Например:

BitSet bitSet = new BitSet();
bitSet.set(15, 25);

bitSet.stream().forEach(System.out::println);

Это выведет все установленные биты на консоль. Поскольку это вернет IntStream , мы можем выполнять обычные числовые операции, такие как суммирование, усреднение, подсчет и так Далее. Например, здесь мы подсчитываем количество установленных битов:

assertThat(bitSet.stream().count()).isEqualTo(10);

Кроме того, метод nextSetBit(fromIndex) вернет следующий битный индекс набора, начиная с fromIndex :

assertThat(bitSet.nextSetBit(13)).isEqualTo(15);

Сам fromIndex включен в этот расчет. Когда в наборе BitSet не осталось ни одного бита true , он вернет значение -1:

assertThat(bitSet.nextSetBit(25)).isEqualTo(-1);

Аналогично, | nextClearBit(fromIndex) возвращает следующий чистый индекс, начинающийся с fromIndex :

assertThat(bitSet.nextClearBit(23)).isEqualTo(25);

С другой стороны, previousClearBit(fromIndex) возвращает индекс ближайшего чистого индекса в противоположном направлении:

assertThat(bitSet.previousClearBit(24)).isEqualTo(14);

То же самое верно для previousSetBit(из индекса) :

assertThat(bitSet.previousSetBit(29)).isEqualTo(24);
assertThat(bitSet.previousSetBit(14)).isEqualTo(-1);

Кроме того, мы можем преобразовать BitSet в byte[] или long[] с помощью методов toByteArray () | или toLongArray () | соответственно:

byte[] bytes = bitSet.toByteArray();
long[] longs = bitSet.toLongArray();

5. Заключение

В этом уроке мы увидели, как мы можем использовать BitSet s для представления вектора битов.

Сначала мы познакомились с обоснованием отказа от использования boolean[] для представления вектора битов. Затем мы увидели, как BitSet работает внутри и как выглядит его API.

Как обычно, все примеры доступны на GitHub .