5
\$\begingroup\$

I have currently implemented an increment method. A method to add bytes. And a method to print out the bitset.   Main.cpp

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

int main()
{
DynamicBitset bitset;

unsigned char count = 97;

bitset.addByte(count);
bitset++;

bitset.printArray();

return 0;
}

DynamicBitset.h

#pragma once
#include <cstring>
#include <iostream>

class DynamicBitset
{
private:
    unsigned char* array;
    unsigned int arrayLength;
    unsigned int bitLength;

public:
    //Constructors
    DynamicBitset();
    DynamicBitset(unsigned int bitLength);
    //Deconstructor
    ~DynamicBitset();

    //function to add a byte to the bitset
    void addByte(unsigned char byte);
    void zeroOutArray();
    void zeroUpTo(unsigned int bitIndex);
    //DynamicBitset& operator++();
    void operator++(int);

    void printArray();
    };

DynamicBitset.cpp

#include "DynamicBitset.h"

DynamicBitset::DynamicBitset()
{
        this->array = nullptr;
        this->arrayLength = 0;
        this->bitLength = 0;
}

DynamicBitset::DynamicBitset(unsigned int bitLength)
{
    if (bitLength % 8 == 0)
    {
        this->arrayLength == bitLength / 8;
        this->array = new unsigned char[this->arrayLength];
        this->bitLength = bitLength;
    }
    else if (bitLength % 8 > 0)
    {
        this->arrayLength = (int)(bitLength / 8) + 1;
        this->array = new unsigned char[this->arrayLength];
        this->bitLength = bitLength;
    }
    else
    {
        this->arrayLength = 0;
        this->array = nullptr;
        this->bitLength = 0;
    }
}

DynamicBitset::~DynamicBitset()
{
    delete[] this->array;
}

void DynamicBitset::addByte(unsigned char byte)
{
    unsigned char* tempArray = new unsigned char[this->arrayLength + 1];
    memcpy(tempArray, this->array, this->arrayLength);
    tempArray[this->arrayLength] = byte;
    delete[] this->array;
    this->array = tempArray;
    this->arrayLength++;
    this->bitLength += 8;
}

void DynamicBitset::zeroOutArray()
{
    for(int i = 0; i < this->arrayLength; i++)
    {
        this->array[i] = 0;
    }
}

void DynamicBitset::zeroUpTo(unsigned int bitIndex)
{
    unsigned int subArrayLength = (unsigned int)(bitIndex / 8);
    unsigned int lastCharBitIndex = bitIndex - (subArrayLength * 8);
    unsigned char powerMask = 1;
    unsigned char bitMask = (powerMask << lastCharBitIndex) - 1;

    bitMask = ~bitMask;

    this->array[subArrayLength] &= bitMask;
    
    for(int i = 0; i < subArrayLength; i++)
    {
        this->array[i] = 0;
    }
    
}

void DynamicBitset::operator++(int)
{
    unsigned int byteCount = 0;
    unsigned int shiftAmount = 0;
    unsigned int bitIndex = 0;

    while (((this->array[byteCount] >> shiftAmount) & 1) != 0)
    {
        shiftAmount++;
        bitIndex++;
        if (shiftAmount % 8 == 0)
        {
            byteCount = bitIndex / 8;
            shiftAmount = 0;
        }

        if ((byteCount >= this->arrayLength) && bitIndex == this->arrayLength * 8)
        {
            this->zeroOutArray();
            std::cout << "This Ran!" << std::endl;
            this->addByte(1);
            return;
        }

    }

    unsigned int subArrayLength = (unsigned int)(bitIndex / 8);
    unsigned int lastCharBitIndex = bitIndex - (subArrayLength * 8);
    unsigned char powerMask = 1;

    this->zeroUpTo(bitIndex);

    this->array[subArrayLength] += (powerMask << lastCharBitIndex);
}

/*
DynamicBitset& DynamicBitset::operator++()
{
    return *this;
}
*/

void DynamicBitset::printArray()
{
    for (int i = 0; i < this->arrayLength; i++)
    {
        std::cout << (int) this->array[i] << ", ";
    }
}

