overloading operator[] to return an lvalue in myBitset class.

closed account (D80DSL3A)
I've recently used std::bitset<size_t> for the 1st time.
I used it to make a sieve of Eratosthenes on for finding prime numbers.

Of course I wondered, how to represent bool values on a bit level like that?
So, toy version here.
I'm happy except for one aspect. I'd like to assign bit values like so:
1
2
myBitset<100> bs;// array of 100 bits
bs[5] = true;// assign 6th bit = 1 

I have a working set function for this, and a working bool operator[] for reading values.

But I would like to assign via eg. bs[5] = true;

Presently working, with main code to generate primes to 200 (finding odd only):
Note: It is achieving 100 bit storage in 13 bytes as expected.
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
61
62
63
64
#include<iostream>
using std::cout;

template<size_t cap>
class myBitset
{
private:
    const static size_t Nele = (cap+7)/8;
    unsigned char A[Nele];
public:
    // as featured by std::bitset
    myBitset(){ for(size_t i=0; i<Nele; ++i) A[i] = 0; }// all to 0
    void set() { for(size_t i=0; i<Nele; ++i) A[i] = 0xff; }// all to 1
    size_t size()const { return cap; }

    // element (bit) access
    bool get(size_t idx)const;// read
    bool operator[](size_t idx)const;// read

    void set(size_t idx, bool b);// write
    // the missing operator[] for an lvalue return
};

template<size_t cap>
bool myBitset<cap>::get(size_t idx)const
{
    unsigned char res = A[idx/8] & (1<<idx%8);
    return res > 0;
}

template<size_t cap>
bool myBitset<cap>::operator[](size_t idx)const
{
    return get(idx);
}

template<size_t cap>
void myBitset<cap>::set(size_t idx, bool b)
{
    if(b) A[idx/8] |= 1<<idx%8;
    else  A[idx/8] &= (0xff - (1<<idx%8));
}

int main ()// generate and show all primes < 200
{
    myBitset<100> bs;
    bs.set();// all bits = 1

    // implement sieve of Eratosthenes on the bitset
    for( size_t i=0; i < bs.size(); ++i )
        if( bs[i] )// prime found
            for( size_t j = 3*(i+1); j < bs.size(); j += 3+2*i )// note: 3*(i+1) = i + 3+2*i
                bs.set(j,false); // I want to write bs[j] = false; here instead


    // show the primes
    for(size_t i=0; i<bs.size(); ++i)
       if( bs[i] ) std::cout << 3+2*i << ' ';

    std::cout << "\nsizeof bs = " << sizeof(bs) << '\n';

    cout << '\n';
    return 0;
}


I have tried the following, with partial success. It's partial because the 2 operator[] definitions can't seem to coexist

or be properly reconciled (desired version called).
I define a myBit object and include an instance as a myBitset member.
This myBit object is returned by ref from myBit& myBitset::operator[](size_t idx);
I also define operator= for myBit, so the assignment in bs[i] = true; can be made.
I can no longer use the prevoius bool myBitset::operator[](size_t idx) function, although I can use the get function fine.

Repace lines 69 and 77 below with the lines above them for error:
forumProbs\main.cpp|67|error: could not convert 'bs.myBitset<cap>::operator[]<100ull>(i)' from 'myBitset<100ull>::myBit' to 'bool'|

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
using std::cout;
//using std::cin;
//using std::string;

template<size_t cap>
class myBitset
{
private:
    const static size_t Nele = (cap+7)/8;
    unsigned char A[Nele];
    struct myBit
    {
        unsigned char* pByte;
        size_t ofst;
        myBit(unsigned char* p_byte=nullptr, size_t idx=0): pByte(p_byte ? p_byte+idx/8 : nullptr), ofst(idx%8) {}
        myBit& init(unsigned char* p_byte, size_t idx) { pByte = p_byte + idx/8; ofst = idx%8; return *this; }
        void operator=(bool b)
        {
            if(b)
                *pByte |= (1<<ofst);
            else
                *pByte &= 0xff - (1<<ofst);
        }
    };
    myBit mb;
public:
    // as featured by std::bitset
    myBitset() { for(size_t i=0; i<Nele; ++i) A[i] = 0; }// all to 0
    void set() { for(size_t i=0; i<Nele; ++i) A[i] = 0xff; }// all to 1
    size_t size()const { return cap; }

    // element (bit) access
    bool get(size_t idx)const;// read
    bool operator[](size_t idx)const;// read

    void set(size_t idx, bool b);// write
    myBit& operator[](size_t idx) { return mb.init(A,idx); }// write
};

template<size_t cap>
bool myBitset<cap>::get(size_t idx)const
{
    unsigned char res = A[idx/8] & (1<<idx%8);
    return res > 0;
}

template<size_t cap>
bool myBitset<cap>::operator[](size_t idx)const
{
    return get(idx);
}

template<size_t cap>
void myBitset<cap>::set(size_t idx, bool b)
{
    if(b) A[idx/8] |= 1<<idx%8;
    else  A[idx/8] &= (0xff - (1<<idx%8));
}

