0%

bit_vector

C version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// i >> 5   equal to i / 32
// i & 0x1f equal to i % 32
class BitVector {
enum {BITSPERWORD = 32, SHIFT = 5, MASK = 0x1f};
int *x;
public:
void set(int i) {
x[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i) {
x[i >> SHIFT] &= ~(1 << (i & MASK));
}
bool test(int i) {
return x[i >> SHIFT] & (1 << (i & MASK));
}

BitVector(int maxelement) {
x = new int[1 + maxelement / BITSPERWORD];
for (int i = 0; i < maxelement; i++)
clr(i);
}
};

C++ version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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(ints_, ints_ + numints, 0); }

bool operator [](::std::size_t bitnum) const {
const ::std::size_t bytenum = bitnum / 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 = bitnum / 64;
bitnum = bitnum % 64;
::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
return bitref(ints_[bytenum], mask);
}

private:
::std::uint64_t ints_[numints];

};

reference

http://stackoverflow.com/questions/8565674/bit-vectors-in-c