For anyone who wants to see the current progress of the project here is the github repository: https://github.com/ChristianDoesCode/DynamicBitset.git

\$\endgroup\$
6
  • 5
    \$\begingroup\$ Could you add some explanation of what this class provides, that's not in std::vector<bool>? That would help reviewers understand the motivation. Also, is 8 an assumption of CHAR_BIT? IF so, that's a problem on platforms where those values differ. \$\endgroup\$ Feb 1 at 15:22
  • \$\begingroup\$ I could have used the vector bool but this project was more designed to learn. So I was trying to see what it would be like creating a dynamic bitset. \$\endgroup\$ Feb 1 at 17:03
  • \$\begingroup\$ What operator+ is supposed to do? \$\endgroup\$
    – coderodde
    Feb 1 at 17:30
  • \$\begingroup\$ Its for making a way to calculate a binary key for my compression algorithm. \$\endgroup\$ Feb 1 at 20:12
  • \$\begingroup\$ If I have analyzed these suggestions correctly I need to implement the following. 1. A way to handle the size of datatypes on multiple platforms. 2. A way to copy the object and copy the memory efficiently. 3. A way to dynamically increase and decrease the array efficiently. 4. documentation 5. use better data types 6. And get rid of unnecessary checks and operations that may hinder performance or are just a inconvenience. \$\endgroup\$ Feb 2 at 2:38

3 Answers 3

6
\$\begingroup\$

Use namespaces

DynamicBitset might be a sufficiently unique name, but if you put it inside a namespace, you're much less likely to collide with some other class from some library you import.

Default constructor

I recommend that you set default values in the class definition, then default the default constructor:

