Yong's Blog
0%

bit_vector

Posted on In Views: Valine:

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