BitArray Organization and Manipulation

[markymark99]

Hello all I am assigned to make a bit array class and I would like some assistance on some definitions of the class. I need to make a Set(), Unset(),Query(), and Flip() member function and all of these have unsigned int variables as parameters. Set() should set that bit to 1, without affecting any others. Unset() should set that bit to 0, without affecting any others. Flip() should change that bit to its opposite, without affecting any others. Query() should return true if that bit is currently 1, and it should return false if that bit is currently . If anyone can help that would be great.

[TheIdeasMan]

What have you done so far?

[markymark99]

Ive oly got the defenition structure down ie.

void BitArray::Flip(unsigned int index)
{
   barray[index] = ~barray[index];
}

Flip() is the only one that is defined but Im not sure if that is even right.

[gunnerfunner]

Choose a container to store the bits – there are some problems with std::vector<bool>(http://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container), so I'd suggest std::array<bool, N> (maybe std::deque<bool> will also work but it's not parameterized on N) and then try and complete the following list. A standard library container would be preferable to the C-style array you're using at present at memory management would be in-built and you can also use other library facilities:

#include <iostream>
#include <array>

template <size_t N>
class BitArray
{
    public:
        BitArray<N>& Set()
        {
            //implemment from here: http://en.cppreference.com/w/cpp/utility/bitset/set
        }


    private:
        std::array<bool, N> m_container {false};
};

int main()
{

}

[markymark99]

this is what i have,

#include <iostream>
#include "Header.h"

using namespace std;

BitArray::BitArray(unsigned int n)
{
    int size = sizeof(char);
    
    if(n % (8*size) != 0)
    {
        arraySize = ((n / (8 * size)) + 1);
    }
    else
    {
        arraySize = n / (8 * size);
    }
    
    barray = new unsigned char[arraySize];

    for(int i = 0; i < arraySize; i++)
    {
        barray[i] = 0;
    }
}
BitArray::BitArray(const BitArray& )
{
    
}
BitArray::~BitArray()
{
    delete [] barray;
}
unsigned int BitArray::Length() const
{
    return arraySize;
}
void BitArray::Set(unsigned int index)
{
}
void BitArray::Unset(unsigned int index)
{
    
}
void BitArray::Flip(unsigned int index)
{
    barray[index] = ~barray[index];
}

im not having trouble with the header file i just need help defining the class for these functions

[markymark99]

would this be a proper defenition to these functions if I am trying to change the index of the array of bits.

void BitArray::Set(unsigned int index)
{
    barray[index] |= 1 << index;
}
void BitArray::Unset(unsigned int index)
{
    barray[index] &= ~(1 << index);
}
void BitArray::Flip(unsigned int index)
{
    barray[index] = ~barray[index];
}

[mbozzi]

Would this be a proper definition

The actual bitmath is correct, but the indexing isn't. barray is an array of unsigned chars, not of bits. The first CHAR_BIT bits are part of the first element of the array, the second CHAR_BIT bits are part of the second, and so on.

In other words, the nth bit is the (n % CHAR_BIT) part of the char at offset n / CHAR_BIT, allowing for integer division.

Note:
The size of char is always 1. However, the number of bits in a char is not always 8 (8 is the minimum). While you can probably get away with the 8-bit assumption in class, this is not a valid assumption especially on certain embedded platforms. You can get the number of bits in a char by using the macro CHAR_BIT from <climits>.

[markymark99]

im not sure what exactly im supposed to do with that im not allowed to use climit or bitset libraries. Im not sure how Im able to change these bits with just the standard libraries. I also need assistance with the operator<<(ostream& os, const BitArray& a) function. Im supposed to format is the entire array, printed as one continuous sequence of bits, inside parintheses.

[mbozzi]

Here's how you could write the Set() function, assuming 8-bit unsigned char:

barray[index / 8] |= (1 << (index % 8)); 

The same idea is applicable to the other values.

Regarding operator<<, here is an algorithm which converts a single unsigned char (element of barray) into a bitstring:

std::string to_binary(unsigned char const N)
{ return (N == 0): "": (to_binary(N / 2) + (N % 2? "1": "0")); }

[markymark99]

oh alright its running now but I have one more question and ill be out of your hair, along with this program I need to create a seive.h file and use it to list all the prime numbers that are less than the arraySize. here is what I have but its not running:

#include <iostream>
#include "Header.h"

using namespace std;

void Sieve(BitArray& b)
{
    int size = b.Length();
    int arr[] = {0};
    
    for (int i = 2; i < size; i++)
    {
        for (int j = i * i; j < size; j+=i)
        {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < size; i++)
    {
        if (arr[i - 1] == 0)
            cout << i << "\t";
    }
}

[markymark99]

#include <iostream>

using namespace std;

#include "Header.h"

int main()
{
    unsigned int i, max, counter = 0;
    
    cout << "\nEnter a positive integer for the maximum value: ";
    cin >> max;
    
    BitArray ba(max);

    seive(ba);
    
    cout << "The bit array looks like this: \n"
    << ba
    << '\n';
    
    cout << "\nPrimes less than " << max << ':' << '\n';
    for (i = 0; i < max; i++)
    {
        if (ba.Query(i))
        {
            counter++;
            cout << i;
            if (counter % 8 == 0)
            {
                cout << '\n';
                counter = 0;
            }
            else
                cout << '\t';
        }
    }
    
    
    cout << "\nGoodbye!\n";
    return 0;
}

also when the program runs it stops right at line 16 but it wont display the bit in a sequence.