El impulso tiene más de 150 bibliotecas, donde un par de las bibliotecas más utilizadas ya estaban incluidas en la biblioteca estándar de C++. El dynamic_bitset es una poderosa biblioteca utilizada para la manipulación de bits. La clase dynamic_bitset se utiliza para representar un conjunto de bits en forma de 0 (restablecer) o 1 (establecer). dynamic_bitset es una mejora sobre el conjunto de bits ( std::bitset y boost::bitset ) que asigna cualquier longitud requerida de bits en tiempo de ejecución, a diferencia del conjunto de bits cuya longitud de bits debe determinarse en tiempo de compilación.
El dynamic_bitset si se encuentra bajo el encabezado boost boost/dynamic_bitset.hpp .
Sintaxis:
boost::dynamic_bitset <uint8_t> B (N, num);
Los parámetros de los constructores son
- N que significa el número requerido de bits en el conjunto.
- num significa cualquier valor integral cuyos bits se almacenarán.
- uint8_t significa el tamaño del bloque (8 aquí, también puede estar vacío si no necesitamos especificar el tamaño del bloque).
Se puede acceder a cada bit individual del conjunto de bits dinámico de manera similar al operador de indexación del conjunto de bits [].
Tenga en cuenta que la representación de bits de un número B en dynamic_bitset de longitud n se representa como:
B[n-1] B[n-2] ... B[1] B[0]
En otras palabras, la indexación en dynamic_bitset funciona en orden inverso (similar a bitset). Cada bit en dynamic_bitset ocupa exactamente un espacio de 1 bit debido a su optimización, lo que hace que las operaciones sean más rápidas que el vector booleano.
Funciones de miembro:
las funciones de miembro básicas que se pueden realizar en dynamic_bitset se enumeran a continuación:
- set() : Asigna cada bit con 1
- reset() : Asigna el bit n con 0 si se pasa el n en el argumento, de lo contrario, borra todo el objeto del conjunto de bits.
- flip() : Invierte cualquier bit dado, es decir, cambia de 0 a 1 o viceversa
- size() : Devuelve el tamaño del objeto dynamic_bitset
- resize() : Se utiliza para aumentar o disminuir el tamaño del objeto
- push_back() : aumenta el tamaño del objeto dynamic_bitset en uno y empuja el valor en MSB
- pop_back() : Elimina un bit de MSB
- num_blocks() : Devuelve el número de bloques en el conjunto de bits
- append : Agrega los bits en el bit más significativo. Esto aumenta el tamaño del conjunto de bits en bits_per_block. Para i en el rango [0, bits_por_bloque), el bit en la posición (tamaño + i) se establece en ((valor >> i) y 1)
- vacío() : devuelve verdadero si la longitud de dynamic_bitset es 0, de lo contrario, devuelve falso.
- count() : Devuelve el número de bits establecidos en dynamic_bitset.
- all() : Comprueba si todos los bits en dynamic_bitset están establecidos, si lo están, devuelve verdadero, de lo contrario, falso.
- any() : Comprueba si al menos uno de los bits en dynamic_bitset está configurado, si lo están, devuelve verdadero, de lo contrario, falso.
- none() : Comprueba si ninguno de los bits en dynamic_bitset está configurado, si ninguno de ellos está configurado, devuelve verdadero o falso.
- test() : Comprueba si el i -ésimo bit está activado o no. Si se establece, devuelve verdadero, de lo contrario, falso.
Ejemplo 1:
CPP
#include <boost/dynamic_bitset.hpp> #include <iostream> using namespace std; int main(int argc, char* argv[]) { int bit_size = 8; // B1 is initialized with size 0 // with all bits 0 boost::dynamic_bitset<> B1; // B2 is initialized with size // bit_size with all bits 0 boost::dynamic_bitset<> B2(bit_size); // B3 is initialized with size // bit_size and value 14 boost::dynamic_bitset<> B3(bit_size, 14); // B4 is initialized with size // bit_size, value 14 and // block_size of 8 bits boost::dynamic_bitset<uint8_t> B4(16, 84); // Empty cout << "Content of B1 is: " << B1 << endl; // 00000000 cout << "Content of B2 is: " << B2 << endl; cout << "Binary representation of 14 in 8 bit: " << B3 << endl; cout << "Content of B4 is: " << B4 << endl << endl; // Setting 1 st of B2 to 1 cout << "Content of B2 before set(): " << B2 << endl; B2.set(0); cout << "Content of B2 after set(0): " << B2 << endl; // Setting every bits of B22 to 1 B2.set(); cout << "Content of B2 after set(): " << B2 << endl; // Resetting 2nd bit to 0 B2.reset(1); cout << "After resetting 2nd bit of B2: " << B2<< endl; // Resetting every bit to 0 B2.reset(); cout << "After resetting every bit of B2: " << B2 << endl; // Flipping first bit of B3 cout << "Content of B3 before flip(): " << B3 << endl; B3.flip(0); cout << "Content of B3 after flip(0): " << B3 << endl; // Flipping every bits of B3 B3.flip(); cout << "Content of B3 after flip(): " << B3 << endl << endl; // Size of B1, B2, B3, B4 cout << "Size of B1 is: " << B1.size() << endl; cout << "Size of B2 is: " << B2.size() << endl; cout << "Size of B3 is: " << B3.size() << endl; cout << "Size of B4 is: " << B4.size() << endl << endl; // Resizing B1 to size 4, // default bit-value 0 B1.resize(4); cout << "B1 after increasing size to 4 bits: " << B1 << endl; // Resizing B1 to size 8, bit-value 1. // If num_bits > size() then the bits // in the range [0, size()) remain the same, // and the bits in [size(), num_bits) // are all set to value (here 1). B1.resize(8, 1); cout << "B1 after increasing size to 8 bits: " << B1 << endl; // Resizing B1 to size 1 i.e. // slicing [1, B1.size()-1) B1.resize(1); cout << "B1 after decreasing size to 1 bit: " << B1 << endl << endl; // Pushing a set bit at MSB in B1 B1.push_back(1); cout << "B1 after push(1) operation: " << B1 << endl; // Pushing a reset bit at MSB in B1 B1.push_back(0); cout << "B1 after push(0) operation : " << B1 << endl << endl; // Popping 1 bit from MSB in B1 cout << "B1 before pop operation: " << B1 << endl; B1.pop_back(); cout << "B1 after pop operation: " << B1 << endl << endl; // Number of blocks = number of bits / block size cout << "Number of blocks in B4: " << B4.num_blocks() << endl << endl; // Checking if any bitset is empty cout << "B1 is " << (B1.empty() ? "empty" : "not empty") << endl; cout << "B2 is " << (B2.empty() ? "empty" : "not empty") << endl; // Resizing B3 to 0 B3.resize(0); cout << "B3 is " << (B3.empty() ? "empty" : "not empty") << endl << endl; // Counting number of set bits in B4 cout << "Content of B4 is: " << B4 << endl; cout << "Number of set bits in it are: " << B4.count() << endl << endl; // Checking if all of the bits of B2 is set B2.set(); // B2 => 11111111 cout << "All bits in B2 are " << (B2.all() ? "set" : "not set") << endl; B2.reset(2); // B2 => 11111011 cout << "All bits in B2 are " << (B2.all() ? "set" : "not set") << endl << endl; // Checking if any of the bits of B2 is set cout << (B2.any() ? "Atleast one" : "No") << " bit in B2 is set " << endl; B2.reset(); // B2 => 00000000 cout << (B2.any() ? "Atleast one" : "No") << " bit in B2 is set " << endl << endl; // Checking if none of the bits of B2 are set // B2 => 00000000 if (B2.none()) cout << "None of the bits in B2 is set"; else cout << "Atleast one bit in B2 is set"; cout << endl << endl; // Testing if 1st bit of B1 is set or not cout << "Content of B1 is: " << B1 << endl; if (B1.test(1)) cout << "B1[1] is set"; else cout << "B1[1] is reset"; return 0; }
Content of B1 is: Content of B2 is: 00000000 Binary representation of 14 in 8 bit: 00001110 Content of B4 is: 0000000001010100 Content of B2 before set(): 00000000 Content of B2 after set(0): 00000001 Content of B2 after set(): 11111111 After resetting 2nd bit of B2: 11111101 After resetting every bit of B2: 00000000 Content of B3 before flip(): 00001110 Content of B3 after flip(0): 00001111 Content of B3 after flip(): 11110000 Size of B1 is: 0 Size of B2 is: 8 Size of B3 is: 8 Size of B4 is: 16 B1 after increasing size to 4 bits: 0000 B1 after increasing size to 8 bits: 11110000 B1 after decreasing size to 1 bit: 0 B1 after push(1) operation: 10 B1 after push(0) operation : 010 B1 before pop operation: 010 B1 after pop operation: 10 Number of blocks in B4: 2 B1 is not empty B2 is not empty B3 is empty Content of B4 is: 0000000001010100 Number of set bits in it are: 3 All bits in B2 are set All bits in B2 are not set Atleast one bit in B2 is set No bit in B2 is set None of the bits in B2 is set Content of B1 is: 10 B1[1] is set
Operadores:
algunos de los operadores que pueden ser útiles para la manipulación de bits:
- operator[] : Devuelve una referencia de n -ésimo bit.
- operator&=() : Realiza AND bit a bit con el objeto de conjunto de bits actual y el objeto de conjunto de bits pasado en el argumento. P.ej. B1.operador&=(B2); AND bit a bit de B1 y B2, es decir, B1 y B2 (B1 y B2 deben tener el mismo número de bits).
- operator|=() : realiza OR bit a bit con el objeto de conjunto de bits actual y el objeto de conjunto de bits pasado en el argumento. P.ej. B1.operador|=(B2); OR bit a bit de B1 y B2, es decir, B1 | B2 (B1 y B2 deben tener el mismo número de bits).
- operator^=() : Realiza bitwise-XOR con el objeto de conjunto de bits actual y el objeto de conjunto de bits pasado en el argumento. P.ej. B1.operador^=(B2); Bitwise-XOR de B1 y B2, es decir, B1 ^ B2 (B1 y B2 deben tener el mismo número de bits).
- operator-=() : Realiza la diferencia establecida con el objeto de conjunto de bits actual y el objeto de conjunto de bits pasado en el argumento. P.ej. B1.operador-=(B2); establezca la diferencia de B1 y B2, es decir, B1 – B2 (B1 y B2 deben tener el mismo número de bits).
- operator=() : Asigna el objeto de conjunto de bits actual con el objeto pasado en el parámetro.
- operator==() : Valida si el objeto bitset actual es exactamente igual al pasado como parámetro.
- operator!=() : Valida si el objeto bitset actual no es igual al pasado como parámetro.
- operator<() : Devuelve verdadero si el conjunto de bits actual es lexicográficamente menor que el objeto de conjunto de bits pasado como parámetro; de lo contrario, devuelve falso.
- operator>() : Devuelve verdadero si el conjunto de bits actual es lexicográficamente mayor que el objeto del conjunto de bits pasado como parámetro; de lo contrario, devuelve falso.
- operator<=() : Devuelve verdadero si el conjunto de bits actual es lexicográficamente menor o igual que el objeto de conjunto de bits pasado como parámetro; de lo contrario, devuelve falso.
- operator>=() : Devuelve verdadero si el conjunto de bits actual es lexicográficamente mayor o igual que el objeto de conjunto de bits pasado como parámetro; de lo contrario, devuelve falso.
- operator~() : Crea una copia del conjunto de bits actual con todos sus bits invertidos.
- operator<<() : Crea una copia del objeto de conjunto de bits actual que se desplaza a la izquierda en n bits.
- operator>>() : Crea una copia del objeto de conjunto de bits actual que se desplaza a la derecha n bits.
- operator<<=() : Desplaza el objeto de conjunto de bits actual a la izquierda en n bits.
- operator>>=() : Desplaza el objeto de conjunto de bits actual hacia la derecha en n bits.
Ejemplo 2:
CPP
#include <boost/dynamic_bitset.hpp> #include <iostream> using namespace std; int main(int argc, char* argv[]) { int n_bits = 8; boost::dynamic_bitset<> B1(n_bits, 123); boost::dynamic_bitset<> B2(n_bits, 206); boost::dynamic_bitset<> temp(4, 3); cout << "Binary representation of 123: " << B1 << endl; cout << "Binary representation of 206: " << B2 << endl << endl; // Operator[] is used to access an individual index // It is a reference of the nth bit. It can be used for // assignment of a boolean value at nth bit cout << "4th bit of B1 consist: " << B1[3] << endl; B1[3] = 0; cout << "Assigning 0 to 4th bit of B1: " << B1 << endl << endl; // Operator= assigns on current bitset object cout << "temp before assignment: " << temp << endl; temp.operator=(B1); cout << "temp after assignment with B1: " << temp << endl << endl; // Operator&= performs bitwise-AND cout << "B1 consist of: " << B1 << endl; cout << "B2 consist of: " << B2 << endl; temp.operator=(B1); temp.operator&=(B2); cout << "B1 AND B2 is : & " << temp << endl << endl; // Operator|= performs bitwise-OR cout << "B1 consist of: " << B1 << endl; cout << "B2 consist of: " << B2 << endl; temp.operator=(B1); temp.operator|=(B2); cout << "B1 OR B2 is : | " << temp << endl << endl; // Operator^= performs bitwise-XOR cout << "B1 consist of: " << B1 << endl; cout << "B2 consist of: " << B2 << endl; temp.operator=(B1); temp.operator^=(B2); cout << "B1 XOR B2 is : ^ " << temp << endl << endl; // Operator-= performs set difference cout << "B1 consist of: " << B1 << endl; cout << "B2 consist of: " << B2 << endl; temp.operator=(B1); temp.operator-=(B2); cout << "Set differ is: " << temp << endl << endl; // Operator== checks if bitset object is equal to // another one, bit length has to be same for true cout << "dynamic_bitset B1 and B2 are " << (operator==(B1, B2) ? "equal" : "not equal") << endl; boost::dynamic_bitset<> B3(2, 0), B4(3, 0); cout << "Content of B3: " << B3 << endl << "Content of B4: " << B4 << endl << "dynamic_bitset B3 and B4 are " << (operator==(B3, B4) ? "equal" : "not equal") << endl; B3.operator=(B4); cout << "dynamic_bitset B3 and B4 are: " << (operator==(B3, B4) ? "equal" : "not equal") << endl << endl; // Operator!= checks if bitset object is unequal cout << "dynamic_bitset B1 and B2 are "; cout << (operator!=(B1, B2) ? "not equal" : "equal") << endl << endl; // Operator< checks if first bitset object is // lexicographically less than second one cout << "B1 consist of: " << B1 << endl; cout << "B2 consist of: " << B2 << endl; if (operator<(B1, B2)) cout << "B1 is lexicographically less than B2"; else cout << "B2 is lexicographically greater than B2"; cout << endl << endl; // Operator> checks if first bitset object is // lexicographically greater than second one cout << "B1 consist of: " << B1 << endl; boost::dynamic_bitset<> B5(8, 0); cout << "B5 consist of: " << B5 << endl; if (operator>(B1, B5)) cout << "B1 is lexicographically greater than B5"; else cout << "B1 is lexicographically less than B5"; cout << endl << endl; // Operator<= checks if first bitset object is // lexicographically less than or equal to second one cout << "B3 is lexicographically "; if (operator<=(B3, B3)) cout << "less than or equal to B3" << endl << endl; else cout << "greater than B3" << endl << endl; // Operator>= cout << "B5 consist of: " << B5 << endl; cout << "B2 consist of: " << B2 << endl; cout << "B5 is lexicographically "; if (operator>=(B5, B2)) cout << "greater than or equal to B2"; else cout << "less than B2"; cout << endl << endl; // Operator~ creates a copy of flipped bitset object cout << "Value of dynamic_bitset B4 : " << B4 << endl; cout << "Creating flipped copy of B4: "; cout << B4.operator~() << endl << endl; // Operator<< creates a copy of current bitset object // which is shifted to left by n times cout << "Value of dynamic_bitset B2: " << B2 << endl; cout << "Copy of B2 left shift 3 times is : "; cout << B2.operator<<(3) << endl; // Operator>> creates a copy of current bitset object // which is shifted to right by n times value of B2 // is not changed, the copy is displayed cout << "Copy of B2 right shift 1 time is : "; cout << B2.operator>>(1) << endl << endl; // Operator<<= shifts the current bitset object // n times to left cout << "Value of dynamic_bitset B2: " << B2 << endl; cout << "B2 left shift 3 times is : "; cout << B2.operator<<=(2) << endl; // Operator>>= shifts current bitset object // n times value to right cout << "B2 right shift 1 time is : "; cout << B2.operator>>=(3); return 0; }
Binary representation of 123: 01111011 Binary representation of 206: 11001110 4th bit of B1 consist: 1 Assigning 0 to 4th bit of B1: 01110011 temp before assignment: 0011 temp after assignment with B1: 01110011 B1 consist of: 01110011 B2 consist of: 11001110 B1 AND B2 is : & 01000010 B1 consist of: 01110011 B2 consist of: 11001110 B1 OR B2 is : | 11111111 B1 consist of: 01110011 B2 consist of: 11001110 B1 XOR B2 is : ^ 10111101 B1 consist of: 01110011 B2 consist of: 11001110 Set differ is: 00110001 dynamic_bitset B1 and B2 are not equal Content of B3: 00 Content of B4: 000 dynamic_bitset B3 and B4 are not equal dynamic_bitset B3 and B4 are: equal dynamic_bitset B1 and B2 are not equal B1 consist of: 01110011 B2 consist of: 11001110 B1 is lexicographically less than B2 B1 consist of: 01110011 B5 consist of: 00000000 B1 is lexicographically greater than B5 B3 is lexicographically less than or equal to B3 B5 consist of: 00000000 B2 consist of: 11001110 B5 is lexicographically less than B2 Value of dynamic_bitset B4 : 000 Creating flipped copy of B4: 111 Value of dynamic_bitset B2: 11001110 Copy of B2 left shift 3 times is : 01110000 Copy of B2 right shift 1 time is : 01100111 Value of dynamic_bitset B2: 11001110 B2 left shift 3 times is : 00111000 B2 right shift 1 time is : 00000111
Aplicaciones:
- dynamic_bitset se puede usar de manera efectiva para representar un subconjunto de un conjunto finito. Cada bit representa si un elemento del conjunto finito está en el subconjunto o no.
- Tamiz de Eratóstenes para encontrar todos los números primos por debajo de un número entero N.
Referencia: https://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html
Publicación traducida automáticamente
Artículo escrito por abhisheksingh5275 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA