Bit array implementation

Question

I have made a bit array implementation that can be seen below:

unsigned int uint_size();

class Bitarray1D {
private:
    unsigned int * array_;
    int elements_;
    int bits_;

public:
    Bitarray1D(int bits);

    ~Bitarray1D();

    void size(int& bits) const;

    unsigned int count() const;

    void setAll(int value);

    void set(int index, int value);

    int test(int index) const;

    unsigned int operator [](int index) const;

    void flip(int index);

    std::string to_string() const;

private:
    void init();

};

and some of the functions:

void Bitarray1D::init(){
        if (bits_ == 0) throw std::invalid_argument("Can't initialize zero size array");

        int number_of_elements = bits_;
        std::cout << "unsigned int size: " << uint_size() << " bytes" << std::endl;

        elements_ = std::ceil((bits_*1.0)/(uint_size()*1.0));
        array_ = new unsigned int[elements_];
}

int Bitarray1D::test(int index) const {
        if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

        int element = index / uint_size();
        int bit = index % uint_size();

        unsigned int temp_element = array_[element];
        temp_element = temp_element >> bit;

        unsigned int mul = 1;
        temp_element = temp_element & mul;
        return temp_element;
}

unsigned int Bitarray1D::operator [] (int index) const {
        if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

        return test(index);
}

uint_size() is a function that returns the size of an unsigned int in bytes.

While this works well, i want to implement the assignment in array-like style as well, i.e.: bitarray[i] = 1;

In the current implementation this is not possible. In order to do so, I figured that [] operator in Bitarray should return a "Bit object" with the appropriate operators like below:

class Bit{
  private:
        unsigned int& element_;
        unsigned int index_;

    int getValue() const{
        // get value of bit
    }
public:
    Bit(unsigned int& element, unsigned int index): element_(element), index_(index){}

    Bit& operator [] (int value){
        return *this;
    }

    Bit& operator = (int value){
          //assign value to the bit
    }

    friend std::ostream& operator<<(std::ostream& os, const Bit& bit){
        os << bit.getValue();
        return os;
    }
};

This implementation works, but has two major problems:

1. Memory leak. In order for the [] operator in Bitarray to return a reference to a Bit object I have to return the following:

   Bit& Bitarray1D::operator [] (int index) const {
        return *(new Bit(..., ... ));
   }
   

2. I could change the array_ of the bitarray to hold an array of class Bit, but then the whole point of the Bitarray is lost, which is smaller memory footprint.

Answer 1

Don't write a function to return a constant

You don't need uint_size(), as the returned value never changes (for a given target platform). You can replace it with

#include <climits>
static const std::size_t uint_bits = CHAR_BIT * sizeof (unsigned int);

Don't require a call to init()

The constructor should fully initialize the object; just move the body of init() there instead.

Use integer operations on integers

Instead of using std::ceil to round up division, we can do this in integer arithmetic by adding one less than the divisor before dividing:

    elements_ = (bits + uint_bits - 1) / uint_bits;

Given that we know the number of bits, we can always compute the number of elements when we need it; you might consider the trade-off between storing and computing elements_.

Obey the Rule of Five (or Rule of Zero)

You allocate memory in the constructor, but don't provide copy/move constructors, nor an assignment operator, so you run the risk of double delete[]. The easiest fix is to use a standard container as the storage; you might also consider using a smart pointer to the storage. As a last resort, you could manage the memory yourself, but I'd advise against that.

Use an unsigned type for indexing

You can avoid needing to check for negative index values by accepting an unsigned integer type in the methods. I recommend std::size_t as the standard type usually used for that.

Return by value when possible

void size(int& bits) const;

is better written as

std::size_t size() const;

---

My version

Working replacement code:

#include <climits>
#include <stdexcept>
#include <vector>

class Bitarray1D {
    using Element = unsigned int;

    class Bit {
        Element& element;
        const Element mask;
    public:
        Bit(Element& element, Element mask) : element{element}, mask{mask} {}
        Bit(const Bit& other) : Bit{other.element, other.mask} {}
        operator bool() const { return element & mask; }
        Bit& operator=(bool b) { element = b ? element | mask : element & ~mask; return *this; }
        Bit& operator=(const Bit& other) { return this->operator=(bool(other)); }
    };

