lunes, 30 de marzo de 2009

Bitset en JAVA

Los contenedores tipo bitset están pensados para almacenar bits. Es decir, conjuntos de N valores 0/1 denominados máscaras de bits ("Bitmask types"). En cierto sentido un bitset es el contenedor más simple del mundo, contiene un número máximo N (determinado en el momento de su definición) de elementos tipo bit. Podríamos considerar que un bitset es como una matriz de bits, de forma que podría establecerse un cierto paralelismo:

bit mb[125]; // L1: matriz de bits de 125 elementos

bitset <125> bs; // L2: bitset de 125 elementos


Naturalmente la sentencia L1 es solo didáctica, no es posible en C++ porque no existe un tipo bit nativo. En cambio L2 si es correcta; define un contenedor bs de tipo bitset de 125 elementos.

La clase proporciona una serie de métodos y operadores para manipular los miembros del contenedor. Dada la naturaleza de sus miembros, estas operaciones son muy limitadas, como cambiar un valor 0 por un 1 y cosas por el estilo. Son las operaciones de bits ("Bitwise operations") que hemos tenido ocasión de ver anteriormente.

Nota: al referirse a los valores de los miembros, además de cero y uno, es frecuente encontrar expresiones como fijar ("set") poner a 1, y limpiar ("reset/clear") poner a cero.


Podría pensarse que este contenedor es innecesario, ya que los campos de bits pueden ser adecuadamente representados por los tipos enteros sin signo int, short y long, y manejados mediante los operadores estándar de manejo de bits. Sin embargo, los objetos de la clase bitset presentan ciertas ventajas. Entre otras, que pueden manejar campos de bits de cualquier longitud, mientras que los operadores estándar de manejo de bits quedan restringidos como máximo a los tipos long. (32 bits en la mayoría de plataformas). Además, a cambio de un inevitable incremento del código respecto al que se deriva de utilizar directamente tipos simples, se consigue mayor comodidad de manejo. Por ejemplo, es posible crear directamente una máscara de bits en la forma:

string s1 = "10101101";
bitset<16> bs1(s1);
bitset<16> bs2("10101101");

mientras que la construcción de una máscara equivalente utilizando los métodos convencionales nos obligaría a hacer:

unsigned short mb = 62125;

lo que supone contar en binario para establecer que el número 62125 es el que corresponde a la máscara de bits deseada.

En cierto modo, este contenedor es un caso excepcional dentro de la STL. En el sentido que no proporciona ningún iterador para recorrer sus elementos. Pero esto no significa que no puede aplicársele ninguno de los algoritmos ofrecidos por la librería. Como en el caso de las matrices, sus elementos pueden ser accedidos mediante el operador subíndice [ ], que permite utilizarlo como si fuese un puntero, y por ende, un iterador.

La clase bitset

La descripción de esta familia de tipos responde al prototipo siguiente :

template class bitset { };


El tipo size_t depende de la implementación. Pero en el compilador Borland C++ 5.5 está definido como:

typedef unsigned int size_t;

Habida cuenta que en el citado compilador:

#define UINT_MAX ULONG_MAX // maximum unsigned int value

y que:

#define ULONG_MAX 4294967295UL // maximum unsigned long value

parece razonable pensar que este tipo de contenedor permite almacenar un número suficientemente grande de elementos (4 Gbits) para cubrir la mayoría de las necesidades prácticas.

La definición se encuentra en el fichero <bitset> que responde al siguiente esquema:

template class bitset;
template bitset

operator&(const bitset&, const bitset&);
template bitset

operator|(const bitset&, const bitset&);
template bitset

operator^(const bitset&, const bitset&);
template
basic_istream&
operator>>(basic_istream& is, bitset& x);
template
basic_ostream&
operator<<(basic_ostream& os, const bitset& x);


Como puede verse, aparte de la definición de la plantilla bitset propiamente dicha, esta cabecera contiene la definición de otras funciones-operador auxiliares para realizar operaciones entre objetos de tipo bitset. Por supuesto, todas estas definiciones se realizan el subespacio std. Observe que estas funciones-operador están definidas como funciones externas (no son métodos de la clase).

Como veremos a continuación, además de los anteriores, la clase bitset dispone de otra serie de métodos públicos auxiliares que permiten realizar diversas operaciones sobre los objetos (bits) alojados en estos contenedores. Pero debe recordar que la mayoría de operadores binarios solo son aplicables cuando el tamaño (número de bits) de ambos operandos coincide.

0 comentarios: