|<------------------------------------ Capacidad ------------------------------------>|
Total
|<---------------------------- Capacidad ------------------------------>|<-Capacidad->|
Usada Libre
|<---------------- Capacidad ---------------->|<--- Capacidad --->|<--- Capacidad --->|
Inicial Incremental Incremental
*-------------------------------------------------------------------------------------*
|0|0|1|1|1|1|1|0|0|1|0|1|0|1|1|1|1|1|1|1|1|1|0|1|0|0|1|1|0|1|0|0|0|0|0|1| | | | | | | |
*-------------------------------------------------------------------------------------*
A A
| |
Indice -------------+ Posicion -------+
Libre
La Estructura de Datos BitSet es un vector de bits que crece tanto como se necesite. Cada componente del vector tiene un valor booleano que puede ser solo verdadero o falso. Los bits del BitSet estan indexados por un entero no negativo. Los valores de cada bit pueden ser examinados y alterados individualmente. Un BitSet puede ser usado para modificar el contenido de otro BitSet a traves de las operaciones booleanas logicas AND, OR inclusivo y OR exclusivo. Todos los bits tienen inicialmente el valor falso.
Para trabajar con cadenas de bits es necesario que el lenguaje cuente
con operadores de bits como los siguientes :
crearBitSet(bitset)
crearBitSet(capacidadInicial, bitset)
averiguarCapacidadTotal(bitset, capacidad)
averiguarCapacidadUsada(bitset, capacidad)
averiguarCapacidadLibre(bitset, capacidad)
averiguarCapacidadVacia(bitset, boolean)
prenderPosicion(bitset, posicion, bitset)
apagarPosicion(bitset, posicion, bitset)
ejecutarAnd(bitset, bitset, bitset)
ejecutarOr(bitset, bitset, bitset)
ejecutarXor(bitset, bitset, bitset)
ejecutarAndNot(bitset, bitset, bitset)
ejecutarIgualdad(bitset, bitset,boolean)
ejecutarCopia(bitset, bitset)
BitSet()
Creates a new bit set.
BitSet(int nbits)
Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.
boolean get(int bitIndex)
Returns the value of the bit with the specified index.
void set(int bitIndex)
Sets the bit specified by the index to true.
void clear(int bitIndex)
Sets the bit specified by the index to false.
int length()
Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
int size()
Returns the number of bits of space actually in use by this BitSet to represent bit values.
void and(BitSet set)
Performs a logical AND of this target bit set with the argument bit set.
void or(BitSet set)
Performs a logical OR of this bit set with the bit set argument.
void xor(BitSet set)
Performs a logical XOR of this bit set with the bit set argument.
void andNot(BitSet set)
Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
boolean equals(Object obj)
Compares this object against the specified object.
Object clone()
Cloning this BitSet produces a new BitSet that is equal to it.
int hashCode()
Returns a hash code value for this bit set.
String toString()
Returns a string representation of this bit set.
BitSet()
Creates a new bit set.
BitSet(int nbits)
Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.
void and(BitSet set)
Performs a logical AND of this target bit set with the argument bit set.
void andNot(BitSet set)
Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
void clear(int bitIndex)
Sets the bit specified by the index to false.
Object clone()
Cloning this BitSet produces a new BitSet that is equal to it.
boolean equals(Object obj)
Compares this object against the specified object.
boolean get(int bitIndex)
Returns the value of the bit with the specified index.
int hashCode()
Returns a hash code value for this bit set.
int length()
Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
void or(BitSet set)
Performs a logical OR of this bit set with the bit set argument.
void set(int bitIndex)
Sets the bit specified by the index to true.
int size()
Returns the number of bits of space actually in use by this BitSet to represent bit values.
String toString()
Returns a string representation of this bit set.
void xor(BitSet set)
Performs a logical XOR of this bit set with the bit set argument.
Esta implementacion usa un modelo de memoria que es una array de longs.
Los longs tienen 64 bits o 8 bytes cada uno. Para representar 1000 bits
es necesario 1000 / 8 = 125 bytes o 1000 / 64 = 15,625 longs.
Para 1000000 de bits es necesario
1000000 / 8 = 125000 bytes o 1000000 / 64 = 15625 longs.
*--------*
0 | | long
*--------*
1 | | long
*--------*
. .
. .
. .
. .
. .
*--------*
n-2 | | long
*--------*
n-1 | | long
*--------*
BitSet is a class you use to represent vectors of bits or
true/false values.
You can represents bitmaps and similar kinds of structures with
BitSet
objects.
BitSet
grow dynamically as new bits are set.
To start the discussion of BitSet, let's look at an example:
import java.util.BitSet;
public class BitSet1
{
public static void main(String args[])
{
// create a BitSet
BitSet bitset = new BitSet();
// set the 0th and 1000th bits
bitset.set(0);
bitset.set(1000);
// display the size, length, and cardinality
System.out.println( "size = " + bitset.size());
System.out.println( "length = " + bitset.length());
System.out.println( "cardinality = " + bitset.cardinality());
// list the bits that are set, using toString()
System.out.println("list #1 = " + bitset);
// list the bits that are set, using a loop
System.out.print("list #2 = ");
for (int i = 0, len = bitset.length(); i < len; i++)
{
if (bitset.get(i))
{
System.out.print(i + " ");
}
}
System.out.println();
// list the bits that are set, using an iterator
System.out.print("list #3 = ");
for (int i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i + 1))
{
System.out.print(i + " ");
}
System.out.println();
}
}
The BitSet1 program creates a BitSet and sets the 0th and 1000th bits to true. Other bits between 0 and 1000 have false values. BitSet allocates enough memory internally to represent the highest set bit. Bits beyond
the highest set bit are considered to be false.
One way of thinking about a BitSet is that it's a vector
of 2^31 true or false bits, with all of the bits initially
set to false. The bits have indices from
0 to Integer.MAX_VALUE, or 2^31 - 1
.
As bits are set to true, memory is allocated to represent them.
The program prints the size, length, and cardinality of the BitSet. The size is the the actual number of bits used by the BitSet. The length is the index of the highest set bit plus one. The cardinality is the number of bits curr
ently set to true in the BitSet.
The program also illustrates three ways of retrieving a list of the set bits in the BitSet. The first way uses the BitSet.toString method. The second way uses a loop and the get method to check each index in the BitSet.nextSetBit method to iterate across all the set bits.
When you run the program, the output is:
size = 1024
length = 1001
cardinality = 2
list #1 = {0, 1000}
list #2 = 0 1000
list #3 = 0 1000
This example also illustrates the idea that internal space to store the bits is dynamically allocated as needed. For example, if the 1000th bit is set, then the BitSet must grow to about 125 bytes.
Here's another example that illustrates this point:
import java.util.BitSet;
public class BitSet2
{
public static void main(String args[])
{
BitSet bitset = new BitSet();
bitset.set(1000000);
System.out.println( "number of bytes required = " + bitset.size() / 8);
}
}
This BitSet2 program sets the millionth bit in a BitSet. The output of the program is:
number of bytes required = 125008
This particular BitSet object must grow to about 125,000 bytes to represent the millionth bit. Note that you can specify the size of the BitSet to the constructor, that is, if you know in advance how big the BitSet i
s likely to get. Doing this will save time and space reallocation as well as copying. BitSet as currently implemented uses a particular internal data structure (64-bit longs) to represent bits. This representation is not part of the external
BitSet interface, however this tip assumes a particular model of memory allocation. This model is based on an array of longs, which represent all bits, true or false, so as to include the highest set bit. However, there are other possible way
s to represent sets of bits. Note that the results from the size method might not make much sense if some other type of internal structure is used.
Let's look at another example. This one shows how you can perform common logical operations on a pair of BitSets:
import java.util.BitSet;
public class BitSet3
{
public static void main(String args[])
{
// create two sets of bits
BitSet bitset1 = new BitSet();
bitset1.set(1);
bitset1.set(5);
bitset1.set(8);
BitSet bitset2 = new BitSet();
bitset2.set(2);
bitset2.set(5);
bitset2.set(7);
bitset2.set(11);
// make a copy of the first one and XOR with the second
BitSet result = (BitSet)bitset1.clone();
result.xor(bitset2);
System.out.println(bitset1 + " XOR " + bitset2 + " = " + result);
}
}
Normally, when you have two BitSets and you do a logical operation like this:
bitset1.xor(bitset2);
The result of the operation (exclusive-OR) is left in bitset1. But the idea in this example is to leave bitset1 unchanged. So the program makes a copy of bitset1 using the clone method.
When you run this example, the result is:
{1, 5, 8} XOR {2, 5, 7, 11} = {1, 2, 7, 8, 11}
A bit is set in the result BitSet if it is set in one, but not both, of the operand BitSets. The BitSet class offers similar methods for computing AND, OR, and ANDNOT. The ANDNOT method, which performs the operation a & ~b, is used to mask out bits in a BitSet.
A final example illustrates how you use BitSet features to operate on a range or group of bits:
import java.util.BitSet;
public class BitSet4
{
public static void main(String args[])
{
BitSet bitset1 = new BitSet();
// set bits from 0 (inclusive) to 99 (exclusive)
bitset1.set(0, 99);
// get bits from 0 (inclusive) to 9 (exclusive)
BitSet bitset2 = bitset1.get(0, 9);
System.out.println(bitset2);
}
}
The BitSet4 program creates a BitSet, and then sets bits 0-98 to true. Then bits 0-8 of this BitSet are copied into a new BitSet. The output is:
{0, 1, 2, 3, 4, 5, 6, 7, 8}
BitSet is an efficient way to represent and manipulate a large number of true/false values.
Terminologia utilizada segun cambios en el contenido de los elementos :
Terminologia utilizada segun cambios en la cantidad de elementos :
*---------------*
| Lenguaje |
| de |
| Programacion |
*---------------*
|
*---------------*
| Sentencias de |
| Programacion |
| para Arreglos |
*---------------*
| | | | |
+-----------------------------------+ | | | +-----------------------------------+
| +-----------------+ | +-----------------+ |
| | | | |
*---------------* *---------------* *---------------* *---------------* *---------------*
| | | | | | | | | |
| Strings | | Arreglos | | Vectores | | BitSets | | StringBuffers |
| | | | | | | | | |
*---------------* *---------------* *---------------* *---------------* *---------------*
Constante Fijo Mutante Fijo Mutante Variable Mutante Variable Mutante Variable
*---------------*
| Lenguaje |
| de |
| Programacion |
*---------------*
|
*---------------*
| Sentencias de |
| Programacion |
| para Arreglos |
*---------------*
|
*---------------*
| |
| Arreglos |
| |
*---------------*
| | | |
+-------------------------+ | | +-------------------------+
| +-------+ +-------+ |
| | | |
*---------------* *---------------* *---------------* *---------------*
| | | | | | | |
| Strings | | Vectores | | BitSets | | StringBuffers |
| | | | | | | |
*---------------* *---------------* *---------------* *---------------*
*---------------*
| Lenguaje |
| de |
| Programacion |
*---------------*
|
*---------------*
| Sentencias de |
| Programacion |
| para Arreglos |
*---------------*
|
*---------------*
| |
| Arreglos |
| |
*---------------*
| |
| |
+-------+ +-------+
| |
*---------------* *---------------*
| | | |
| Strings | | Vectores |
| | | |
*---------------* *---------------*
| |
| |
+-------+ +-------+
| |
*---------------* *---------------*
| | | |
| BitSets | | StringBuffers |
| | | |
*---------------* *---------------*
*---------------*
| Lenguaje |
| de |
| Programacion |
*---------------*
| | | | |
+-----------------------------------+ | | | +-----------------------------------+
| +-----------------+ | +-----------------+ |
| | | | |
*---------------* *---------------* *---------------* *---------------* *---------------*
| | | | | | | | | | Estructuras
| Strings | | Arreglos | | Vectores | | BitSets | | StringBuffers | de Datos
| | | | | | | | | | Standard
*---------------* *---------------* *---------------* *---------------* *---------------*
| | | | |
| | | | |
| | | | |
*---------------* *---------------* *---------------* *---------------* *---------------*
| | | | | | | | | | Estructuras
| Strings | | Arreglos | | Vectores | | BitSets | | StringBuffers | de Datos
| | | | | | | | | | Personalizadas
*---------------* *---------------* *---------------* *---------------* *---------------*
Constante Fijo Mutante Fijo Mutante Variable Mutante Variable Mutante Variable
Cuando deseo personalizar una estructura de datos, agregándole más métodos, o modificando los
métodos existentes, lo correcto es extender la clase standard y codificar solo los agregados
o modificaciones pertinentes.