# Bit array implementation

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.

# 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;
public:
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;
}

• The rule of Five seems the reason why when i declare vector<Bitarray1D> i get all sorts runtime errors. Is that true? – k_kaz Jun 2 '17 at 11:12
• Yes. You must either delete the move/copy constructors and assignment operators or else define them correctly. – ruds Jun 2 '17 at 11:22
• "You can avoid needing to check for negative index values by accepting an unsigned integer type in the methods." That's true, but it just shifts the problem around. Thanks to C++'s awful implicit conversion rules, there's nothing stopping the caller from specifying a negative index value. It will just be implicitly converted to an unsigned value using modulo arithmetic, so what you'll end up with is a very large positive number. So now a bug still lurks, and worse, you have no way of ever testing for it! I'd rather just have an assertion that the input is non-negative. – Cody Gray Jun 2 '17 at 13:30
• @Cody - if you have that bug, then the test for > size() will catch it (I've just verified this by changing bits[2] to bits[-2] in the test program). Are you suggesting that there's a platform on which a negative value will become a valid value when converted? – Toby Speight Jun 2 '17 at 13:47
• Oh, no, sorry. It works fine here. I had missed that the size was a small constant here. I was just noting that using unsigned types to avoid checking for negative inputs is not generally a good idea. – Cody Gray Jun 2 '17 at 14:16

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)]);
}


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;
}

• I made some boneheaded arithmetic mistakes that I've fixed thanks to Toby Speight's answer. – ruds Jun 2 '17 at 11:21
• You made a lot of good points while I was testing my replacement code (e.g. with a typedef for the element type, and returning the proxy by value). IF you combine your explanation with my sample code, we're looking good! – Toby Speight Jun 2 '17 at 11:28
• Slight enhancement - your element() and offset() methods can be constexpr, which could help the compiler. – Toby Speight Jun 2 '17 at 11:29
• Both are great answers! – k_kaz Jun 2 '17 at 11:54