class DynamicBitset
{
private:
    unsigned char* array = nullptr;
    unsigned int arrayLength = 0;
    unsigned int bitLength = 0;

public:
    //Constructors
    DynamicBitset() = default;
//...

DynamicBitset::DynamicBitset(unsigned int bitLength)

This function looks at three cases: the first two (bitLength % 8 == 0 and bitLength % 8 > 0) cover all possible cases, the third one will never happen.

The first two cases do the same thing, but compute the array length slightly differently. This is unnecessary, it is possible to compute the array length correctly for all cases as follows:

DynamicBitset::DynamicBitset(unsigned int bitLength)
{
    arrayLength = (bitLength + 7) / 8;
    array = new unsigned char[this->arrayLength];
    bitLength = bitLength;
}

(By the way, you had a bug there: this->arrayLength == bitLength / 8 should have used assignment, =, not equality comparison. Turn on all compiler warnings and pay attention to them, your compiler should be able to warn you about typos like this.)

this->

You don't need to say this->array, unless there's another array defined locally that would hide the class definition. array by itself is sufficient.

memcpy

This is a C function, it's been imported into the C++ standard for convenience, but it is best to use actual C++ functions, as they're type safe. Functions such as memcpy will do lots of damage if the memory pointed to is filled with objects that have a constructor or a destructor. Instead do std::copy_n(array, arrayLength, tempArray).

Use the standard library

For example, in void zeroOutArray() you have a loop, instead you can use std::fill or std::fill_n:

void DynamicBitset::zeroOutArray()
{
    std::fill_n(array, arrayLength, 0);
}

This is not only faster to type and easier to read (and thus maintain), but potentially also more efficient.

operator++(int)

This operator should return the value of the operand before increment. It is typically implemented as:

DynamicBitset DynamicBitset::operator++(int) {
    DynamicBitset tmp = *this;  // make a copy
    operator++();               // increment object using other overload
    return tmp;                 // return the copy
}

This implementation would then be based on operator++(), the prefix increment, which must return a reference to the object itself:

DynamicBitset& DynamicBitset::operator++() {
    // Implement increment here...
    return *this;
}

I recommend that you look at a reference like cppreference.com when overloading standard operators, to see if you have the right function signature.

Don't use std::endl

std::endl not only outputs a newline, it also flushes the output buffer. This can cause significant delays, and is typically unnecessary. Just output the '\n' character instead: std::cout << "This Ran!\n";

Console output

Instead of DynamicBitset::printArray(), consider overloading the << operator:

friend std::ostream& operator<< (std::ostream& stream, const DynamicBitset& bitSet) {
    for (int i = 0; i < bitSet->arrayLength; i++)
    {
        stream << (int) bitSet->array[i] << ", ";
    }
}

This is much more flexible, as you can now write the bit set contents to a file or to a string (using stingstream).

Documentation

I suggest you add comments to your header file explaining what every class and function does. This might be clear to you now, but it is not clear to us, and might not be clear to you in a year's time.

What's the purpose?

You can add elements to your bit set, increment it, and zero it. But you can't get any of the data out, except for printing it to the console! It seems to me that this makes the class quite useless... I assume it's work in progress?

\$\endgroup\$
7
  • \$\begingroup\$ Thank you for all the suggestions! This is a work and progress and in my most recent version I made today I added a way to get individual bit values by overload the [] operator. Also the return on the increment operator is causing me problems I'm still trying to work out. I think it's a problem with dereferencing the this reference. That's why I'm returning void \$\endgroup\$ Feb 1 at 22:12
  • \$\begingroup\$ @ChristianPhillips You need to return a reference, then return *this should always work. What I do notice now is that you don't have a copy constructor nor copy assignment, so DynamicBitset tmp = *this will not compile. Because you have a destructor, there should be no default copy constructor and assignment created for you, you need to do this explicitly. And that's a good thing because otherwise you'd end up with two objects sharing a pointer to the same array... While you're at it, also write a move constructor and move assignment. \$\endgroup\$ Feb 1 at 22:21
  • \$\begingroup\$ Do you think you can link me some resources to learn how to do this. I am new to c++ so I don't know how to implement this but it seems like it will solve my problem. \$\endgroup\$ Feb 2 at 2:21
  • 1
    \$\begingroup\$ You recommend not to use this-> if it's not necessary. I personally like to always add this-> to make a clear distinction between local variables and class properties. Do you have a good reason for not to use this-> except for less chars to type? \$\endgroup\$ Feb 2 at 6:43
  • 1
    \$\begingroup\$ @Green绿色 Explicit is good, but redundant is not. So this one is a toss up really. But I think it’s clearer without. If your function body is just std::fill_n(array, arrayLength, 0);, where else are those variables coming from? \$\endgroup\$ Feb 2 at 15:52
8
\$\begingroup\$

Advice 1 - std::size_t for indexing and counting

Instead of the following:

unsigned int arrayLength;
unsigned int bitLength;

I suggest you do instead:

#include <cstdlib>
...
std::size_t arrayLength;
std::size_t bitLength;

Advice 2 - zeroUpTo

I guess you could use memset to set some entries to zero. It is likely to be faster than a bare for loop. (Same applies to zeroOutArray.)

Advice 3 - performance issue

addByte(unsigned char) is a show stopper. You do \$\Theta(n)\$ effort everytime you add a single (!) element. You could do it in \$\Theta(1)\$ amortized time if you multiply the internal array to \$qn\$, where \$q > 1\$ is the expansion factor, when there is no more room for a new element. (\$q = 2\$ is a good choice.) You can read about this issue on my Wordpress weblog.

\$\endgroup\$
11
  • \$\begingroup\$ I have see that the vector does a very similar thing by increasing the size of the array by two times the current length. But the reason I did not do this is because lets say I put in 10 million bytes than I wanted to increase it by 1 million more bytes I believe this would increases the size of the array by 2^1000000 in size which would overwhelm my memory. Although this was just my thought process I probably am wrong. \$\endgroup\$ Feb 1 at 17:09
  • 1
    \$\begingroup\$ @ChristianPhillips No. You won’t increase it by 2^1000… The size will grow from 10_000_000 to 20_000_000. \$\endgroup\$
    – coderodde
    Feb 1 at 17:27
  • 2
    \$\begingroup\$ memset is not a good recommendation. Better use functions in the C++ standard library. std::fill would be more appropriate. \$\endgroup\$ Feb 1 at 20:42
  • 1
    \$\begingroup\$ @ChristianPhillips Doubling of the array size is the standard solution used about everywhere. You can choose a different factor, if you have some good reason to do so, but as a novice I wouldn’t second-guess established rules of thumb. \$\endgroup\$ Feb 1 at 20:46
  • 1
    \$\begingroup\$ @ChristianPhillips Now we get into the nitty-gritty detail of how modern OSes work, but if you allocate a large chunk of memory and don’t use it, that memory will not actually be mapped to your physical memory. So allocating an array that is way too large for what you need is not a problem, not even if it’s larger than your physical memory. See this answer for all the details. This means that putting in effort to reduce the size of your increments when reallocating is not really useful, and you will only see worse performance, not better. \$\endgroup\$ Feb 2 at 16:09
4
\$\begingroup\$

operator++ increments the whole thing as a BigInt? It's incredibly inefficient to do this one bit at a time; you're running on a CPU with ALUs that can propagate carry through an unsigned long in a single cycle (typically 32 or 64 bits wide)

Also since you're just adding 1 and taking advantage of how that clears consecutive set low bits, you could be looping on array[i]++ == 0xff (or UCHAR_MAX to avoid assuming CHAR_BIT == 8).

See also On vector<bool> -- Howard Hinnant - bad name for a useful data structure. As he points out, a good implementation can have specializations for std::find, std::fill, std::rotate, and other algorithms that take advantage of having multiple bits packed into each element, instead of that being a hindrance. e.g. loop until you find the first non-zero or not-all-ones chunk and then std::countr_zero on that, instead of only checking one bit at a time. If you're going to implement your own dynamic bit array, read that article first.

You are taking advantage of this idea with zeroUpTo: you mask the top chunk and just zero-fill the lower ones.


There's no portable way to find the widest one-register integer type. uint_fast32_t is 64 bits in glibc on all 64-bit platforms including x86-64, which is bad for many use-cases but good for this. But other more sane libraries like MUSL make different choices, and IDK what MSVC on Windows does. size_t or uintptr_t are most often full-width, but 64-bit ILP32 ABIs have narrower pointers (32-bit pointers on 64-bit systems, like AArch64 ILP32 and x86-64 Linux's x32).

