C++ - BitVector logic

Question

I have implemented a simple bit vector class. However, I have some problems with understanding, how to push data to it.

In a standard vector, push_back inserts new element et the end. A similar logic can be implemented for single bit.

However, I want to append number with a given precision. For example:

13 => 4bits (1101)
54 => 6bits (11 0110)
522 => 10bits (10 0000 1010)

Starting with a bit vector with bits:

x x x

I can append it from highest bit (left to right), so for eg. 54@6bits I got

x x x 11 0110

or I can append it from lowest bit (right to left), so for eg. 54@6bits I got

x x x 0110 11

For me, the first option seems more logical.

However, when I add aligned numbers 522@16bits I end up with for left to right

x x x 0000 0010 0000 1010

or from right to left

x x x 0101 0000 0100 0000

However, in this case (right to left), when I later wants to read data to memory, they are incorrect because of Endian. How to solve this logic?

I want to be able to append numbers with selected bits precision, and later copy them from memory to variables.

Currently, I have solved this as:

template <typename T>
void BitVector::Append(T number, Endian e){
    if (e == BitVector::Endian::Big){
        this->Append(number, sizeof(T));
    }
    else {
        uint8_t tmp[sizeof(T)];
        memcpy(tmp, &number, sizeof(T));

        for (size_t i = 0; i < sizeof(T); i++){
            this->Append(tmp[i], 8);
        }
    }
}

and

void BitVector::Append(uint64_t number, uint32_t bitSize){
    for (long i = long(bitSize - 1); i >= 0; i--){
        this->push_back((number >> i) & 1);
    }
}

Templated Append with Little endian should correspond to setting elements of array.

BitVector bb;

bb.Append<uint16_t>(160, BitVector::Endian::Little);
bb.Append<uint16_t>(39, BitVector::Endian::Little);

uint16_t tmp[2];
tmp[0] = 160;
tmp[1] = 39;

uint8_t res[4];
memcpy(res, tmp, 4);

res and internal data of bit vector now contains the same data.

However, I am not sure if this is the most readable way.

Maybe better on Code Review? – D. Ben Knoble Aug 09 '19 at 21:22 — D. Ben Knoble, Aug 09 '19 at 21:22

score 2 · Answer 1 · answered Aug 09 '19 at 17:50

There is no correct answer here. Your memcpy() code reinterprets bit patterns using the machine's endianess, and exercises undefined behaviour. For your bit vector, you can decide whether you enforce a specific endianess, or whether you stick the machine default. Neither approach is correct, this just depends on how you want to use the bit vector.

In general, the concept of extending a bit vector with an integer seems kind of questionable. It is also extremely weird that you want to ignore unset more-significant bits (like your example indicates, although your Append() implementation doesn't do this).

If you're implementing the bit vector out of necessity rather than interest, investigate whether std::vector<bool> wouldn't satisfy your requirements. It is specified in such a way that it can be implemented as a bit vector.

Thank you, I know about my memcpy, it is targeted for x86 platforms, so I expect Little endian. I am porting some code and I need real bit manipulation vector. Appending integers is more-or-less a helper method so I dont have to add them by bits manually. — Martin Perry, Aug 09 '19 at 18:27

score 1 · Answer 2 · answered Aug 09 '19 at 21:02

You are implementing an array of bits. Bit positions are numbered from 0 upwards. There is no endianess involved at all.

Now you have decide what bits you want to be set if you add say the number 4 as a 3 bit number. If your vector already contains 79 bits, then you add bits number 79, 80 and 81. It would make most sense if you add bit 0, 1 and 2 of the number 4 (0, 0 and 1) in that order.

I’d recommend you implement everything using 64 bit unsigned integers as backing store, and using shift operations to put everything in the right place.

One mistake you made in your drawing: you drew the bits in your array from left to right, as we usually do, but the bits in your numbers from right to left. That’s probably the source of s lot of confusion.

C++ - BitVector logic

2 Answers2