Implementemos el conjunto de bits en C++, de modo que las siguientes operaciones se puedan realizar en las complejidades de tiempo establecidas:
- init (tamaño int): inicializa un conjunto de bits de tamaño 0 bits.
- void fix(int pos): cambia el bit en la posición pos a 1. Sin cambios si ya era 1.
- void unfix(int pos): cambia el bit en la posición pos a 0. Sin cambios si ya era 0.
- void flip(): cambia todos los 1 a 0 y todos los 0 a 1.
- bool check(): si todos los valores del conjunto de bits son 1, devuelve verdadero, de lo contrario, devuelve falso.
- bool checkOne() : si al menos un bit es 1 , devuelve verdadero. De lo contrario, devuelve falso.
- int countOne() : devuelve el número de bits cuyo valor es 1.
- string Value(): devuelve el valor actual del conjunto de bits en forma de string.
El init(tamaño) debe tener una complejidad O(tamaño) (aproximadamente). El resto de las operaciones deben tener una complejidad constante.
O(tamaño/d) donde d puede ser 32 o 64 (dependiendo de los bits).
Implementación: la implementación requerida se puede realizar fácilmente manteniendo una string de un tamaño determinado y realizando todas las operaciones en ella manteniendo simultáneamente un recuento de 0 y 1 en ella. Pero la operación de volteo no sería posible en tiempo constante con este enfoque.
Entonces, en lugar de 1, mantendremos dos strings. Una es la string original y la otra es la string opuesta a la string original (es decir, en las posiciones de 0, mantendremos 1 y viceversa). En la operación de volteo , simplemente podemos intercambiar las 2 cuerdas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// initializing variables to store
// the number of 0s , 1s and size of
// out bitset
int zero = 0, one = 0, sz = 0;
// string "s" is the string to store
// our bitset, string "t" is the
// helper string to make flip()
// function complexity O(1)
string s, t;
// function to initialize the bitset
// of size "size"
void init(int size)
{
string ss(size, '0');
string tt(size, '1');
t = tt;
s = ss;
// initially number of zeroes in
// string s is equal to size
zero = size;
sz = size;
}
// function to make bit at position
//"pos" equal to 1
void fix(int pos)
{
// setting bit at position "pos"
// equal to 1 in string s and equal
// to 0 in string t and simultaneously
// updating
// number of 0s and 1s in string s
if (s[pos] == '0') {
one++;
zero--;
}
t[pos] = '0';
s[pos] = '1';
}
// function to make bit at position "pos"
// equal to 0
void unfix(int pos)
{
// setting bit at position "pos" equal
// to 0 in string s and equal to 1 in
// string t and simultaneously
// updating
// number of 0s and 1s in string s
if (s[pos] == '1') {
zero++;
one--;
}
t[pos] = '1';
s[pos] = '0';
}
// function to flip the bits of bitset
void flip()
{
// for flip operation , we will simply
// swap the strings s and t as they are
// just opposite of each other. Also,
// we will swap number of 0s and 1s in
// string s obviously
swap(s, t);
swap(one, zero);
}
// function to check if all the elements of
// bitset are '1'
bool check()
{
// If number of 1s in string s is equal
// to the size of s, that means all the
// characters of s are 1.
return (one == sz);
}
// function for checking if there is atleast
// one '1' in bitset
bool checkOne() { return (one > 0); }
// function for returning the number of 1s
// in bitset
int countOne() { return one; }
// function for returning value of string s
// or the bitset
string Value() { return s; }
int main()
{
init(5); // 00000
fix(1); // 01000
fix(2); // 01100
unfix(1); // 00100
flip(); // 11011
int number_of_ones = countOne(); // 4
string bitset = Value(); // 11011
cout << "number of ones in our bitset are: "
<< number_of_ones << endl;
cout << "Value of our bitset is: " << bitset << endl;
}
number of ones in our bitset are: 4 Value of our bitset is: 11011
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA