Aquí hay una implementación de vector de bits de tamaño estático muy simple. Requiere C++ 11 para funcionar ya que se basa en el encabezado <cstdint>, pero este encabezado se encuentra bastante comúnmente ya que está basado en una característica C99. En una pizca, puede usar el encabezado C <stdint.h> y simplemente usar tipos en el espacio de nombres global.
Nota: Esto fue escrito sobre la marcha y no se ha probado en absoluto. Ni siquiera comprobé que compilara. Entonces, puede haber errores.
#include <cstdint> // ::std::uint64_t type
#include <cstddef> // ::std::size_t type
#include <algorithm>
class my_bitvector_base {
protected:
class bitref { // Prevent this class from being used anywhere else.
public:
bitref(::std::uint64_t &an_int, ::std::uint64_t mask)
: an_int_(an_int), mask_(mask)
{
}
const bitref &operator =(bool val) {
if (val) {
an_int_ |= mask_;
} else {
an_int_ &= ~mask_;
}
return *this;
}
const bitref &operator =(const bitref &br) {
return this->operator =(bool(br));
}
operator bool() const {
return ((an_int_ & mask_) != 0) ? true : false;
}
private:
::std::uint64_t &an_int_;
::std::uint64_t mask_;
};
};
template < ::std::size_t Size >
class my_bitvector : public my_bitvector_base {
private:
static constexpr ::std::size_t numints = ((Size + 63)/64);
public:
my_bitvector() { ::std::fill(array, array + numints, 0); }
bool operator [](::std::size_t bitnum) const {
const ::std::size_t bytenum = bit/64;
bitnum = bitnum % 64;
return ((ints_[bytenum] & (::std::uint64_t(1) << bitnum)) != 0) ? true : false;
}
bitref operator[](::std::size_t bitnum) {
const ::std::size_t bytenum = bit/64;
bitnum = bitnum % 64;
::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
return bitref(ints_[bytenum], mask);
}
private:
::std::uint64_t ints_[numints];
};
// Example uses
void test()
{
my_bitvector<70> bits; // A 70 bit long bit vector initialized to all false
bits[1] = true; // Set bit 1 to true
bool abit = bits[1]; // abit should be true.
abit = bits[69]; // abit should be false.
}
El conjunto my_bitvector_base cosa es crear una especie de tipo privado. Puede mencionarlo en la interfaz o implementación para las clases derivadas porque es protected, pero no puede mencionarlo en otros contextos. Esto evita que las personas guarden una copia de bitref. Esto es importante porque un bitref solo existe para permitir la asignación al resultado de operator [] porque el comité de estándares de C++, en toda su sabiduría, no ha implementado operator []= o algo similar para asignar a un elemento de matriz.
Como puede ver, un vector de bits es básicamente una matriz de bits. Los vectores de bits Fancier simularán una matriz "infinita" de bits, todos inicializados en verdadero o falso. Lo hacen mediante el seguimiento del último bit que se ha establecido y todos los bits anteriores. Y si pides un poco después de eso, solo devuelven el valor inicializado.
Un vector de buen bit también implementará operator & y otras sutilezas, por lo que se comportan como un entero sin signo muy grande con referencia a las operaciones de manipulación de bits.
¿Qué desea saber * sobre * vectores de bits? En C++, normalmente usarías 'std :: bitset' o' std :: vector 'para este –
jalf
, ni siquiera sé para qué sirven, así que cualquier cosa servirá) –
también me gustaría saber qué es la mecánica interna del bit vector. perdón por mal inglés –