In this case it's probably fine to make the compiler work in chunks of 2 registers on 32-bit machines by using uint64_t* array; or unsigned long long. https://stackoverflow.com/questions/4153852/assembly-adc-add-with-carry-to-c/75759422#75759422 shows portable C++ that some compilers (maybe just Clang) can compile to a chain of adc (add-with-carry) instructions.

But like I said, for just adding 1 and then propagating carry, this really amounts to searching for the first 0 bit and setting it, and clearing below it. But fortunately the "bithack" for doing that is just binary addition :P
This can be done one uint_fast64_t at a time with for (size_t i=0 ; ... ; i++) { if (array[i]++ != -1ULL) break; } with the loop logic detecting when you reach the end of the array and need to allocate more space.

Compilers won't auto-vectorize this search because the iteration count isn't calculable before the first iteration; if it's common for there to be more than 128 or 256 contiguous 1 bits at the bottom of your bitset, you'd want the compiler to be using SSE2 or AVX2 (if compiling for x86) to search for the first 32-byte chunk that isn't all-ones. So you could manually vectorize this with intrinsics, but it wouldn't be a win if carry propagation usually ends within the lowest uint_fast64_t, like for uniformly random numbers. https://stackoverflow.com/questions/67605508/efficiently-find-least-significant-set-bit-in-a-large-array/67779725#67779725 - finding the lowest clear bit is basically equivalent.


C++ makes it annoying (compared to assembly language) to access the same bytes in memory with different element widths, although unsigned char * is allowed to alias anything so it's fairly easy to mix a wide size like uint_fast64_t with unsigned char accesses.

This lets you to set/clear/toggle single bits by just modifying the containing byte instead of the whole 64-bit chunk. So setting nearby bits is more likely to be two independent load/modify/store ops on separate bytes rather than one dependent chain of modifying the same aligned 64-bit chunk of memory twice.

