Una guía para BitSet en Java

1. Información general

En este tutorial, veremos cómo podemos usar BitSet s para representar un vector de bits.

Primero, comenzaremos con la justificación detrás de no usar el booleano [] . Luego, después de familiarizarnos con los componentes internos de BitSet , analizaremos más de cerca su API.

2. Matriz de bits

Para almacenar y manipular matrices de bits, se podría argumentar que deberíamos usar boolean [] como nuestra estructura de datos. A primera vista, podría parecer una sugerencia razonable.

Sin embargo, cada miembro booleano en un booleano [] normalmente consume un byte en lugar de solo un bit . Entonces, cuando tenemos requisitos de memoria estrictos, o simplemente apuntamos a una huella de memoria reducida, boolean [] está lejos de ser ideal.

Para hacer las cosas más concretas, veamos cuánto espacio consume un booleano [] con 1024 elementos:

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

Idealmente, esperamos una huella de memoria de 1024 bits de esta matriz. Sin embargo, Java Object Layout (JOL) revela una realidad completamente diferente:

[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

Si ignoramos la sobrecarga del encabezado del objeto, los elementos de la matriz están consumiendo 1024 bytes, en lugar de los 1024 bits esperados. Eso es un 700% más de memoria de lo que esperábamos.

Los problemas de direccionabilidad y el desgarro de palabras son las principales razones por las que los booleanos son más que un solo bit.

Para resolver este problema, podemos usar una combinación de tipos de datos numéricos (como long ) y operaciones de bits. Ahí es donde entra BitSet .

3. Cómo funciona BitSet

Como mencionamos anteriormente, para lograr el uso de memoria de un bit por bandera, la API BitSet usa una combinación de tipos de datos numéricos básicos y operaciones bit a bit.

En aras de la simplicidad, supongamos que vamos a representar ocho banderas con un byte . Al principio, inicializamos todos los bits de este único byte con cero:

Ahora, si queremos establecer el bit en la posición tres en verdadero , primero debemos desplazar a la izquierda el número 1 por tres:

Y luego o su resultado con el valor del byte actual :

El mismo proceso ocurrirá si decide establecer el bit en el índice siete:

Como se muestra arriba, realizamos un desplazamiento a la izquierda de siete bits y combinamos el resultado con el valor del byte anterior usando el operador o .

3.1. Obtener un índice de bits

Para comprobar si un índice de bits en particular está establecido en verdadero o no, usaremos el operador y . Por ejemplo, así es como verificamos si el índice tres está configurado:

  1. Realización de un desplazamiento a la izquierda de tres bits en el valor uno
  2. Anding el resultado con el valor de byte actual
  3. Si el resultado es mayor que cero, entonces encontramos una coincidencia y ese índice de bits está realmente establecido. De lo contrario, el índice solicitado es claro o es igual a falso

El diagrama anterior muestra los pasos de la operación de obtención para el índice tres. Sin embargo, si preguntamos por un índice claro, el resultado será diferente:

Dado que el resultado y es igual a cero, el índice cuatro es claro.

3.2. Crecimiento del almacenamiento

Actualmente, solo podemos almacenar un vector de 8 bits. Para ir más allá de esta limitación, solo tenemos que usar una matriz de bytes , en lugar de un solo byte , ¡eso es todo!

Ahora, cada vez que necesitemos establecer, obtener o borrar un índice específico, primero debemos encontrar el elemento de matriz correspondiente. Por ejemplo, supongamos que vamos a establecer el índice 14:

Como se muestra en el diagrama anterior, después de encontrar el elemento de matriz correcto, establecimos el índice apropiado.

Además, si queremos establecer un índice más allá de 15 aquí, BitSet expandirá su matriz interna, primero. Solo después de expandir la matriz y copiar los elementos, establecerá el bit solicitado. Esto es algo similar a cómo funciona ArrayList internamente.

Hasta ahora, usamos el tipo de datos byte en aras de la simplicidad. La API de BitSet , sin embargo, usa una matriz de valores largos internamente .

4. La API de BitSet

Ahora que sabemos lo suficiente sobre la teoría, es hora de ver cómo se ve la API de BitSet .

Para empezar, comparemos la huella de memoria de una instancia de BitSet con 1024 bits con el booleano [] que vimos anteriormente:

BitSet bitSet = new BitSet(1024); System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

Esto imprimirá tanto el tamaño superficial de la instancia de BitSet como el tamaño de su matriz interna:

[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]

Como se muestra arriba, usa un largo [] con 16 elementos (16 * 64 bits = 1024 bits) internamente. De todos modos, esta instancia usa 168 bytes en total, mientras que el booleano [] usa 1024 bytes .

The more bits we have, the more the footprint difference increases. For example, to store 1024 * 1024 bits, the boolean[] consumes 1 MB, and the BitSet instance consumes around 130 KB.

4.1. Constructing BitSets

The simplest way to create a BitSet instance is to use the no-arg constructor:

BitSet bitSet = new BitSet();

This will create a BitSet instance with a long[] of size one. Of course, it can automatically grow this array if needed.

It's also possible to create a BitSet with an initial number of bits:

BitSet bitSet = new BitSet(100_000);

Here, the internal array will have enough elements to hold 100,000 bits. This constructor comes in handy when we already have a reasonable estimate on the number of bits to store. In such use cases, it can prevent or decrease the unnecessary copying of array elements while growing it.

It's even possible to create a BitSet from an existing long[], byte[], LongBuffer, and ByteBuffer. For instance, here we're creating a BitSet instance from a given long[]:

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

There are three more overloaded versions of the valueOf() static factory method to support the other mentioned types.

4.2. Setting Bits

We can set the value of a particular index to true using the set(index) method:

BitSet bitSet = new BitSet(); bitSet.set(10); assertThat(bitSet.get(10)).isTrue();

As usual, the indices are zero-based. It's even possible to set a range of bits to true using the set(fromInclusive, toExclusive) method:

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

As is evident from the method signature, the beginning index is inclusive, and the ending one is exclusive.

When we say setting an index, we usually mean setting it to true. Despite this terminology, we can set a particular bit index to false using the set(index, boolean) method:

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

This version also supports setting a range of values:

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

4.3. Clearing Bits

Instead of setting a specific bit index to false, we can simply clear it using the clear(index) method:

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

Moreover, we can also clear a range of bits with the clear(fromInclusive, toExclusive) overloaded version:

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(); }