int main ()
{
    myBitset<100> bs;
    bs.set();// all bits = 1

    // implement sieve of Eratosthenes on the bitset
    for( size_t i=0; i < bs.size(); ++i )
    //    if( bs[i] )//no support
        if( bs.get(i) )// replace with line above
            for( size_t j = 3*(i+1); j < bs.size(); j += 3+2*i )// note: 3*(i+1) = i + 3+2*i
                bs[j] = false;// YAY! write method works.


    // show the primes
    for(size_t i=0; i<bs.size(); ++i)
     //  if( bs[i] ) cout << 3+2*i << ' ';//no support
       if( bs.get(i) ) cout << 3+2*i << ' ';// replace with line above

    cout << "\nsizeof bs = " << sizeof(bs) << '\n';

    cout << '\n';
    return 0;
}


How do I resolve this dilemmna and get my [] overload both ways?

EDIT: As it stands I would choose to forego the lvalue versionof [] and just use the set function.
The addition of a sub object (myBit) for the sole purpose of supporting an operator definition seems bad.
Perhaps I'm overlooking something simple?
Last edited on
closed account (D80DSL3A)
No, I hadn't closely. One reason being to see if I could think of the necessary structure myself.
The error should have given more clue. If can't convert from myBit to bool then...
overload operator bool() of course!

I see that's done with bitset::reference, an embedded class type.
So an embedded type is necessary! I'll look more carefully as I see their reference object isn't implemented at all like my myBit embedded object is.
However, addition of this overload to the myBit struct definition:
1
2
3
4
5
operator bool() const
        {
            unsigned char res = *pByte & (1<<ofst);
            return res > 0;
        }

does resolve the [] overload dilemma. I can now use both at once.
Problem solved!
Thank you.
closed account (D80DSL3A)
Implementation improving!
Instead of a myBit instance for each myBitset, use a reference to a static instance.
Introducig a myBitset member function myBit& get_ms(size_t idx) for storage and retrieval of a static instance.

Also, realized the one [] overload does all now, so down to just that.
Getting sizeof(bs) = 13 bytes again too, unlike 32 bytes for one with a myBit member.

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
61
62
63
64
65
66
67
68
69
70
#include<iostream>
using std::cout;

template<size_t cap>
class myBitset
{
private:
    const static size_t Nele = (cap+7)/8;
    unsigned char A[Nele];
    struct myBit
    {
        unsigned char* pByte;
        size_t ofst;
        myBit(unsigned char* p_byte=nullptr, size_t idx=0): pByte(p_byte ? p_byte+idx/8 : nullptr), ofst(idx%8) {}
        myBit& init(unsigned char* p_byte, size_t idx) { pByte = p_byte + idx/8; ofst = idx%8; return *this; }
        void operator=(bool b)
        {
            if(b)
                *pByte |= (1<<ofst);
            else
                *pByte &= 0xff - (1<<ofst);
        }
        operator bool() const
        {
            unsigned char res = *pByte & (1<<ofst);
            return res > 0;
        }
       void flip(){ *this = !(*this); }// NEW
    };

    // obtain reference to static instance within
    myBit& get_mb(size_t idx)// for use in oprator[] overload
    {
        static myBit mb;
        mb.init(A,idx);
        return mb;
    }
public:
    // as featured by std::bitset
    myBitset() { for(size_t i=0; i<Nele; ++i) A[i] = 0; }// all to 0
    void set() { for(size_t i=0; i<Nele; ++i) A[i] = 0xff; }// all to 1
    size_t size()const { return cap; }

   void flip(size_t idx) { get_mb(idx).flip(); }// flip bit value. NEW

    // element (bit) access
    myBit& operator[](size_t idx) { return get_mb(idx); }// read or write
};

int main ()
{
    myBitset<100> bs;
    bs.set();// all bits = 1

    // implement sieve of Eratosthenes on the bitset
    for( size_t i=0; i < bs.size(); ++i )
        if( bs[i] )// prime found
            for( size_t j = 3*(i+1); j < bs.size(); j += 3+2*i )
                bs[j] = false;

    bs[3].flip();// make 9 prime? NEW
    // show the primes
    for(size_t i=0; i<bs.size(); ++i)
       if( bs[i] ) cout << 3+2*i << ' ';

    cout << "\nsizeof bs = " << sizeof(bs) << '\n';

    cout << '\n';
    return 0;
}

Comments re. improvements are still quite welcome.

EDIT: The myBit overloads for bool() and = prove quite useful for a flip (flip bit value) function. Because of these overloads:
1
2
// flip the myBit
void flip(){ *this = !(*this); }

Then a flip function in the myBitset class:
void flip(size_t idx) { get_mb(idx).flip(); }// flip bit value
Calling bs[3].flip(); after filling the sieve makes 9 suddenly prime.
Added code to above. Marked as NEW
Last edited on
Topic archived. No new replies allowed.