    static const std::size_t element_bits = CHAR_BIT * sizeof (Element);

    std::size_t bits;
    std::vector<Element> array;

public:
    Bitarray1D(std::size_t bits);
    ~Bitarray1D() = default;

    std::size_t size() const;

    Bit operator[](std::size_t index);

};

Bitarray1D::Bitarray1D(std::size_t bits)
    : bits{bits},
      array{}
{
    // rounded-up division
    array.resize((bits + element_bits - 1) / element_bits);
}

Bitarray1D::Bit Bitarray1D::operator[](std::size_t index) {
        if (index >= bits)
            throw std::out_of_range("Index out of range");
        return Bit(array[index / element_bits], 1u << (index % element_bits));
}


int main()
{
    Bitarray1D bits{15};
    bits[0] = 0;
    bits[2] = bits[1] = 1;
    return bits[0] + bits[1] + bits[2] != 2;
}

Answer 2

I have a number of comments, so I'll just sort of spray them out.

---

Using a proxy reference type is tricky, and can lead to some interesting problems. For example, a class that provides proxy references (e.g. vector<bool> cannot meet the standard's requirements for a container (see http://www.gotw.ca/publications/mill09.htm). It also makes the use of auto dangerous:

Bitarray1D arr(1);
arr.set(0, 0);
const auto this_isnt_really_a_bool = arr[0];
arr.set(0, 1);
assert(!this_isnt_really_a_bool);  // fails

However, if you plan to use a proxy reference, you should return it by value, not by reference:

Bit Bittarray1D::operator[](int index) const {
    return Bit(array_[element(index)], offset(index)]);
}

This solves your memory leak.

---

Why do you use int throughout as the type of a bit? What would you do if someone called set with value == 2? Would you accidentally set the next higher bit (and have undefined behavior if that were already the highest bit in an element)? C++ has a type that takes on the same values as a bit: bool.

Likewise, you use multiple types to represent a size (you pass int to the constructor and as bits_ and elements_ members, you return unsigned int from count). Use std::size_t; it's designed for this purpose.

---

uint_size is not such a good idea. Compilers will likely omit optimizations, and experience readers will be confused by the use of a function. Instead, define a constant:

constexpr std::size_t uint_size = sizeof(unsigned) * CHAR_BITS;

(some people would name this kUintSize or UINT_SIZE or similar. In any case, this need not be defined in the header.

By the by, I wouldn't necessarily commit to using unsigned as your representation type. If you use a typedef, you can profile to determine which type maximizes performance.

using Repr = unsigned;
// using Repr = std::uint64_t;
// using Repr = unsigned char;

---

You presumably have the following lines in each member function that takes an index argument:

    if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

    int element = index / uint_size();
    int bit = index % uint_size();

Why not add a couple of private functions that take care of this:

std::size_t element(std::size_t index) const {
    if (index >= bits_) throw std::out_of_range("Index out of range");
    return index / REPR_BITS;
}
std::size_t offset(std::size_t index) const {
    return index % REPR_BITS;
}

---

You keep both elements_ and bits_, but you do not allow users to resize the array, and elements_ doesn't seem to be used anywhere. Omit elements_.

---

Why does init exist? You only have one constructor, and even if you added others, you could delegate.

I've recommended that you eliminate elements_, but if you choose not to, please initialize it differently. Using floating point in this way is dangerous. Instead, initialize it like so:

elements_ = (bits_ + REPR_BITS - 1) / REPR_BITS;

Here's what your constructor should look like.

Bitarray1D::Bitarray1D(std::size_t bits) 
    : array_(new Repr[(bits + REPR_BITS - 1) / REPR_BITS]()),
      bits_(bits) {}

Note that my code, unlike yours, initializes the array to 0 (new int[5]() value-initializes, new int[5] does not).

---

Your implementation of test has a lot going on; here's a simpler implementation:

bool Bitarray1D::test(std::size_t index) const {
    return (array_[element(index)] >> offset(index)) & 1u;
}