Interestingly, if we call this method without passing any arguments, it'll clear all the set bits:

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

As shown above, after calling the clear() method, all bits are set to zero.

4.4. Getting Bits

So far, we used the get(index) method quite extensively. When the requested bit index is set, then this method will return true. Otherwise, it'll return false:

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

Similar to set and clear, we can get a range of bit indices using the get(fromInclusive, toExclusive) method:

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

As shown above, this method returns another BitSet in the [20, 30) range of the current one. That is, index 20 of the bitSet variable is equivalent to index zero of the newBitSet variable.

4.5. Flipping Bits

To negate the current bit index value, we can use the flip(index) method. That is, it'll turn true values to false and vice versa:

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

Similarly, we can achieve the same thing for a range of values using the flip(fromInclusive, toExclusive) method:

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

4.6. Length

There are three length-like methods for a BitSet. The size() method returns the number of bits the internal array can represent. For instance, since the no-arg constructor allocates a long[] array with one element, then the size() will return 64 for it:

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

With one 64-bit number, we can only represent 64 bits. Of course, this will change if we pass the number of bits explicitly:

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

Moreover, the cardinality() method represents the number of set bits in a BitSet:

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

At first, this method returns zero as all bits are false. After setting the [10, 30) range to true, then the cardinality() method call returns 20.

Also, the length() method returns the one index after the index of the last set bit:

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

At first, the last set index is 29, so this method returns 30. When we set the index 100 to true, then the length() method returns 101. It's also worth mentioning that this method will return zero if all bits are clear.

Finally, the isEmpty() method returns false when there is at least one set bit in the BitSet. Otherwise, it'll return true:

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

4.7. Combining With Other BitSets

The intersects(BitSet) method takes another BitSet and returns true when two BitSets have something in common. That is, they have at least one set bit in the same index:

BitSet first = new BitSet(); first.set(5, 10); BitSet second = new BitSet(); second.set(7, 15); assertThat(first.intersects(second)).isTrue();

The [7, 9] range is set in both BitSets, so this method returns true.

It's also possible to perform the logical and operation on two BitSets:

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

This will perform a logical and between the two BitSets and modifies the first variable with the result. Similarly, we can perform a logical xor on two BitSets, too:

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(); }

There are other methods such as the andNot(BitSet) or the or(BitSet),which can perform other logical operations on two BitSets.

4.8. Miscellaneous

As of Java 8, there is a stream() method to stream all set bits of a BitSet. For instance:

BitSet bitSet = new BitSet(); bitSet.set(15, 25); bitSet.stream().forEach(System.out::println);

This will print all set bits to the console. Since this will return an IntStream, we can perform common numerical operations such as summation, average, counting, and so on. For instance, here we're counting the number of set bits:

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

Also, the nextSetBit(fromIndex) method will return the next set bit index starting from the fromIndex:

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

The fromIndex itself is included in this calculation. When there isn't any true bit left in the BitSet, it'll return -1:

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

Similarly, the nextClearBit(fromIndex) returns the next clear index starting from the fromIndex:

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

On the other hand, the previousClearBit(fromIndex) returns the index of the nearest clear index in the opposite direction:

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

Same is true for previousSetBit(fromIndex):

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

Moreover, we can convert a BitSet to a byte[] or a long[] using the toByteArray() or toLongArray() methods, respectively:

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

5. Conclusion

En este tutorial, vimos cómo podemos usar BitSet s para representar un vector de bits.

Al principio, nos familiarizamos con la lógica de no usar boolean [] para representar un vector de bits. Luego vimos cómo funciona un BitSet internamente y cómo se ve su API.

Como de costumbre, todos los ejemplos están disponibles en GitHub.