e.g. for a Sieve of Eratosthenes, looping with small strides to clear every 3rd or 5th bit will do a lot of accesses in a row to the same 64-bit chunk if you use too large a chunk size, creating longer dependency chains than out-of-order exec can hide, especially if your bitset factors out even numbers. This is something most std::vector<bool> and std::bitset<N> implementations do badly, only using unsigned long chunks. See my comments on Sieve of Eratosthenes in x86 assembly for performance results for hand-written asm for that.

(One advantage to only using wide accesses is that you avoid store-forwarding stalls, which would happen when reloading the word containing a recently-stored byte that's still in the store buffer and hasn't committed to cache yet. On Intel CPUs, perf event ld_blocks.store_forward.)


For example

class DynamicBitset
{
private:
    uint_fast64_t* array;
    size_t arrayLength;  // # of allocated uint_fast64_t chunks
    size_t bitLength;    // position of highest set bit?
   // or no, I think this is just in-use size
   // like how std::vector is normally implemented with size and capacity members.

...
};
#include <limits>
//#include <bit>       // C++20 std::countl_zero

// Let's just implement the pre-increment version so we can return the modified bitset
// Treating the whole Bitset as a BigInteger, increment by one
DynamicBitset& DynamicBitset::operator++()
{
    const auto bits_per_chunk = std::numeric_limits< decltype(this->array[0]) >::digits;

    for (size_t i = 0 ; i < this->arrayLength ; i++) {
        // -1L sign-extends to whatever width uint_fast64_t actually is, and converts to an unsigned value with all bits set
        // unless -1L is wider than uint_fast64_t in which case it has too many bits set.  I could have written uint_fast64_t(0) - 1U
        if (array[i]++ != -1L) {
            // the element wasn't all-ones before we incremented it, so it didn't wrap
            // carry propagation ended here
            // update highest-set-bit position if it might have increased
            if (i >= this->bitLength / bits_per_chunk){
               // this is the chunk at or above the one holding the previous MSB, if I got this right

               // the bit-index of the bit past the end of array[i]
               this->bitLength = i * bits_per_chunk;
               // MSB_position = i * bits_per_chunk - std::countr_zero(array[i]);
               return *this;
            }
        }
    }

   // if we haven't already returned, the allocated space was all 1 bits
   // We have to reallocate, all zeros except for a new high element
   size_t old_len = this->arrayLength;

  // free the old *then* allocate new zeroed memory since we don't need to copy anything
   delete[] this->array;
   this->arrayLength *= 2;  // growth factor
   this->array = new uint_fast64_t [this->arrayLength];
 // maybe consider std::vector<uint_fast64_t> for the storage?
 // Unless you really want bitLength to be counted in bits

  // C++ lacks calloc and realloc so we were forced to delete/new and can't get pre-zeroed memory perhaps from the kernel.
   std::fill_n(this->array, this->arrayLength, 0);


   this->array[old_len+1] = 1;  // carry propagation into the next element

   return *this;
}

I've kept your this->member style choice. It's unconventional style, but does help remind distinguish instance members from local variables.

You'd normally want to factor reallocation out into a separate function, but operator++ is a special case because we only need to grow in one case of existing contents that results in all-zero in the existing space. This isn't the cleanest code, a bit cluttered with comments. Also untested, but I hope it gets the idea across.

\$\endgroup\$
4
  • \$\begingroup\$ Your response seemed very good but it was kind of hard for me to follow. \$\endgroup\$ Feb 2 at 2:19
  • \$\begingroup\$ If I have analyzed these suggestions correctly I need to implement the following. 1. A way to handle the size of datatypes on multiple platforms. 2. A way to copy the object and copy the memory efficiently. 3. A way to dynamically increase and decrease the array efficiently. 4. documentation 5. use better data types 6. And get rid of unnecessary checks and operations that may hinder performance or are just a inconvenience. \$\endgroup\$ Feb 2 at 2:38
  • \$\begingroup\$ @ChristianPhillips: I added an example implementation of operator++() for uint_fast64_t chunks, which I think is at least a viable idea. I haven't tested it, there could be off-by-one errors in some of the conditions. \$\endgroup\$ Feb 2 at 3:09
  • \$\begingroup\$ Ok thank you I will test it. \$\endgroup\$ Feb 2 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.