C++ data type to store and manipulate individual bits
$begingroup$
The use cases I’m facing require me to have a C++ data type that can store and manipulate the state of somewhere between 400 and 500 bits. In addition it is necessary to be able to store that state within SQL server databases in an efficient manner, i.e. not wasting unnecessary space because there will be a lot of such database records eventually.
I had a look at std::bitset
which is capable of storing that amount of bits but lacks the capability to export its internal state in an efficient way. It offers to_ulong
and to_ullong
which both are too small to store up to 500 bits and to_string
which would result in a string of 500 characters, i.e. one character per bit which seems rather inefficient.
I figured I could pack all bits that I require into a byte array that I could store in the SQL database as a blob and hence use eight times less space compared to storing them as a 500 character string.
First I tried to turn the output of std::bitset
into a byte array but realized that the logic required to do so might as well be turned into its own class that directly operates with a byte array.
The class that I’m posting here is the result of that approach. Its interface is inspired by std::bitset
but deviates in some cases and does not offer all functionality that std::bitset
does, simply because I have no use for that functionality.
It does provide read-only access to the array that stores the bits and offers creating an object from such an array so that I can store to and load the state from the database.
The class is designed to be compiled with C++14 but I will migrate my code base to C++17 within a few months.
When reviewing, could you please consider commenting on the following topics?
- Currently, there is no overloaded
=
operator, only a copy constructor. For this particular case, is overloading=
necessary / does make sense? - Given that I switch to C++17: Are there any parts of the code that could be simplified using C++17?
- I’m unsure how to overload the
operator so that it can be used to set/get individual bits. I assume I'll need some kind of proxy object but I'm unsure how best to do it. Hints on how to do this would be appreciated.
- I use
#pragma once
instead of the more traditional include guards because the compilers (Clang and Microsoft Visual C++) on all platforms that I build for (Android, iOS, Windows) support it. I’m unaware of any downsides of using it. Any comments regarding this? - I’m covering the class using the unit tests that I posted. They are built on top of Microsoft’s CppUnitTestFramework that ships together with Visual Studio. Comments regarding those tests are highly appreciated.
- The method to access individual bits is named
get
while the corresponding method ofstd::bitset
is namedtest
. I usedget
as name because “it just makes more sense to me thantest
”. You might consider this to be a drawback because the class cannot be used as a drop-in replacement forstd::bitset
that way. However, as mentioned not all functionality is provided anyway (<<
,>>
,operators are missing, etc.). Comments regarding this?
The class:
#pragma once
#include <array>
namespace common
{
template<std::size_t bit_count>
class bitpattern
{
public:
static constexpr std::size_t BitCount = bit_count;
static constexpr std::size_t ByteCount = (bit_count % CHAR_BIT) ? (bit_count / CHAR_BIT) + 1 : (bit_count / CHAR_BIT);
bitpattern()
{
}
// The string that is passed to this method is read from right to left, i.e.
// the last character on the right end of the string is turned into the bit
// at index 0.
bitpattern(const std::string bits)
{
std::size_t character_count = (bits.length() > bit_count) ? bit_count : bits.length();
std::size_t first_character = bits.length() - 1;
for(std::size_t i = 0; i < character_count; i++)
{
switch(bits[first_character - i])
{
case '0': continue;
case '1': set(i); break;
default : throw std::invalid_argument("Argument string contains characters other than '0' and '1'.");
}
}
}
bitpattern(const std::array<uint8_t, ByteCount> bits)
{
_bit_container = bits;
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits are 0
}
bitpattern(const bitpattern<bit_count>& pattern)
{
_bit_container = pattern._bit_container;
}
bitpattern<bit_count>& flip()
{
for(uint8_t& byte : _bit_container)
{
byte = ~byte;
}
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return *this;
}
bitpattern<bit_count>& flip(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] ^= (1u << (index % CHAR_BIT));
return *this;
}
bool get(std::size_t index) const
{
_throw_if_too_large(index);
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
bitpattern<bit_count>& set(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] |= (1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] &= ~(1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset()
{
_bit_container.fill(0);
return *this;
}
bool all() const
{
std::size_t i = 0;
for(; i < (ByteCount - 1); i++)
{
if(_bit_container[i] != 0b1111'1111)
{
return false;
}
}
// The last byte is treated separately because it could contain
// padding bits that are 0.
return _bit_container[i] == _padding_bit_mask;
}
bool any() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return true;
}
}
return false;
}
bool none() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return false;
}
}
return true;
}
std::size_t count() const
{
std::size_t count = 0;
for(uint8_t byte : _bit_container)
{
// Implementation of the Hamming Weight algorithm for 8-bit numbers.
// See https://en.wikipedia.org/wiki/Hamming_weight
// and https://stackoverflow.com/a/30692782/5548098
byte = byte - ((byte >> 1) & 0b0101'0101);
byte = (byte & 0b0011'0011) + ((byte >> 2) & 0b0011'0011);
count += ((byte + (byte >> 4)) & 0b0000'1111);
}
return count;
}
bool operator==(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] != right._bit_container[i])
{
return false;
}
}
return true;
}
bool operator!=(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] == right._bit_container[i])
{
return false;
}
}
return true;
}
bitpattern<bit_count>& operator&=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] &= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator|=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] |= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator^=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] ^= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count> operator&(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] & right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator|(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] | right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator^(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] ^ right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator~()
{
bitpattern<bit_count> inverted_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
inverted_pattern._bit_container[i] = ~_bit_container[i];
}
inverted_pattern._bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return inverted_pattern;
}
// Note that the string generated by this method must be read from
// right to left, i.e. the bit with index 0 is to be found at the
// right end of the string. The approach is taken from numbers where
// the least significant number is found at the right end.
std::string to_string() const
{
std::string pattern;
pattern.reserve(bit_count);
for(int i = (bit_count - 1); i >= 0; i--)
{
pattern.append(get(i) ? "1" : "0");
}
return pattern;
}
const std::array<uint8_t, ByteCount>& array() const
{
return _bit_container;
}
private:
void _throw_if_too_large(std::size_t index) const
{
if(index >= bit_count)
{
throw std::out_of_range("Index is too large.");
}
}
static constexpr uint8_t _create_padding_bit_mask()
{
uint8_t count = bit_count % CHAR_BIT;
uint8_t bit_mask = 0b1111'1111;
if(count)
{
for(int i = (CHAR_BIT - 1); i >= count; i--)
{
bit_mask ^= (1 << i);
}
}
return bit_mask;
}
static constexpr uint8_t _padding_bit_mask = _create_padding_bit_mask();
std::array<uint8_t, ByteCount> _bit_container{};
};
}
Associated unit tests:
#include "CppUnitTest.h"
#include "../bitpattern/bitpattern.h"
#include <map>
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace common
{
TEST_CLASS(bitpatterntests)
{
public:
TEST_METHOD(ConstructionZeroInitializesArray)
{
bitpattern<69> pattern;
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooLarge)
{
std::string bits = "10101110100011010101011100101";
bitpattern<14> pattern_from_string(bits);
bitpattern<14> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(2).set(5).set(6).set(7).set(9).set(11).set(13));
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooSmall)
{
std::string bits = "101001110101010";
bitpattern<28> pattern_from_string(bits);
bitpattern<28> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(1).set(3).set(5).set(7).set(8).set(9).set(12).set(14));
}
TEST_METHOD(ConstructionFromStringWorksWithStringOfSameLength)
{
std::string bits = "001000110011010001011";
bitpattern<21> pattern_from_string(bits);
bitpattern<21> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(1).set(3).set(7).set(9).set(10).set(13).set(14).set(18));
}
TEST_METHOD(ConstructionFromEmptyStringZeroInitializesArray)
{
std::string bits = "";
bitpattern<13> pattern(bits);
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringContainingCharactersOtherThanOneAndZeroThrowsException)
{
std::string bits = "01010A0102";
auto func = [bits] { bitpattern<29> pattern(bits); };
Assert::ExpectException<std::invalid_argument>(func);
}
TEST_METHOD(ConstructionFromArrayZeros1PaddingBits)
{
bitpattern<7> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0111'1111);
}
TEST_METHOD(ConstructionFromArrayZeros2PaddingBits)
{
bitpattern<6> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0011'1111);
}
TEST_METHOD(ConstructionFromArrayZeros3PaddingBits)
{
bitpattern<5> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0001'1111);
}
TEST_METHOD(ConstructionFromArrayZeros4PaddingBits)
{
bitpattern<4> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'1111);
}
TEST_METHOD(ConstructionFromArrayZeros5PaddingBits)
{
bitpattern<3> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0111);
}
TEST_METHOD(ConstructionFromArrayZeros6PaddingBits)
{
bitpattern<2> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0011);
}
TEST_METHOD(ConstructionFromArrayZeros7PaddingBits)
{
bitpattern<1> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0001);
}
TEST_METHOD(CopyConstructedObjectIsEqualToOriginalObject)
{
bitpattern<34> pattern;
bitpattern<34> pattern_copied(pattern);
Assert::IsTrue(pattern == pattern_copied);
}
TEST_METHOD(FlipInvertsAllBitsExceptPaddingBits)
{
std::array<uint8_t, 4> input = { 0b0011'1010, 0b1111'1011, 0b0001'1011, 0b0110'1010 };
std::array<uint8_t, 4> expected_output = { 0b1100'0101, 0b0000'0100, 0b1110'0100, 0b0000'0101 };
bitpattern<27> pattern(input);
pattern.flip();
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsAllBitsIfThereAreNoPaddingBits)
{
std::array<uint8_t, 3> input = { 0b1010'0110, 0b1111'1111, 0b0110'1001 };
std::array<uint8_t, 3> expected_output = { 0b0101'1001, 0b0000'0000, 0b1001'0110 };
bitpattern<24> pattern(input);
pattern.flip();
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsTheSpecifiedBit)
{
std::array<uint8_t, 5> input = { 0b0010'0010, 0b1010'1001, 0b0110'0101, 0b1101'0000, 0b0011'1110 };
std::array<uint8_t, 5> expected_output = { 0b0000'1011, 0b0011'1001, 0b0110'1101, 0b0101'1000, 0b0000'0110 };
bitpattern<36> pattern(input);
pattern.flip(0).flip(3).flip(5).flip(12).flip(15).flip(19).flip(27).flip(31).flip(35);
std::array<uint8_t, 5> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<12> pattern;
auto func = [&pattern] { pattern.flip(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(GetReturnsTheValueOfTheSpecifiedBit)
{
std::array<uint8_t, 3> input = { 0b0110'0100, 0b0010'1011 };
bitpattern<23> pattern(input);
bool is_set = pattern.get(2) &&
pattern.get(5) &&
pattern.get(6) &&
pattern.get(8) &&
pattern.get(9) &&
pattern.get(11) &&
pattern.get(13);
bool is_not_set = !pattern.get(0) &&
!pattern.get(1) &&
!pattern.get(3) &&
!pattern.get(4) &&
!pattern.get(7) &&
!pattern.get(10) &&
!pattern.get(12) &&
!pattern.get(14) &&
!pattern.get(15);
Assert::IsTrue(is_set && is_not_set);
}
TEST_METHOD(GetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<18> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(SetChangesTheSpecifiedBitToOne)
{
std::array<uint8_t, 3> expected_output = { 0b0011'1001, 0b0100'0100, 0b0001'0110 };
bitpattern<21> pattern;
pattern.set(0).set(3).set(4).set(5).set(10).set(14).set(17).set(18).set(20);
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetAllowsChangingAllBits)
{
std::array<uint8_t, 12> input = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
std::array<uint8_t, 12> expected_output = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0000'0111 };
bitpattern<91> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.set(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<44> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(ResetChangesTheSpecifiedBitToZero)
{
std::array<uint8_t, 4> input = { 0b0111'1011, 0b0111'0101, 0b1101'0110, 0b0001'0111 };
std::array<uint8_t, 4> expected_output = { 0b0001'1001, 0b0001'0001, 0b1101'0010, 0b0000'0000 };
bitpattern<25> pattern(input);
pattern.reset(1).reset(5).reset(6).reset(10).reset(13).reset(14).reset(16).reset(18).reset(24);
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZero)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
pattern.reset();
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZeroIndividually)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.reset(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<86> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(AllReturnsTrueIfAllBitsAreOne)
{
std::array<uint8_t, 8> input = { 255, 255, 255, 255, 255, 255, 255, 255 };
bitpattern<58> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsTrueIfPaddingBitsAreZero)
{
std::array<uint8_t, 5> input = { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b0000'0001 };
bitpattern<33> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsFalseIfNotAllBitsAreOne)
{
std::array<uint8_t, 5> input = { 0b0111'0111, 0b1111'1111, 0b1101'0111, 0b1111'1110, 0b0001'0000 };
bitpattern<37> pattern(input);
Assert::IsFalse(pattern.all());
}
TEST_METHOD(AnyReturnsTrueIfAnyBitIsOne)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0010'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsTrue(pattern.any());
}
TEST_METHOD(AnyReturnsFalseIfAllBitAreZero)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsFalse(pattern.any());
}
TEST_METHOD(NoneReturnsTrueIfNoBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<29> pattern(input);
Assert::IsTrue(pattern.none());
}
TEST_METHOD(NoneReturnsFalseIfAnyBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0100'0100, 0b0001'0000, 0b0010'0000, 0b0000'0010 };
bitpattern<29> pattern(input);
Assert::IsFalse(pattern.none());
}
TEST_METHOD(CountReturnsTheCorrectNumberOfBitsSetToOne)
{
const std::map<std::size_t, std::array<uint8_t, 4>> records
{
// Bit count (map key) does not include padding bits
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 } },
{ 15, { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ 16, { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ 16, { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ 15, { 0b0010'0001, 0b1011'0011, 0b0011'0001, 0b0011'1011 } },
{ 11, { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ 7, { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ 4, { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ 2, { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b1100'0000 } },
{ 7, { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ 18, { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ 30, { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t count = pattern.count();
std::wstring message = L"Expected " + std::to_wstring(record.first) + L" ones (1) in " + wstring_from_string(pattern.to_string()) + L" but counted " + std::to_wstring(count);
Assert::IsTrue(count == record.first, message.c_str());
}
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingAnObjectWithItself)
{
bitpattern<60> pattern;
pattern.set(48).set(12);
Assert::IsTrue(pattern == pattern);
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(EqualOperatorReturnsFalseWhenComparingTwoDifferentObjects)
{
bitpattern<17> pattern1(std::array<uint8_t, 3> { 0b0101'1010, 0b1100'0001, 0b0001'0011 });
bitpattern<17> pattern2(std::array<uint8_t, 3> { 0b1110'0110, 0b1001'0110, 0b0111'0000 });
Assert::IsFalse(pattern1 == pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingAnObjectWithItself)
{
bitpattern<129> pattern;
pattern.set(128).set(0);
Assert::IsFalse(pattern != pattern);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsFalse(pattern1 != pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsTrueWhenComparingTwoDifferentObjects)
{
bitpattern<21> pattern1(std::array<uint8_t, 3> { 0b0111'0011, 0b0101'0101, 0b0111'0100 });
bitpattern<21> pattern2(std::array<uint8_t, 3> { 0b1010'1001, 0b1010'0110, 0b1000'1111 });
Assert::IsTrue(pattern1 != pattern2);
}
TEST_METHOD(BitwiseAndAssignmentOperatorProducesAndResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1010'0010, 0b0000'0110, 0b0110'0100 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left &= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrAssignmentOperatorProducesOrResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1110'1111, 0b1111'0110, 0b0111'1111 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left |= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorAssignmentOperatorProducesXorResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left ^= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseAndOperatorProducesAndResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0010'0100, 0b0010'0010, 0b0010'1000 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 & pattern2 & pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrOperatorProducesOrResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b1111'1101, 0b1111'1111, 0b0111'1111 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 | pattern2 | pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorOperatorProducesXorResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0111'0101, 0b1111'1010, 0b0111'1001 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 ^ pattern2 ^ pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseNotOperatorInvertsThePattern)
{
std::array<uint8_t, 3> input = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
std::array<uint8_t, 3> expected_result = { 0b1011'0010, 0b0000'1111, 0b0110'0100 };
bitpattern<23> pattern(input);
bitpattern<23> pattern_inverted = ~pattern;
std::array<uint8_t, 3> actual_result = pattern_inverted.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(InvertingTwiceResultsInTheSameObject)
{
bitpattern<24> pattern1(std::array<uint8_t, 3> { 0b0110'0111, 0b1111'0100, 0b0111'1011 });
bitpattern<24> pattern2 = ~pattern1;
pattern2 = ~pattern2;
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(ToStringReturnsCorrectOutput_)
{
const std::map<std::string, std::array<uint8_t, 4>> records
{
{ "10101010101010101010101010101010", { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ "00000000111111110000000011111111", { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ "11111111000000001111111100000000", { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ "00110011001100110011001100110011", { 0b0011'0011, 0b0011'0011, 0b0011'0011, 0b0011'0011 } },
{ "11101110010100100010100010000100", { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ "01100000000110000000001000111000", { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ "00000001000000010000000100000001", { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ "00000001000000000000000100000000", { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ "00011111000001110000001100001111", { 0b0000'1111, 0b0000'0011, 0b0000'0111, 0b0001'1111 } },
{ "00000001000000000001100011110000", { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ "11111111000000000111111010111110", { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ "00101011001111101110000000001111", { 0b0000'1111, 0b1110'0000, 0b0011'1110, 0b0010'1011 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t substr_index = record.first.length() - pattern.BitCount;
std::string expected_output = record.first.substr(substr_index);
std::string actual_output = pattern.to_string();
std::wstring message = L"Expected " + wstring_from_string(expected_output) + L" but was " + wstring_from_string(actual_output);
Assert::IsTrue(actual_output == expected_output, message.c_str());
}
}
private:
std::wstring wstring_from_string(const std::string& string)
{
std::wstring wstring;
wstring.assign(string.begin(), string.end());
return wstring;
}
};
}
c++ array c++14 c++17 bitset
$endgroup$
add a comment |
$begingroup$
The use cases I’m facing require me to have a C++ data type that can store and manipulate the state of somewhere between 400 and 500 bits. In addition it is necessary to be able to store that state within SQL server databases in an efficient manner, i.e. not wasting unnecessary space because there will be a lot of such database records eventually.
I had a look at std::bitset
which is capable of storing that amount of bits but lacks the capability to export its internal state in an efficient way. It offers to_ulong
and to_ullong
which both are too small to store up to 500 bits and to_string
which would result in a string of 500 characters, i.e. one character per bit which seems rather inefficient.
I figured I could pack all bits that I require into a byte array that I could store in the SQL database as a blob and hence use eight times less space compared to storing them as a 500 character string.
First I tried to turn the output of std::bitset
into a byte array but realized that the logic required to do so might as well be turned into its own class that directly operates with a byte array.
The class that I’m posting here is the result of that approach. Its interface is inspired by std::bitset
but deviates in some cases and does not offer all functionality that std::bitset
does, simply because I have no use for that functionality.
It does provide read-only access to the array that stores the bits and offers creating an object from such an array so that I can store to and load the state from the database.
The class is designed to be compiled with C++14 but I will migrate my code base to C++17 within a few months.
When reviewing, could you please consider commenting on the following topics?
- Currently, there is no overloaded
=
operator, only a copy constructor. For this particular case, is overloading=
necessary / does make sense? - Given that I switch to C++17: Are there any parts of the code that could be simplified using C++17?
- I’m unsure how to overload the
operator so that it can be used to set/get individual bits. I assume I'll need some kind of proxy object but I'm unsure how best to do it. Hints on how to do this would be appreciated.
- I use
#pragma once
instead of the more traditional include guards because the compilers (Clang and Microsoft Visual C++) on all platforms that I build for (Android, iOS, Windows) support it. I’m unaware of any downsides of using it. Any comments regarding this? - I’m covering the class using the unit tests that I posted. They are built on top of Microsoft’s CppUnitTestFramework that ships together with Visual Studio. Comments regarding those tests are highly appreciated.
- The method to access individual bits is named
get
while the corresponding method ofstd::bitset
is namedtest
. I usedget
as name because “it just makes more sense to me thantest
”. You might consider this to be a drawback because the class cannot be used as a drop-in replacement forstd::bitset
that way. However, as mentioned not all functionality is provided anyway (<<
,>>
,operators are missing, etc.). Comments regarding this?
The class:
#pragma once
#include <array>
namespace common
{
template<std::size_t bit_count>
class bitpattern
{
public:
static constexpr std::size_t BitCount = bit_count;
static constexpr std::size_t ByteCount = (bit_count % CHAR_BIT) ? (bit_count / CHAR_BIT) + 1 : (bit_count / CHAR_BIT);
bitpattern()
{
}
// The string that is passed to this method is read from right to left, i.e.
// the last character on the right end of the string is turned into the bit
// at index 0.
bitpattern(const std::string bits)
{
std::size_t character_count = (bits.length() > bit_count) ? bit_count : bits.length();
std::size_t first_character = bits.length() - 1;
for(std::size_t i = 0; i < character_count; i++)
{
switch(bits[first_character - i])
{
case '0': continue;
case '1': set(i); break;
default : throw std::invalid_argument("Argument string contains characters other than '0' and '1'.");
}
}
}
bitpattern(const std::array<uint8_t, ByteCount> bits)
{
_bit_container = bits;
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits are 0
}
bitpattern(const bitpattern<bit_count>& pattern)
{
_bit_container = pattern._bit_container;
}
bitpattern<bit_count>& flip()
{
for(uint8_t& byte : _bit_container)
{
byte = ~byte;
}
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return *this;
}
bitpattern<bit_count>& flip(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] ^= (1u << (index % CHAR_BIT));
return *this;
}
bool get(std::size_t index) const
{
_throw_if_too_large(index);
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
bitpattern<bit_count>& set(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] |= (1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] &= ~(1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset()
{
_bit_container.fill(0);
return *this;
}
bool all() const
{
std::size_t i = 0;
for(; i < (ByteCount - 1); i++)
{
if(_bit_container[i] != 0b1111'1111)
{
return false;
}
}
// The last byte is treated separately because it could contain
// padding bits that are 0.
return _bit_container[i] == _padding_bit_mask;
}
bool any() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return true;
}
}
return false;
}
bool none() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return false;
}
}
return true;
}
std::size_t count() const
{
std::size_t count = 0;
for(uint8_t byte : _bit_container)
{
// Implementation of the Hamming Weight algorithm for 8-bit numbers.
// See https://en.wikipedia.org/wiki/Hamming_weight
// and https://stackoverflow.com/a/30692782/5548098
byte = byte - ((byte >> 1) & 0b0101'0101);
byte = (byte & 0b0011'0011) + ((byte >> 2) & 0b0011'0011);
count += ((byte + (byte >> 4)) & 0b0000'1111);
}
return count;
}
bool operator==(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] != right._bit_container[i])
{
return false;
}
}
return true;
}
bool operator!=(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] == right._bit_container[i])
{
return false;
}
}
return true;
}
bitpattern<bit_count>& operator&=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] &= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator|=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] |= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator^=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] ^= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count> operator&(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] & right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator|(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] | right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator^(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] ^ right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator~()
{
bitpattern<bit_count> inverted_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
inverted_pattern._bit_container[i] = ~_bit_container[i];
}
inverted_pattern._bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return inverted_pattern;
}
// Note that the string generated by this method must be read from
// right to left, i.e. the bit with index 0 is to be found at the
// right end of the string. The approach is taken from numbers where
// the least significant number is found at the right end.
std::string to_string() const
{
std::string pattern;
pattern.reserve(bit_count);
for(int i = (bit_count - 1); i >= 0; i--)
{
pattern.append(get(i) ? "1" : "0");
}
return pattern;
}
const std::array<uint8_t, ByteCount>& array() const
{
return _bit_container;
}
private:
void _throw_if_too_large(std::size_t index) const
{
if(index >= bit_count)
{
throw std::out_of_range("Index is too large.");
}
}
static constexpr uint8_t _create_padding_bit_mask()
{
uint8_t count = bit_count % CHAR_BIT;
uint8_t bit_mask = 0b1111'1111;
if(count)
{
for(int i = (CHAR_BIT - 1); i >= count; i--)
{
bit_mask ^= (1 << i);
}
}
return bit_mask;
}
static constexpr uint8_t _padding_bit_mask = _create_padding_bit_mask();
std::array<uint8_t, ByteCount> _bit_container{};
};
}
Associated unit tests:
#include "CppUnitTest.h"
#include "../bitpattern/bitpattern.h"
#include <map>
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace common
{
TEST_CLASS(bitpatterntests)
{
public:
TEST_METHOD(ConstructionZeroInitializesArray)
{
bitpattern<69> pattern;
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooLarge)
{
std::string bits = "10101110100011010101011100101";
bitpattern<14> pattern_from_string(bits);
bitpattern<14> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(2).set(5).set(6).set(7).set(9).set(11).set(13));
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooSmall)
{
std::string bits = "101001110101010";
bitpattern<28> pattern_from_string(bits);
bitpattern<28> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(1).set(3).set(5).set(7).set(8).set(9).set(12).set(14));
}
TEST_METHOD(ConstructionFromStringWorksWithStringOfSameLength)
{
std::string bits = "001000110011010001011";
bitpattern<21> pattern_from_string(bits);
bitpattern<21> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(1).set(3).set(7).set(9).set(10).set(13).set(14).set(18));
}
TEST_METHOD(ConstructionFromEmptyStringZeroInitializesArray)
{
std::string bits = "";
bitpattern<13> pattern(bits);
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringContainingCharactersOtherThanOneAndZeroThrowsException)
{
std::string bits = "01010A0102";
auto func = [bits] { bitpattern<29> pattern(bits); };
Assert::ExpectException<std::invalid_argument>(func);
}
TEST_METHOD(ConstructionFromArrayZeros1PaddingBits)
{
bitpattern<7> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0111'1111);
}
TEST_METHOD(ConstructionFromArrayZeros2PaddingBits)
{
bitpattern<6> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0011'1111);
}
TEST_METHOD(ConstructionFromArrayZeros3PaddingBits)
{
bitpattern<5> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0001'1111);
}
TEST_METHOD(ConstructionFromArrayZeros4PaddingBits)
{
bitpattern<4> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'1111);
}
TEST_METHOD(ConstructionFromArrayZeros5PaddingBits)
{
bitpattern<3> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0111);
}
TEST_METHOD(ConstructionFromArrayZeros6PaddingBits)
{
bitpattern<2> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0011);
}
TEST_METHOD(ConstructionFromArrayZeros7PaddingBits)
{
bitpattern<1> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0001);
}
TEST_METHOD(CopyConstructedObjectIsEqualToOriginalObject)
{
bitpattern<34> pattern;
bitpattern<34> pattern_copied(pattern);
Assert::IsTrue(pattern == pattern_copied);
}
TEST_METHOD(FlipInvertsAllBitsExceptPaddingBits)
{
std::array<uint8_t, 4> input = { 0b0011'1010, 0b1111'1011, 0b0001'1011, 0b0110'1010 };
std::array<uint8_t, 4> expected_output = { 0b1100'0101, 0b0000'0100, 0b1110'0100, 0b0000'0101 };
bitpattern<27> pattern(input);
pattern.flip();
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsAllBitsIfThereAreNoPaddingBits)
{
std::array<uint8_t, 3> input = { 0b1010'0110, 0b1111'1111, 0b0110'1001 };
std::array<uint8_t, 3> expected_output = { 0b0101'1001, 0b0000'0000, 0b1001'0110 };
bitpattern<24> pattern(input);
pattern.flip();
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsTheSpecifiedBit)
{
std::array<uint8_t, 5> input = { 0b0010'0010, 0b1010'1001, 0b0110'0101, 0b1101'0000, 0b0011'1110 };
std::array<uint8_t, 5> expected_output = { 0b0000'1011, 0b0011'1001, 0b0110'1101, 0b0101'1000, 0b0000'0110 };
bitpattern<36> pattern(input);
pattern.flip(0).flip(3).flip(5).flip(12).flip(15).flip(19).flip(27).flip(31).flip(35);
std::array<uint8_t, 5> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<12> pattern;
auto func = [&pattern] { pattern.flip(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(GetReturnsTheValueOfTheSpecifiedBit)
{
std::array<uint8_t, 3> input = { 0b0110'0100, 0b0010'1011 };
bitpattern<23> pattern(input);
bool is_set = pattern.get(2) &&
pattern.get(5) &&
pattern.get(6) &&
pattern.get(8) &&
pattern.get(9) &&
pattern.get(11) &&
pattern.get(13);
bool is_not_set = !pattern.get(0) &&
!pattern.get(1) &&
!pattern.get(3) &&
!pattern.get(4) &&
!pattern.get(7) &&
!pattern.get(10) &&
!pattern.get(12) &&
!pattern.get(14) &&
!pattern.get(15);
Assert::IsTrue(is_set && is_not_set);
}
TEST_METHOD(GetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<18> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(SetChangesTheSpecifiedBitToOne)
{
std::array<uint8_t, 3> expected_output = { 0b0011'1001, 0b0100'0100, 0b0001'0110 };
bitpattern<21> pattern;
pattern.set(0).set(3).set(4).set(5).set(10).set(14).set(17).set(18).set(20);
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetAllowsChangingAllBits)
{
std::array<uint8_t, 12> input = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
std::array<uint8_t, 12> expected_output = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0000'0111 };
bitpattern<91> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.set(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<44> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(ResetChangesTheSpecifiedBitToZero)
{
std::array<uint8_t, 4> input = { 0b0111'1011, 0b0111'0101, 0b1101'0110, 0b0001'0111 };
std::array<uint8_t, 4> expected_output = { 0b0001'1001, 0b0001'0001, 0b1101'0010, 0b0000'0000 };
bitpattern<25> pattern(input);
pattern.reset(1).reset(5).reset(6).reset(10).reset(13).reset(14).reset(16).reset(18).reset(24);
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZero)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
pattern.reset();
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZeroIndividually)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.reset(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<86> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(AllReturnsTrueIfAllBitsAreOne)
{
std::array<uint8_t, 8> input = { 255, 255, 255, 255, 255, 255, 255, 255 };
bitpattern<58> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsTrueIfPaddingBitsAreZero)
{
std::array<uint8_t, 5> input = { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b0000'0001 };
bitpattern<33> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsFalseIfNotAllBitsAreOne)
{
std::array<uint8_t, 5> input = { 0b0111'0111, 0b1111'1111, 0b1101'0111, 0b1111'1110, 0b0001'0000 };
bitpattern<37> pattern(input);
Assert::IsFalse(pattern.all());
}
TEST_METHOD(AnyReturnsTrueIfAnyBitIsOne)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0010'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsTrue(pattern.any());
}
TEST_METHOD(AnyReturnsFalseIfAllBitAreZero)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsFalse(pattern.any());
}
TEST_METHOD(NoneReturnsTrueIfNoBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<29> pattern(input);
Assert::IsTrue(pattern.none());
}
TEST_METHOD(NoneReturnsFalseIfAnyBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0100'0100, 0b0001'0000, 0b0010'0000, 0b0000'0010 };
bitpattern<29> pattern(input);
Assert::IsFalse(pattern.none());
}
TEST_METHOD(CountReturnsTheCorrectNumberOfBitsSetToOne)
{
const std::map<std::size_t, std::array<uint8_t, 4>> records
{
// Bit count (map key) does not include padding bits
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 } },
{ 15, { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ 16, { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ 16, { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ 15, { 0b0010'0001, 0b1011'0011, 0b0011'0001, 0b0011'1011 } },
{ 11, { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ 7, { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ 4, { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ 2, { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b1100'0000 } },
{ 7, { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ 18, { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ 30, { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t count = pattern.count();
std::wstring message = L"Expected " + std::to_wstring(record.first) + L" ones (1) in " + wstring_from_string(pattern.to_string()) + L" but counted " + std::to_wstring(count);
Assert::IsTrue(count == record.first, message.c_str());
}
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingAnObjectWithItself)
{
bitpattern<60> pattern;
pattern.set(48).set(12);
Assert::IsTrue(pattern == pattern);
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(EqualOperatorReturnsFalseWhenComparingTwoDifferentObjects)
{
bitpattern<17> pattern1(std::array<uint8_t, 3> { 0b0101'1010, 0b1100'0001, 0b0001'0011 });
bitpattern<17> pattern2(std::array<uint8_t, 3> { 0b1110'0110, 0b1001'0110, 0b0111'0000 });
Assert::IsFalse(pattern1 == pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingAnObjectWithItself)
{
bitpattern<129> pattern;
pattern.set(128).set(0);
Assert::IsFalse(pattern != pattern);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsFalse(pattern1 != pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsTrueWhenComparingTwoDifferentObjects)
{
bitpattern<21> pattern1(std::array<uint8_t, 3> { 0b0111'0011, 0b0101'0101, 0b0111'0100 });
bitpattern<21> pattern2(std::array<uint8_t, 3> { 0b1010'1001, 0b1010'0110, 0b1000'1111 });
Assert::IsTrue(pattern1 != pattern2);
}
TEST_METHOD(BitwiseAndAssignmentOperatorProducesAndResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1010'0010, 0b0000'0110, 0b0110'0100 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left &= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrAssignmentOperatorProducesOrResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1110'1111, 0b1111'0110, 0b0111'1111 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left |= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorAssignmentOperatorProducesXorResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left ^= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseAndOperatorProducesAndResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0010'0100, 0b0010'0010, 0b0010'1000 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 & pattern2 & pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrOperatorProducesOrResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b1111'1101, 0b1111'1111, 0b0111'1111 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 | pattern2 | pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorOperatorProducesXorResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0111'0101, 0b1111'1010, 0b0111'1001 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 ^ pattern2 ^ pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseNotOperatorInvertsThePattern)
{
std::array<uint8_t, 3> input = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
std::array<uint8_t, 3> expected_result = { 0b1011'0010, 0b0000'1111, 0b0110'0100 };
bitpattern<23> pattern(input);
bitpattern<23> pattern_inverted = ~pattern;
std::array<uint8_t, 3> actual_result = pattern_inverted.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(InvertingTwiceResultsInTheSameObject)
{
bitpattern<24> pattern1(std::array<uint8_t, 3> { 0b0110'0111, 0b1111'0100, 0b0111'1011 });
bitpattern<24> pattern2 = ~pattern1;
pattern2 = ~pattern2;
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(ToStringReturnsCorrectOutput_)
{
const std::map<std::string, std::array<uint8_t, 4>> records
{
{ "10101010101010101010101010101010", { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ "00000000111111110000000011111111", { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ "11111111000000001111111100000000", { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ "00110011001100110011001100110011", { 0b0011'0011, 0b0011'0011, 0b0011'0011, 0b0011'0011 } },
{ "11101110010100100010100010000100", { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ "01100000000110000000001000111000", { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ "00000001000000010000000100000001", { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ "00000001000000000000000100000000", { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ "00011111000001110000001100001111", { 0b0000'1111, 0b0000'0011, 0b0000'0111, 0b0001'1111 } },
{ "00000001000000000001100011110000", { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ "11111111000000000111111010111110", { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ "00101011001111101110000000001111", { 0b0000'1111, 0b1110'0000, 0b0011'1110, 0b0010'1011 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t substr_index = record.first.length() - pattern.BitCount;
std::string expected_output = record.first.substr(substr_index);
std::string actual_output = pattern.to_string();
std::wstring message = L"Expected " + wstring_from_string(expected_output) + L" but was " + wstring_from_string(actual_output);
Assert::IsTrue(actual_output == expected_output, message.c_str());
}
}
private:
std::wstring wstring_from_string(const std::string& string)
{
std::wstring wstring;
wstring.assign(string.begin(), string.end());
return wstring;
}
};
}
c++ array c++14 c++17 bitset
$endgroup$
add a comment |
$begingroup$
The use cases I’m facing require me to have a C++ data type that can store and manipulate the state of somewhere between 400 and 500 bits. In addition it is necessary to be able to store that state within SQL server databases in an efficient manner, i.e. not wasting unnecessary space because there will be a lot of such database records eventually.
I had a look at std::bitset
which is capable of storing that amount of bits but lacks the capability to export its internal state in an efficient way. It offers to_ulong
and to_ullong
which both are too small to store up to 500 bits and to_string
which would result in a string of 500 characters, i.e. one character per bit which seems rather inefficient.
I figured I could pack all bits that I require into a byte array that I could store in the SQL database as a blob and hence use eight times less space compared to storing them as a 500 character string.
First I tried to turn the output of std::bitset
into a byte array but realized that the logic required to do so might as well be turned into its own class that directly operates with a byte array.
The class that I’m posting here is the result of that approach. Its interface is inspired by std::bitset
but deviates in some cases and does not offer all functionality that std::bitset
does, simply because I have no use for that functionality.
It does provide read-only access to the array that stores the bits and offers creating an object from such an array so that I can store to and load the state from the database.
The class is designed to be compiled with C++14 but I will migrate my code base to C++17 within a few months.
When reviewing, could you please consider commenting on the following topics?
- Currently, there is no overloaded
=
operator, only a copy constructor. For this particular case, is overloading=
necessary / does make sense? - Given that I switch to C++17: Are there any parts of the code that could be simplified using C++17?
- I’m unsure how to overload the
operator so that it can be used to set/get individual bits. I assume I'll need some kind of proxy object but I'm unsure how best to do it. Hints on how to do this would be appreciated.
- I use
#pragma once
instead of the more traditional include guards because the compilers (Clang and Microsoft Visual C++) on all platforms that I build for (Android, iOS, Windows) support it. I’m unaware of any downsides of using it. Any comments regarding this? - I’m covering the class using the unit tests that I posted. They are built on top of Microsoft’s CppUnitTestFramework that ships together with Visual Studio. Comments regarding those tests are highly appreciated.
- The method to access individual bits is named
get
while the corresponding method ofstd::bitset
is namedtest
. I usedget
as name because “it just makes more sense to me thantest
”. You might consider this to be a drawback because the class cannot be used as a drop-in replacement forstd::bitset
that way. However, as mentioned not all functionality is provided anyway (<<
,>>
,operators are missing, etc.). Comments regarding this?
The class:
#pragma once
#include <array>
namespace common
{
template<std::size_t bit_count>
class bitpattern
{
public:
static constexpr std::size_t BitCount = bit_count;
static constexpr std::size_t ByteCount = (bit_count % CHAR_BIT) ? (bit_count / CHAR_BIT) + 1 : (bit_count / CHAR_BIT);
bitpattern()
{
}
// The string that is passed to this method is read from right to left, i.e.
// the last character on the right end of the string is turned into the bit
// at index 0.
bitpattern(const std::string bits)
{
std::size_t character_count = (bits.length() > bit_count) ? bit_count : bits.length();
std::size_t first_character = bits.length() - 1;
for(std::size_t i = 0; i < character_count; i++)
{
switch(bits[first_character - i])
{
case '0': continue;
case '1': set(i); break;
default : throw std::invalid_argument("Argument string contains characters other than '0' and '1'.");
}
}
}
bitpattern(const std::array<uint8_t, ByteCount> bits)
{
_bit_container = bits;
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits are 0
}
bitpattern(const bitpattern<bit_count>& pattern)
{
_bit_container = pattern._bit_container;
}
bitpattern<bit_count>& flip()
{
for(uint8_t& byte : _bit_container)
{
byte = ~byte;
}
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return *this;
}
bitpattern<bit_count>& flip(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] ^= (1u << (index % CHAR_BIT));
return *this;
}
bool get(std::size_t index) const
{
_throw_if_too_large(index);
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
bitpattern<bit_count>& set(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] |= (1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] &= ~(1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset()
{
_bit_container.fill(0);
return *this;
}
bool all() const
{
std::size_t i = 0;
for(; i < (ByteCount - 1); i++)
{
if(_bit_container[i] != 0b1111'1111)
{
return false;
}
}
// The last byte is treated separately because it could contain
// padding bits that are 0.
return _bit_container[i] == _padding_bit_mask;
}
bool any() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return true;
}
}
return false;
}
bool none() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return false;
}
}
return true;
}
std::size_t count() const
{
std::size_t count = 0;
for(uint8_t byte : _bit_container)
{
// Implementation of the Hamming Weight algorithm for 8-bit numbers.
// See https://en.wikipedia.org/wiki/Hamming_weight
// and https://stackoverflow.com/a/30692782/5548098
byte = byte - ((byte >> 1) & 0b0101'0101);
byte = (byte & 0b0011'0011) + ((byte >> 2) & 0b0011'0011);
count += ((byte + (byte >> 4)) & 0b0000'1111);
}
return count;
}
bool operator==(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] != right._bit_container[i])
{
return false;
}
}
return true;
}
bool operator!=(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] == right._bit_container[i])
{
return false;
}
}
return true;
}
bitpattern<bit_count>& operator&=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] &= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator|=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] |= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator^=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] ^= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count> operator&(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] & right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator|(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] | right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator^(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] ^ right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator~()
{
bitpattern<bit_count> inverted_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
inverted_pattern._bit_container[i] = ~_bit_container[i];
}
inverted_pattern._bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return inverted_pattern;
}
// Note that the string generated by this method must be read from
// right to left, i.e. the bit with index 0 is to be found at the
// right end of the string. The approach is taken from numbers where
// the least significant number is found at the right end.
std::string to_string() const
{
std::string pattern;
pattern.reserve(bit_count);
for(int i = (bit_count - 1); i >= 0; i--)
{
pattern.append(get(i) ? "1" : "0");
}
return pattern;
}
const std::array<uint8_t, ByteCount>& array() const
{
return _bit_container;
}
private:
void _throw_if_too_large(std::size_t index) const
{
if(index >= bit_count)
{
throw std::out_of_range("Index is too large.");
}
}
static constexpr uint8_t _create_padding_bit_mask()
{
uint8_t count = bit_count % CHAR_BIT;
uint8_t bit_mask = 0b1111'1111;
if(count)
{
for(int i = (CHAR_BIT - 1); i >= count; i--)
{
bit_mask ^= (1 << i);
}
}
return bit_mask;
}
static constexpr uint8_t _padding_bit_mask = _create_padding_bit_mask();
std::array<uint8_t, ByteCount> _bit_container{};
};
}
Associated unit tests:
#include "CppUnitTest.h"
#include "../bitpattern/bitpattern.h"
#include <map>
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace common
{
TEST_CLASS(bitpatterntests)
{
public:
TEST_METHOD(ConstructionZeroInitializesArray)
{
bitpattern<69> pattern;
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooLarge)
{
std::string bits = "10101110100011010101011100101";
bitpattern<14> pattern_from_string(bits);
bitpattern<14> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(2).set(5).set(6).set(7).set(9).set(11).set(13));
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooSmall)
{
std::string bits = "101001110101010";
bitpattern<28> pattern_from_string(bits);
bitpattern<28> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(1).set(3).set(5).set(7).set(8).set(9).set(12).set(14));
}
TEST_METHOD(ConstructionFromStringWorksWithStringOfSameLength)
{
std::string bits = "001000110011010001011";
bitpattern<21> pattern_from_string(bits);
bitpattern<21> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(1).set(3).set(7).set(9).set(10).set(13).set(14).set(18));
}
TEST_METHOD(ConstructionFromEmptyStringZeroInitializesArray)
{
std::string bits = "";
bitpattern<13> pattern(bits);
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringContainingCharactersOtherThanOneAndZeroThrowsException)
{
std::string bits = "01010A0102";
auto func = [bits] { bitpattern<29> pattern(bits); };
Assert::ExpectException<std::invalid_argument>(func);
}
TEST_METHOD(ConstructionFromArrayZeros1PaddingBits)
{
bitpattern<7> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0111'1111);
}
TEST_METHOD(ConstructionFromArrayZeros2PaddingBits)
{
bitpattern<6> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0011'1111);
}
TEST_METHOD(ConstructionFromArrayZeros3PaddingBits)
{
bitpattern<5> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0001'1111);
}
TEST_METHOD(ConstructionFromArrayZeros4PaddingBits)
{
bitpattern<4> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'1111);
}
TEST_METHOD(ConstructionFromArrayZeros5PaddingBits)
{
bitpattern<3> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0111);
}
TEST_METHOD(ConstructionFromArrayZeros6PaddingBits)
{
bitpattern<2> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0011);
}
TEST_METHOD(ConstructionFromArrayZeros7PaddingBits)
{
bitpattern<1> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0001);
}
TEST_METHOD(CopyConstructedObjectIsEqualToOriginalObject)
{
bitpattern<34> pattern;
bitpattern<34> pattern_copied(pattern);
Assert::IsTrue(pattern == pattern_copied);
}
TEST_METHOD(FlipInvertsAllBitsExceptPaddingBits)
{
std::array<uint8_t, 4> input = { 0b0011'1010, 0b1111'1011, 0b0001'1011, 0b0110'1010 };
std::array<uint8_t, 4> expected_output = { 0b1100'0101, 0b0000'0100, 0b1110'0100, 0b0000'0101 };
bitpattern<27> pattern(input);
pattern.flip();
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsAllBitsIfThereAreNoPaddingBits)
{
std::array<uint8_t, 3> input = { 0b1010'0110, 0b1111'1111, 0b0110'1001 };
std::array<uint8_t, 3> expected_output = { 0b0101'1001, 0b0000'0000, 0b1001'0110 };
bitpattern<24> pattern(input);
pattern.flip();
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsTheSpecifiedBit)
{
std::array<uint8_t, 5> input = { 0b0010'0010, 0b1010'1001, 0b0110'0101, 0b1101'0000, 0b0011'1110 };
std::array<uint8_t, 5> expected_output = { 0b0000'1011, 0b0011'1001, 0b0110'1101, 0b0101'1000, 0b0000'0110 };
bitpattern<36> pattern(input);
pattern.flip(0).flip(3).flip(5).flip(12).flip(15).flip(19).flip(27).flip(31).flip(35);
std::array<uint8_t, 5> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<12> pattern;
auto func = [&pattern] { pattern.flip(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(GetReturnsTheValueOfTheSpecifiedBit)
{
std::array<uint8_t, 3> input = { 0b0110'0100, 0b0010'1011 };
bitpattern<23> pattern(input);
bool is_set = pattern.get(2) &&
pattern.get(5) &&
pattern.get(6) &&
pattern.get(8) &&
pattern.get(9) &&
pattern.get(11) &&
pattern.get(13);
bool is_not_set = !pattern.get(0) &&
!pattern.get(1) &&
!pattern.get(3) &&
!pattern.get(4) &&
!pattern.get(7) &&
!pattern.get(10) &&
!pattern.get(12) &&
!pattern.get(14) &&
!pattern.get(15);
Assert::IsTrue(is_set && is_not_set);
}
TEST_METHOD(GetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<18> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(SetChangesTheSpecifiedBitToOne)
{
std::array<uint8_t, 3> expected_output = { 0b0011'1001, 0b0100'0100, 0b0001'0110 };
bitpattern<21> pattern;
pattern.set(0).set(3).set(4).set(5).set(10).set(14).set(17).set(18).set(20);
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetAllowsChangingAllBits)
{
std::array<uint8_t, 12> input = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
std::array<uint8_t, 12> expected_output = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0000'0111 };
bitpattern<91> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.set(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<44> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(ResetChangesTheSpecifiedBitToZero)
{
std::array<uint8_t, 4> input = { 0b0111'1011, 0b0111'0101, 0b1101'0110, 0b0001'0111 };
std::array<uint8_t, 4> expected_output = { 0b0001'1001, 0b0001'0001, 0b1101'0010, 0b0000'0000 };
bitpattern<25> pattern(input);
pattern.reset(1).reset(5).reset(6).reset(10).reset(13).reset(14).reset(16).reset(18).reset(24);
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZero)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
pattern.reset();
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZeroIndividually)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.reset(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<86> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(AllReturnsTrueIfAllBitsAreOne)
{
std::array<uint8_t, 8> input = { 255, 255, 255, 255, 255, 255, 255, 255 };
bitpattern<58> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsTrueIfPaddingBitsAreZero)
{
std::array<uint8_t, 5> input = { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b0000'0001 };
bitpattern<33> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsFalseIfNotAllBitsAreOne)
{
std::array<uint8_t, 5> input = { 0b0111'0111, 0b1111'1111, 0b1101'0111, 0b1111'1110, 0b0001'0000 };
bitpattern<37> pattern(input);
Assert::IsFalse(pattern.all());
}
TEST_METHOD(AnyReturnsTrueIfAnyBitIsOne)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0010'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsTrue(pattern.any());
}
TEST_METHOD(AnyReturnsFalseIfAllBitAreZero)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsFalse(pattern.any());
}
TEST_METHOD(NoneReturnsTrueIfNoBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<29> pattern(input);
Assert::IsTrue(pattern.none());
}
TEST_METHOD(NoneReturnsFalseIfAnyBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0100'0100, 0b0001'0000, 0b0010'0000, 0b0000'0010 };
bitpattern<29> pattern(input);
Assert::IsFalse(pattern.none());
}
TEST_METHOD(CountReturnsTheCorrectNumberOfBitsSetToOne)
{
const std::map<std::size_t, std::array<uint8_t, 4>> records
{
// Bit count (map key) does not include padding bits
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 } },
{ 15, { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ 16, { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ 16, { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ 15, { 0b0010'0001, 0b1011'0011, 0b0011'0001, 0b0011'1011 } },
{ 11, { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ 7, { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ 4, { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ 2, { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b1100'0000 } },
{ 7, { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ 18, { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ 30, { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t count = pattern.count();
std::wstring message = L"Expected " + std::to_wstring(record.first) + L" ones (1) in " + wstring_from_string(pattern.to_string()) + L" but counted " + std::to_wstring(count);
Assert::IsTrue(count == record.first, message.c_str());
}
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingAnObjectWithItself)
{
bitpattern<60> pattern;
pattern.set(48).set(12);
Assert::IsTrue(pattern == pattern);
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(EqualOperatorReturnsFalseWhenComparingTwoDifferentObjects)
{
bitpattern<17> pattern1(std::array<uint8_t, 3> { 0b0101'1010, 0b1100'0001, 0b0001'0011 });
bitpattern<17> pattern2(std::array<uint8_t, 3> { 0b1110'0110, 0b1001'0110, 0b0111'0000 });
Assert::IsFalse(pattern1 == pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingAnObjectWithItself)
{
bitpattern<129> pattern;
pattern.set(128).set(0);
Assert::IsFalse(pattern != pattern);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsFalse(pattern1 != pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsTrueWhenComparingTwoDifferentObjects)
{
bitpattern<21> pattern1(std::array<uint8_t, 3> { 0b0111'0011, 0b0101'0101, 0b0111'0100 });
bitpattern<21> pattern2(std::array<uint8_t, 3> { 0b1010'1001, 0b1010'0110, 0b1000'1111 });
Assert::IsTrue(pattern1 != pattern2);
}
TEST_METHOD(BitwiseAndAssignmentOperatorProducesAndResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1010'0010, 0b0000'0110, 0b0110'0100 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left &= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrAssignmentOperatorProducesOrResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1110'1111, 0b1111'0110, 0b0111'1111 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left |= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorAssignmentOperatorProducesXorResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left ^= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseAndOperatorProducesAndResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0010'0100, 0b0010'0010, 0b0010'1000 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 & pattern2 & pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrOperatorProducesOrResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b1111'1101, 0b1111'1111, 0b0111'1111 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 | pattern2 | pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorOperatorProducesXorResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0111'0101, 0b1111'1010, 0b0111'1001 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 ^ pattern2 ^ pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseNotOperatorInvertsThePattern)
{
std::array<uint8_t, 3> input = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
std::array<uint8_t, 3> expected_result = { 0b1011'0010, 0b0000'1111, 0b0110'0100 };
bitpattern<23> pattern(input);
bitpattern<23> pattern_inverted = ~pattern;
std::array<uint8_t, 3> actual_result = pattern_inverted.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(InvertingTwiceResultsInTheSameObject)
{
bitpattern<24> pattern1(std::array<uint8_t, 3> { 0b0110'0111, 0b1111'0100, 0b0111'1011 });
bitpattern<24> pattern2 = ~pattern1;
pattern2 = ~pattern2;
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(ToStringReturnsCorrectOutput_)
{
const std::map<std::string, std::array<uint8_t, 4>> records
{
{ "10101010101010101010101010101010", { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ "00000000111111110000000011111111", { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ "11111111000000001111111100000000", { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ "00110011001100110011001100110011", { 0b0011'0011, 0b0011'0011, 0b0011'0011, 0b0011'0011 } },
{ "11101110010100100010100010000100", { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ "01100000000110000000001000111000", { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ "00000001000000010000000100000001", { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ "00000001000000000000000100000000", { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ "00011111000001110000001100001111", { 0b0000'1111, 0b0000'0011, 0b0000'0111, 0b0001'1111 } },
{ "00000001000000000001100011110000", { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ "11111111000000000111111010111110", { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ "00101011001111101110000000001111", { 0b0000'1111, 0b1110'0000, 0b0011'1110, 0b0010'1011 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t substr_index = record.first.length() - pattern.BitCount;
std::string expected_output = record.first.substr(substr_index);
std::string actual_output = pattern.to_string();
std::wstring message = L"Expected " + wstring_from_string(expected_output) + L" but was " + wstring_from_string(actual_output);
Assert::IsTrue(actual_output == expected_output, message.c_str());
}
}
private:
std::wstring wstring_from_string(const std::string& string)
{
std::wstring wstring;
wstring.assign(string.begin(), string.end());
return wstring;
}
};
}
c++ array c++14 c++17 bitset
$endgroup$
The use cases I’m facing require me to have a C++ data type that can store and manipulate the state of somewhere between 400 and 500 bits. In addition it is necessary to be able to store that state within SQL server databases in an efficient manner, i.e. not wasting unnecessary space because there will be a lot of such database records eventually.
I had a look at std::bitset
which is capable of storing that amount of bits but lacks the capability to export its internal state in an efficient way. It offers to_ulong
and to_ullong
which both are too small to store up to 500 bits and to_string
which would result in a string of 500 characters, i.e. one character per bit which seems rather inefficient.
I figured I could pack all bits that I require into a byte array that I could store in the SQL database as a blob and hence use eight times less space compared to storing them as a 500 character string.
First I tried to turn the output of std::bitset
into a byte array but realized that the logic required to do so might as well be turned into its own class that directly operates with a byte array.
The class that I’m posting here is the result of that approach. Its interface is inspired by std::bitset
but deviates in some cases and does not offer all functionality that std::bitset
does, simply because I have no use for that functionality.
It does provide read-only access to the array that stores the bits and offers creating an object from such an array so that I can store to and load the state from the database.
The class is designed to be compiled with C++14 but I will migrate my code base to C++17 within a few months.
When reviewing, could you please consider commenting on the following topics?
- Currently, there is no overloaded
=
operator, only a copy constructor. For this particular case, is overloading=
necessary / does make sense? - Given that I switch to C++17: Are there any parts of the code that could be simplified using C++17?
- I’m unsure how to overload the
operator so that it can be used to set/get individual bits. I assume I'll need some kind of proxy object but I'm unsure how best to do it. Hints on how to do this would be appreciated.
- I use
#pragma once
instead of the more traditional include guards because the compilers (Clang and Microsoft Visual C++) on all platforms that I build for (Android, iOS, Windows) support it. I’m unaware of any downsides of using it. Any comments regarding this? - I’m covering the class using the unit tests that I posted. They are built on top of Microsoft’s CppUnitTestFramework that ships together with Visual Studio. Comments regarding those tests are highly appreciated.
- The method to access individual bits is named
get
while the corresponding method ofstd::bitset
is namedtest
. I usedget
as name because “it just makes more sense to me thantest
”. You might consider this to be a drawback because the class cannot be used as a drop-in replacement forstd::bitset
that way. However, as mentioned not all functionality is provided anyway (<<
,>>
,operators are missing, etc.). Comments regarding this?
The class:
#pragma once
#include <array>
namespace common
{
template<std::size_t bit_count>
class bitpattern
{
public:
static constexpr std::size_t BitCount = bit_count;
static constexpr std::size_t ByteCount = (bit_count % CHAR_BIT) ? (bit_count / CHAR_BIT) + 1 : (bit_count / CHAR_BIT);
bitpattern()
{
}
// The string that is passed to this method is read from right to left, i.e.
// the last character on the right end of the string is turned into the bit
// at index 0.
bitpattern(const std::string bits)
{
std::size_t character_count = (bits.length() > bit_count) ? bit_count : bits.length();
std::size_t first_character = bits.length() - 1;
for(std::size_t i = 0; i < character_count; i++)
{
switch(bits[first_character - i])
{
case '0': continue;
case '1': set(i); break;
default : throw std::invalid_argument("Argument string contains characters other than '0' and '1'.");
}
}
}
bitpattern(const std::array<uint8_t, ByteCount> bits)
{
_bit_container = bits;
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits are 0
}
bitpattern(const bitpattern<bit_count>& pattern)
{
_bit_container = pattern._bit_container;
}
bitpattern<bit_count>& flip()
{
for(uint8_t& byte : _bit_container)
{
byte = ~byte;
}
_bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return *this;
}
bitpattern<bit_count>& flip(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] ^= (1u << (index % CHAR_BIT));
return *this;
}
bool get(std::size_t index) const
{
_throw_if_too_large(index);
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
bitpattern<bit_count>& set(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] |= (1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset(std::size_t index)
{
_throw_if_too_large(index);
_bit_container[index / CHAR_BIT] &= ~(1u << (index % CHAR_BIT));
return *this;
}
bitpattern<bit_count>& reset()
{
_bit_container.fill(0);
return *this;
}
bool all() const
{
std::size_t i = 0;
for(; i < (ByteCount - 1); i++)
{
if(_bit_container[i] != 0b1111'1111)
{
return false;
}
}
// The last byte is treated separately because it could contain
// padding bits that are 0.
return _bit_container[i] == _padding_bit_mask;
}
bool any() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return true;
}
}
return false;
}
bool none() const
{
for(uint8_t byte : _bit_container)
{
if(byte > 0)
{
return false;
}
}
return true;
}
std::size_t count() const
{
std::size_t count = 0;
for(uint8_t byte : _bit_container)
{
// Implementation of the Hamming Weight algorithm for 8-bit numbers.
// See https://en.wikipedia.org/wiki/Hamming_weight
// and https://stackoverflow.com/a/30692782/5548098
byte = byte - ((byte >> 1) & 0b0101'0101);
byte = (byte & 0b0011'0011) + ((byte >> 2) & 0b0011'0011);
count += ((byte + (byte >> 4)) & 0b0000'1111);
}
return count;
}
bool operator==(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] != right._bit_container[i])
{
return false;
}
}
return true;
}
bool operator!=(const bitpattern<bit_count>& right) const
{
for(std::size_t i = 0; i < ByteCount; i++)
{
if(_bit_container[i] == right._bit_container[i])
{
return false;
}
}
return true;
}
bitpattern<bit_count>& operator&=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] &= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator|=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] |= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count>& operator^=(const bitpattern<bit_count>& right)
{
for(std::size_t i = 0; i < ByteCount; i++)
{
_bit_container[i] ^= right._bit_container[i];
}
return *this;
}
bitpattern<bit_count> operator&(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] & right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator|(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] | right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator^(const bitpattern<bit_count>& right)
{
bitpattern<bit_count> resulting_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
resulting_pattern._bit_container[i] = _bit_container[i] ^ right._bit_container[i];
}
return resulting_pattern;
}
bitpattern<bit_count> operator~()
{
bitpattern<bit_count> inverted_pattern;
for(std::size_t i = 0; i < ByteCount; i++)
{
inverted_pattern._bit_container[i] = ~_bit_container[i];
}
inverted_pattern._bit_container[ByteCount - 1] &= _padding_bit_mask; // Ensure that the padding bits stay 0
return inverted_pattern;
}
// Note that the string generated by this method must be read from
// right to left, i.e. the bit with index 0 is to be found at the
// right end of the string. The approach is taken from numbers where
// the least significant number is found at the right end.
std::string to_string() const
{
std::string pattern;
pattern.reserve(bit_count);
for(int i = (bit_count - 1); i >= 0; i--)
{
pattern.append(get(i) ? "1" : "0");
}
return pattern;
}
const std::array<uint8_t, ByteCount>& array() const
{
return _bit_container;
}
private:
void _throw_if_too_large(std::size_t index) const
{
if(index >= bit_count)
{
throw std::out_of_range("Index is too large.");
}
}
static constexpr uint8_t _create_padding_bit_mask()
{
uint8_t count = bit_count % CHAR_BIT;
uint8_t bit_mask = 0b1111'1111;
if(count)
{
for(int i = (CHAR_BIT - 1); i >= count; i--)
{
bit_mask ^= (1 << i);
}
}
return bit_mask;
}
static constexpr uint8_t _padding_bit_mask = _create_padding_bit_mask();
std::array<uint8_t, ByteCount> _bit_container{};
};
}
Associated unit tests:
#include "CppUnitTest.h"
#include "../bitpattern/bitpattern.h"
#include <map>
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace common
{
TEST_CLASS(bitpatterntests)
{
public:
TEST_METHOD(ConstructionZeroInitializesArray)
{
bitpattern<69> pattern;
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooLarge)
{
std::string bits = "10101110100011010101011100101";
bitpattern<14> pattern_from_string(bits);
bitpattern<14> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(2).set(5).set(6).set(7).set(9).set(11).set(13));
}
TEST_METHOD(ConstructionFromStringWorksEvenIfTheStringIsTooSmall)
{
std::string bits = "101001110101010";
bitpattern<28> pattern_from_string(bits);
bitpattern<28> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(1).set(3).set(5).set(7).set(8).set(9).set(12).set(14));
}
TEST_METHOD(ConstructionFromStringWorksWithStringOfSameLength)
{
std::string bits = "001000110011010001011";
bitpattern<21> pattern_from_string(bits);
bitpattern<21> pattern_reference;
Assert::IsTrue(pattern_from_string == pattern_reference.set(0).set(1).set(3).set(7).set(9).set(10).set(13).set(14).set(18));
}
TEST_METHOD(ConstructionFromEmptyStringZeroInitializesArray)
{
std::string bits = "";
bitpattern<13> pattern(bits);
std::array<uint8_t, pattern.ByteCount> actual_output = pattern.array();
std::array<uint8_t, pattern.ByteCount> expected_output = { 0, 0 };
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ConstructionFromStringContainingCharactersOtherThanOneAndZeroThrowsException)
{
std::string bits = "01010A0102";
auto func = [bits] { bitpattern<29> pattern(bits); };
Assert::ExpectException<std::invalid_argument>(func);
}
TEST_METHOD(ConstructionFromArrayZeros1PaddingBits)
{
bitpattern<7> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0111'1111);
}
TEST_METHOD(ConstructionFromArrayZeros2PaddingBits)
{
bitpattern<6> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0011'1111);
}
TEST_METHOD(ConstructionFromArrayZeros3PaddingBits)
{
bitpattern<5> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0001'1111);
}
TEST_METHOD(ConstructionFromArrayZeros4PaddingBits)
{
bitpattern<4> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'1111);
}
TEST_METHOD(ConstructionFromArrayZeros5PaddingBits)
{
bitpattern<3> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0111);
}
TEST_METHOD(ConstructionFromArrayZeros6PaddingBits)
{
bitpattern<2> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0011);
}
TEST_METHOD(ConstructionFromArrayZeros7PaddingBits)
{
bitpattern<1> pattern(std::array<uint8_t, 1> { 0b1111'1111 });
Assert::IsTrue(pattern.array()[0] == 0b0000'0001);
}
TEST_METHOD(CopyConstructedObjectIsEqualToOriginalObject)
{
bitpattern<34> pattern;
bitpattern<34> pattern_copied(pattern);
Assert::IsTrue(pattern == pattern_copied);
}
TEST_METHOD(FlipInvertsAllBitsExceptPaddingBits)
{
std::array<uint8_t, 4> input = { 0b0011'1010, 0b1111'1011, 0b0001'1011, 0b0110'1010 };
std::array<uint8_t, 4> expected_output = { 0b1100'0101, 0b0000'0100, 0b1110'0100, 0b0000'0101 };
bitpattern<27> pattern(input);
pattern.flip();
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsAllBitsIfThereAreNoPaddingBits)
{
std::array<uint8_t, 3> input = { 0b1010'0110, 0b1111'1111, 0b0110'1001 };
std::array<uint8_t, 3> expected_output = { 0b0101'1001, 0b0000'0000, 0b1001'0110 };
bitpattern<24> pattern(input);
pattern.flip();
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipInvertsTheSpecifiedBit)
{
std::array<uint8_t, 5> input = { 0b0010'0010, 0b1010'1001, 0b0110'0101, 0b1101'0000, 0b0011'1110 };
std::array<uint8_t, 5> expected_output = { 0b0000'1011, 0b0011'1001, 0b0110'1101, 0b0101'1000, 0b0000'0110 };
bitpattern<36> pattern(input);
pattern.flip(0).flip(3).flip(5).flip(12).flip(15).flip(19).flip(27).flip(31).flip(35);
std::array<uint8_t, 5> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(FlipThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<12> pattern;
auto func = [&pattern] { pattern.flip(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(GetReturnsTheValueOfTheSpecifiedBit)
{
std::array<uint8_t, 3> input = { 0b0110'0100, 0b0010'1011 };
bitpattern<23> pattern(input);
bool is_set = pattern.get(2) &&
pattern.get(5) &&
pattern.get(6) &&
pattern.get(8) &&
pattern.get(9) &&
pattern.get(11) &&
pattern.get(13);
bool is_not_set = !pattern.get(0) &&
!pattern.get(1) &&
!pattern.get(3) &&
!pattern.get(4) &&
!pattern.get(7) &&
!pattern.get(10) &&
!pattern.get(12) &&
!pattern.get(14) &&
!pattern.get(15);
Assert::IsTrue(is_set && is_not_set);
}
TEST_METHOD(GetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<18> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(SetChangesTheSpecifiedBitToOne)
{
std::array<uint8_t, 3> expected_output = { 0b0011'1001, 0b0100'0100, 0b0001'0110 };
bitpattern<21> pattern;
pattern.set(0).set(3).set(4).set(5).set(10).set(14).set(17).set(18).set(20);
std::array<uint8_t, 3> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetAllowsChangingAllBits)
{
std::array<uint8_t, 12> input = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
std::array<uint8_t, 12> expected_output = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0000'0111 };
bitpattern<91> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.set(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(SetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<44> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(ResetChangesTheSpecifiedBitToZero)
{
std::array<uint8_t, 4> input = { 0b0111'1011, 0b0111'0101, 0b1101'0110, 0b0001'0111 };
std::array<uint8_t, 4> expected_output = { 0b0001'1001, 0b0001'0001, 0b1101'0010, 0b0000'0000 };
bitpattern<25> pattern(input);
pattern.reset(1).reset(5).reset(6).reset(10).reset(13).reset(14).reset(16).reset(18).reset(24);
std::array<uint8_t, 4> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZero)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
pattern.reset();
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetChangesAllBitsToZeroIndividually)
{
std::array<uint8_t, 12> input = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0b0011'1111 };
std::array<uint8_t, 12> expected_output = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bitpattern<94> pattern;
for(std::size_t i = 0; i < pattern.BitCount; i++)
{
pattern.reset(i);
}
std::array<uint8_t, 12> actual_output = pattern.array();
Assert::IsTrue(actual_output == expected_output);
}
TEST_METHOD(ResetThrowsExceptionForIndexThatIsTooLarge)
{
bitpattern<86> pattern;
auto func = [&pattern] { pattern.get(pattern.BitCount); };
Assert::ExpectException<std::out_of_range>(func);
}
TEST_METHOD(AllReturnsTrueIfAllBitsAreOne)
{
std::array<uint8_t, 8> input = { 255, 255, 255, 255, 255, 255, 255, 255 };
bitpattern<58> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsTrueIfPaddingBitsAreZero)
{
std::array<uint8_t, 5> input = { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b0000'0001 };
bitpattern<33> pattern(input);
Assert::IsTrue(pattern.all());
}
TEST_METHOD(AllReturnsFalseIfNotAllBitsAreOne)
{
std::array<uint8_t, 5> input = { 0b0111'0111, 0b1111'1111, 0b1101'0111, 0b1111'1110, 0b0001'0000 };
bitpattern<37> pattern(input);
Assert::IsFalse(pattern.all());
}
TEST_METHOD(AnyReturnsTrueIfAnyBitIsOne)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0010'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsTrue(pattern.any());
}
TEST_METHOD(AnyReturnsFalseIfAllBitAreZero)
{
std::array<uint8_t, 3> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<18> pattern(input);
Assert::IsFalse(pattern.any());
}
TEST_METHOD(NoneReturnsTrueIfNoBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 };
bitpattern<29> pattern(input);
Assert::IsTrue(pattern.none());
}
TEST_METHOD(NoneReturnsFalseIfAnyBitsAreOne)
{
std::array<uint8_t, 4> input = { 0b0100'0100, 0b0001'0000, 0b0010'0000, 0b0000'0010 };
bitpattern<29> pattern(input);
Assert::IsFalse(pattern.none());
}
TEST_METHOD(CountReturnsTheCorrectNumberOfBitsSetToOne)
{
const std::map<std::size_t, std::array<uint8_t, 4>> records
{
// Bit count (map key) does not include padding bits
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b0000'0000 } },
{ 15, { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ 16, { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ 16, { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ 15, { 0b0010'0001, 0b1011'0011, 0b0011'0001, 0b0011'1011 } },
{ 11, { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ 7, { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ 4, { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ 2, { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ 0, { 0b0000'0000, 0b0000'0000, 0b0000'0000, 0b1100'0000 } },
{ 7, { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ 18, { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ 30, { 0b1111'1111, 0b1111'1111, 0b1111'1111, 0b1111'1111 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t count = pattern.count();
std::wstring message = L"Expected " + std::to_wstring(record.first) + L" ones (1) in " + wstring_from_string(pattern.to_string()) + L" but counted " + std::to_wstring(count);
Assert::IsTrue(count == record.first, message.c_str());
}
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingAnObjectWithItself)
{
bitpattern<60> pattern;
pattern.set(48).set(12);
Assert::IsTrue(pattern == pattern);
}
TEST_METHOD(EqualOperatorReturnsTrueWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(EqualOperatorReturnsFalseWhenComparingTwoDifferentObjects)
{
bitpattern<17> pattern1(std::array<uint8_t, 3> { 0b0101'1010, 0b1100'0001, 0b0001'0011 });
bitpattern<17> pattern2(std::array<uint8_t, 3> { 0b1110'0110, 0b1001'0110, 0b0111'0000 });
Assert::IsFalse(pattern1 == pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingAnObjectWithItself)
{
bitpattern<129> pattern;
pattern.set(128).set(0);
Assert::IsFalse(pattern != pattern);
}
TEST_METHOD(NotEqualOperatorReturnsFalseWhenComparingTwoSimilarObjects)
{
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<24> pattern2(input);
Assert::IsFalse(pattern1 != pattern2);
}
TEST_METHOD(NotEqualOperatorReturnsTrueWhenComparingTwoDifferentObjects)
{
bitpattern<21> pattern1(std::array<uint8_t, 3> { 0b0111'0011, 0b0101'0101, 0b0111'0100 });
bitpattern<21> pattern2(std::array<uint8_t, 3> { 0b1010'1001, 0b1010'0110, 0b1000'1111 });
Assert::IsTrue(pattern1 != pattern2);
}
TEST_METHOD(BitwiseAndAssignmentOperatorProducesAndResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1010'0010, 0b0000'0110, 0b0110'0100 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left &= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrAssignmentOperatorProducesOrResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b1110'1111, 0b1111'0110, 0b0111'1111 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left |= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorAssignmentOperatorProducesXorResultOfTwoPatterns)
{
std::array<uint8_t, 3> left = { 0b1110'0110, 0b0101'0110, 0b1111'0100 };
std::array<uint8_t, 3> right = { 0b1010'1011, 0b1010'0110, 0b1110'1111 };
std::array<uint8_t, 3> expected_result = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
bitpattern<23> pattern_left (left);
bitpattern<23> pattern_right(right);
pattern_left ^= pattern_right;
std::array<uint8_t, 3> actual_result = pattern_left.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseAndOperatorProducesAndResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0010'0100, 0b0010'0010, 0b0010'1000 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 & pattern2 & pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseOrOperatorProducesOrResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b1111'1101, 0b1111'1111, 0b0111'1111 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 | pattern2 | pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseXorOperatorProducesXorResultOfMultiplePatterns)
{
std::array<uint8_t, 3> input1 = { 0b0011'0101, 0b0010'1111, 0b1010'1010 };
std::array<uint8_t, 3> input2 = { 0b1010'1100, 0b1010'0011, 0b1110'1111 };
std::array<uint8_t, 3> input3 = { 0b1110'1100, 0b0111'0110, 0b1011'1100 };
std::array<uint8_t, 3> expected_result = { 0b0111'0101, 0b1111'1010, 0b0111'1001 };
bitpattern<23> pattern1(input1);
bitpattern<23> pattern2(input2);
bitpattern<23> pattern3(input3);
bitpattern<23> pattern_result = pattern1 ^ pattern2 ^ pattern3;
std::array<uint8_t, 3> actual_result = pattern_result.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(BitwiseNotOperatorInvertsThePattern)
{
std::array<uint8_t, 3> input = { 0b0100'1101, 0b1111'0000, 0b0001'1011 };
std::array<uint8_t, 3> expected_result = { 0b1011'0010, 0b0000'1111, 0b0110'0100 };
bitpattern<23> pattern(input);
bitpattern<23> pattern_inverted = ~pattern;
std::array<uint8_t, 3> actual_result = pattern_inverted.array();
Assert::IsTrue(actual_result == expected_result);
}
TEST_METHOD(InvertingTwiceResultsInTheSameObject)
{
bitpattern<24> pattern1(std::array<uint8_t, 3> { 0b0110'0111, 0b1111'0100, 0b0111'1011 });
bitpattern<24> pattern2 = ~pattern1;
pattern2 = ~pattern2;
Assert::IsTrue(pattern1 == pattern2);
}
TEST_METHOD(ToStringReturnsCorrectOutput_)
{
const std::map<std::string, std::array<uint8_t, 4>> records
{
{ "10101010101010101010101010101010", { 0b1010'1010, 0b1010'1010, 0b1010'1010, 0b1010'1010 } },
{ "00000000111111110000000011111111", { 0b1111'1111, 0b0000'0000, 0b1111'1111, 0b0000'0000 } },
{ "11111111000000001111111100000000", { 0b0000'0000, 0b1111'1111, 0b0000'0000, 0b1111'1111 } },
{ "00110011001100110011001100110011", { 0b0011'0011, 0b0011'0011, 0b0011'0011, 0b0011'0011 } },
{ "11101110010100100010100010000100", { 0b1000'0100, 0b0010'1000, 0b0101'0010, 0b1110'1110 } },
{ "01100000000110000000001000111000", { 0b0011'1000, 0b0000'0010, 0b0001'1000, 0b0110'0000 } },
{ "00000001000000010000000100000001", { 0b0000'0001, 0b0000'0001, 0b0000'0001, 0b0000'0001 } },
{ "00000001000000000000000100000000", { 0b0000'0000, 0b0000'0001, 0b0000'0000, 0b0000'0001 } },
{ "00011111000001110000001100001111", { 0b0000'1111, 0b0000'0011, 0b0000'0111, 0b0001'1111 } },
{ "00000001000000000001100011110000", { 0b1111'0000, 0b0001'1000, 0b0000'0000, 0b0000'0001 } },
{ "11111111000000000111111010111110", { 0b1011'1110, 0b0111'1110, 0b0000'0000, 0b1111'1111 } },
{ "00101011001111101110000000001111", { 0b0000'1111, 0b1110'0000, 0b0011'1110, 0b0010'1011 } },
};
for(auto const& record : records)
{
bitpattern<30> pattern(record.second);
std::size_t substr_index = record.first.length() - pattern.BitCount;
std::string expected_output = record.first.substr(substr_index);
std::string actual_output = pattern.to_string();
std::wstring message = L"Expected " + wstring_from_string(expected_output) + L" but was " + wstring_from_string(actual_output);
Assert::IsTrue(actual_output == expected_output, message.c_str());
}
}
private:
std::wstring wstring_from_string(const std::string& string)
{
std::wstring wstring;
wstring.assign(string.begin(), string.end());
return wstring;
}
};
}
c++ array c++14 c++17 bitset
c++ array c++14 c++17 bitset
edited Jan 1 at 1:36
200_success
129k15153415
129k15153415
asked Dec 31 '18 at 9:19
ackhackh
1585
1585
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here are some things that may help you improve your program.
Use all required #include
s
The templated class uses CHAR_BIT
but is missing this line that provides the definition:
#include <climits>
Eliminate unused variables
The variable input
in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.
Be careful with naming
I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common
for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.
Keep maintaining the tests
The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.
Let the compiler generate the empty constructor
Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:
bitpattern() = default;
The intent is a bit more clear in my opinion.
Consider adding some constructors
At the moment this code won't compile:
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<22> pattern2(input);
bitpattern<24> pattern3(pattern2);
It would be nice to have the ability to create longer bit patterns from smaller ones.
It would also be nice to provide constexpr
constructors for patterns like this:
constexpr bitpattern<23> pattern{0x6423};
Here's a way to do that:
constexpr bitpattern(unsigned long long val)
{
for (std::size_t i=0; i < ByteCount; ++i) {
_bit_container[i] = val & 0xff;
val >>= 8;
}
}
Note that this uses for
loop in a constexpr
function and uses the operator
on the std::array
and so requires C++17 or later.
Consider adding operator
The std::bitset
uses std::bitset::reference
to enable operator
. You could probably do the same. Note that there are two flavors; one is constexpr
and returns an actual bool
and the other returns a reference
object. Here's one way to do that. First, here's the reference
class which is in the public
section of the bitpattern
class:
class reference {
friend class bitpattern<bit_count>;
public:
reference& operator=(bool x) {
if (x) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
reference(); // leave undefined
reference& operator=(const reference& x) {
bool bit{x};
if (bit) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
~reference() = default;
operator bool() const {
return *ptr & mask;
}
bool operator~() const {
return !(*ptr & mask);
}
reference& flip() {
*ptr ^= mask;
return *this;
}
private:
reference(uint8_t *ptr, uint8_t mask) :
ptr{ptr}, mask{mask} {}
uint8_t *ptr;
uint8_t mask;
};
Here are the two types of operator
:
constexpr bool operator(std::size_t index) const
{
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
reference operator(std::size_t index)
{
_throw_if_too_large(index);
return reference{&_bit_container[index / CHAR_BIT],
static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}
Note that the constexpr
can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset
.
Add tests for operator
Here are the tests I addeed for the new operator
:
void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
constexpr bitpattern<23> pattern{0x2b64};
constexpr bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
constexpr bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
bitpattern<23> pattern{0x2b64};
bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
$endgroup$
add a comment |
$begingroup$
not directly answering your question, but just a notice:
I would say the more elegant way would be just extending the std::bitset
and add the extra methods you need, for ex. to_bytes()
:
template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
using byte_t = uint8_t;
static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
using bytes_t = std::array<byte_t, num_bytes>;
// declare approprite constructors and forward to the base class
// using base class implementation
// declare the extra functions you need, for ex.
// (this is not the efficienst method, but just for demonstration)
bytes_t to_bytes() const noexcept
{
bytes_t bytes;
for (size_t bix = 0; bix < num_bytes; bix++)
{
byte b = 0;
for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
if (this->operator (bix*8 + bitix))
b |= (0x01 << bitix);
bytes[bix] = b;
}
return bytes;
}
};
Another way would be stay at std::bitset
and using the appropriate non-class utility functions, for ex:
template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);
This way (1. or 2.) you can take advantage of the functionalities std::bitset
already offers.
$endgroup$
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210631%2fc-data-type-to-store-and-manipulate-individual-bits%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here are some things that may help you improve your program.
Use all required #include
s
The templated class uses CHAR_BIT
but is missing this line that provides the definition:
#include <climits>
Eliminate unused variables
The variable input
in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.
Be careful with naming
I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common
for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.
Keep maintaining the tests
The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.
Let the compiler generate the empty constructor
Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:
bitpattern() = default;
The intent is a bit more clear in my opinion.
Consider adding some constructors
At the moment this code won't compile:
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<22> pattern2(input);
bitpattern<24> pattern3(pattern2);
It would be nice to have the ability to create longer bit patterns from smaller ones.
It would also be nice to provide constexpr
constructors for patterns like this:
constexpr bitpattern<23> pattern{0x6423};
Here's a way to do that:
constexpr bitpattern(unsigned long long val)
{
for (std::size_t i=0; i < ByteCount; ++i) {
_bit_container[i] = val & 0xff;
val >>= 8;
}
}
Note that this uses for
loop in a constexpr
function and uses the operator
on the std::array
and so requires C++17 or later.
Consider adding operator
The std::bitset
uses std::bitset::reference
to enable operator
. You could probably do the same. Note that there are two flavors; one is constexpr
and returns an actual bool
and the other returns a reference
object. Here's one way to do that. First, here's the reference
class which is in the public
section of the bitpattern
class:
class reference {
friend class bitpattern<bit_count>;
public:
reference& operator=(bool x) {
if (x) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
reference(); // leave undefined
reference& operator=(const reference& x) {
bool bit{x};
if (bit) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
~reference() = default;
operator bool() const {
return *ptr & mask;
}
bool operator~() const {
return !(*ptr & mask);
}
reference& flip() {
*ptr ^= mask;
return *this;
}
private:
reference(uint8_t *ptr, uint8_t mask) :
ptr{ptr}, mask{mask} {}
uint8_t *ptr;
uint8_t mask;
};
Here are the two types of operator
:
constexpr bool operator(std::size_t index) const
{
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
reference operator(std::size_t index)
{
_throw_if_too_large(index);
return reference{&_bit_container[index / CHAR_BIT],
static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}
Note that the constexpr
can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset
.
Add tests for operator
Here are the tests I addeed for the new operator
:
void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
constexpr bitpattern<23> pattern{0x2b64};
constexpr bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
constexpr bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
bitpattern<23> pattern{0x2b64};
bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
$endgroup$
add a comment |
$begingroup$
Here are some things that may help you improve your program.
Use all required #include
s
The templated class uses CHAR_BIT
but is missing this line that provides the definition:
#include <climits>
Eliminate unused variables
The variable input
in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.
Be careful with naming
I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common
for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.
Keep maintaining the tests
The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.
Let the compiler generate the empty constructor
Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:
bitpattern() = default;
The intent is a bit more clear in my opinion.
Consider adding some constructors
At the moment this code won't compile:
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<22> pattern2(input);
bitpattern<24> pattern3(pattern2);
It would be nice to have the ability to create longer bit patterns from smaller ones.
It would also be nice to provide constexpr
constructors for patterns like this:
constexpr bitpattern<23> pattern{0x6423};
Here's a way to do that:
constexpr bitpattern(unsigned long long val)
{
for (std::size_t i=0; i < ByteCount; ++i) {
_bit_container[i] = val & 0xff;
val >>= 8;
}
}
Note that this uses for
loop in a constexpr
function and uses the operator
on the std::array
and so requires C++17 or later.
Consider adding operator
The std::bitset
uses std::bitset::reference
to enable operator
. You could probably do the same. Note that there are two flavors; one is constexpr
and returns an actual bool
and the other returns a reference
object. Here's one way to do that. First, here's the reference
class which is in the public
section of the bitpattern
class:
class reference {
friend class bitpattern<bit_count>;
public:
reference& operator=(bool x) {
if (x) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
reference(); // leave undefined
reference& operator=(const reference& x) {
bool bit{x};
if (bit) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
~reference() = default;
operator bool() const {
return *ptr & mask;
}
bool operator~() const {
return !(*ptr & mask);
}
reference& flip() {
*ptr ^= mask;
return *this;
}
private:
reference(uint8_t *ptr, uint8_t mask) :
ptr{ptr}, mask{mask} {}
uint8_t *ptr;
uint8_t mask;
};
Here are the two types of operator
:
constexpr bool operator(std::size_t index) const
{
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
reference operator(std::size_t index)
{
_throw_if_too_large(index);
return reference{&_bit_container[index / CHAR_BIT],
static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}
Note that the constexpr
can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset
.
Add tests for operator
Here are the tests I addeed for the new operator
:
void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
constexpr bitpattern<23> pattern{0x2b64};
constexpr bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
constexpr bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
bitpattern<23> pattern{0x2b64};
bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
$endgroup$
add a comment |
$begingroup$
Here are some things that may help you improve your program.
Use all required #include
s
The templated class uses CHAR_BIT
but is missing this line that provides the definition:
#include <climits>
Eliminate unused variables
The variable input
in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.
Be careful with naming
I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common
for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.
Keep maintaining the tests
The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.
Let the compiler generate the empty constructor
Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:
bitpattern() = default;
The intent is a bit more clear in my opinion.
Consider adding some constructors
At the moment this code won't compile:
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<22> pattern2(input);
bitpattern<24> pattern3(pattern2);
It would be nice to have the ability to create longer bit patterns from smaller ones.
It would also be nice to provide constexpr
constructors for patterns like this:
constexpr bitpattern<23> pattern{0x6423};
Here's a way to do that:
constexpr bitpattern(unsigned long long val)
{
for (std::size_t i=0; i < ByteCount; ++i) {
_bit_container[i] = val & 0xff;
val >>= 8;
}
}
Note that this uses for
loop in a constexpr
function and uses the operator
on the std::array
and so requires C++17 or later.
Consider adding operator
The std::bitset
uses std::bitset::reference
to enable operator
. You could probably do the same. Note that there are two flavors; one is constexpr
and returns an actual bool
and the other returns a reference
object. Here's one way to do that. First, here's the reference
class which is in the public
section of the bitpattern
class:
class reference {
friend class bitpattern<bit_count>;
public:
reference& operator=(bool x) {
if (x) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
reference(); // leave undefined
reference& operator=(const reference& x) {
bool bit{x};
if (bit) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
~reference() = default;
operator bool() const {
return *ptr & mask;
}
bool operator~() const {
return !(*ptr & mask);
}
reference& flip() {
*ptr ^= mask;
return *this;
}
private:
reference(uint8_t *ptr, uint8_t mask) :
ptr{ptr}, mask{mask} {}
uint8_t *ptr;
uint8_t mask;
};
Here are the two types of operator
:
constexpr bool operator(std::size_t index) const
{
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
reference operator(std::size_t index)
{
_throw_if_too_large(index);
return reference{&_bit_container[index / CHAR_BIT],
static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}
Note that the constexpr
can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset
.
Add tests for operator
Here are the tests I addeed for the new operator
:
void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
constexpr bitpattern<23> pattern{0x2b64};
constexpr bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
constexpr bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
bitpattern<23> pattern{0x2b64};
bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
$endgroup$
Here are some things that may help you improve your program.
Use all required #include
s
The templated class uses CHAR_BIT
but is missing this line that provides the definition:
#include <climits>
Eliminate unused variables
The variable input
in several tests in your code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.
Be careful with naming
I'm not sure how useful it is to take care to wrap things into a namespace, but then use the name common
for it. It isn't necessarily wrong, but it's worth pondering whether there's a better, more apt name for the namespace.
Keep maintaining the tests
The tests are quite good. I was able to translate them all into the standard, non-Microsoft CppUnit in a few minutes. All tests passed on my 64-bit Linux box using gcc.
Let the compiler generate the empty constructor
Instead of explicitly writing the empty constructor, explicitly tell the compiler to construct it instead:
bitpattern() = default;
The intent is a bit more clear in my opinion.
Consider adding some constructors
At the moment this code won't compile:
std::array<uint8_t, 3> input = { 0b0010'0011, 0b0000'0001, 0b0110'0001 };
bitpattern<24> pattern1(input);
bitpattern<22> pattern2(input);
bitpattern<24> pattern3(pattern2);
It would be nice to have the ability to create longer bit patterns from smaller ones.
It would also be nice to provide constexpr
constructors for patterns like this:
constexpr bitpattern<23> pattern{0x6423};
Here's a way to do that:
constexpr bitpattern(unsigned long long val)
{
for (std::size_t i=0; i < ByteCount; ++i) {
_bit_container[i] = val & 0xff;
val >>= 8;
}
}
Note that this uses for
loop in a constexpr
function and uses the operator
on the std::array
and so requires C++17 or later.
Consider adding operator
The std::bitset
uses std::bitset::reference
to enable operator
. You could probably do the same. Note that there are two flavors; one is constexpr
and returns an actual bool
and the other returns a reference
object. Here's one way to do that. First, here's the reference
class which is in the public
section of the bitpattern
class:
class reference {
friend class bitpattern<bit_count>;
public:
reference& operator=(bool x) {
if (x) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
reference(); // leave undefined
reference& operator=(const reference& x) {
bool bit{x};
if (bit) {
*ptr |= mask;
} else {
*ptr &= ~mask;
}
return *this;
}
~reference() = default;
operator bool() const {
return *ptr & mask;
}
bool operator~() const {
return !(*ptr & mask);
}
reference& flip() {
*ptr ^= mask;
return *this;
}
private:
reference(uint8_t *ptr, uint8_t mask) :
ptr{ptr}, mask{mask} {}
uint8_t *ptr;
uint8_t mask;
};
Here are the two types of operator
:
constexpr bool operator(std::size_t index) const
{
return _bit_container[index / CHAR_BIT] & (1u << (index % CHAR_BIT));
}
reference operator(std::size_t index)
{
_throw_if_too_large(index);
return reference{&_bit_container[index / CHAR_BIT],
static_cast<uint8_t>(1 << (index % CHAR_BIT))};
}
Note that the constexpr
can't throw, so providing an out-of-range index is simply undefined behavior as with std::bitset
.
Add tests for operator
Here are the tests I addeed for the new operator
:
void ConstexprIndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
constexpr bitpattern<23> pattern{0x2b64};
constexpr bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
constexpr bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
void IndexOperatorReturnsTheValueOfTheSpecifiedBit()
{
bitpattern<23> pattern{0x2b64};
bool is_set =
pattern[2] &&
pattern[5] &&
pattern[6] &&
pattern[8] &&
pattern[9] &&
pattern[11] &&
pattern[13];
bool is_not_set =
!pattern[0] &&
!pattern[1] &&
!pattern[3] &&
!pattern[4] &&
!pattern[7] &&
!pattern[10] &&
!pattern[12] &&
!pattern[14] &&
!pattern[15];
CPPUNIT_ASSERT(is_set && is_not_set);
}
answered Dec 31 '18 at 17:02
EdwardEdward
46.7k378212
46.7k378212
add a comment |
add a comment |
$begingroup$
not directly answering your question, but just a notice:
I would say the more elegant way would be just extending the std::bitset
and add the extra methods you need, for ex. to_bytes()
:
template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
using byte_t = uint8_t;
static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
using bytes_t = std::array<byte_t, num_bytes>;
// declare approprite constructors and forward to the base class
// using base class implementation
// declare the extra functions you need, for ex.
// (this is not the efficienst method, but just for demonstration)
bytes_t to_bytes() const noexcept
{
bytes_t bytes;
for (size_t bix = 0; bix < num_bytes; bix++)
{
byte b = 0;
for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
if (this->operator (bix*8 + bitix))
b |= (0x01 << bitix);
bytes[bix] = b;
}
return bytes;
}
};
Another way would be stay at std::bitset
and using the appropriate non-class utility functions, for ex:
template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);
This way (1. or 2.) you can take advantage of the functionalities std::bitset
already offers.
$endgroup$
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
add a comment |
$begingroup$
not directly answering your question, but just a notice:
I would say the more elegant way would be just extending the std::bitset
and add the extra methods you need, for ex. to_bytes()
:
template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
using byte_t = uint8_t;
static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
using bytes_t = std::array<byte_t, num_bytes>;
// declare approprite constructors and forward to the base class
// using base class implementation
// declare the extra functions you need, for ex.
// (this is not the efficienst method, but just for demonstration)
bytes_t to_bytes() const noexcept
{
bytes_t bytes;
for (size_t bix = 0; bix < num_bytes; bix++)
{
byte b = 0;
for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
if (this->operator (bix*8 + bitix))
b |= (0x01 << bitix);
bytes[bix] = b;
}
return bytes;
}
};
Another way would be stay at std::bitset
and using the appropriate non-class utility functions, for ex:
template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);
This way (1. or 2.) you can take advantage of the functionalities std::bitset
already offers.
$endgroup$
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
add a comment |
$begingroup$
not directly answering your question, but just a notice:
I would say the more elegant way would be just extending the std::bitset
and add the extra methods you need, for ex. to_bytes()
:
template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
using byte_t = uint8_t;
static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
using bytes_t = std::array<byte_t, num_bytes>;
// declare approprite constructors and forward to the base class
// using base class implementation
// declare the extra functions you need, for ex.
// (this is not the efficienst method, but just for demonstration)
bytes_t to_bytes() const noexcept
{
bytes_t bytes;
for (size_t bix = 0; bix < num_bytes; bix++)
{
byte b = 0;
for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
if (this->operator (bix*8 + bitix))
b |= (0x01 << bitix);
bytes[bix] = b;
}
return bytes;
}
};
Another way would be stay at std::bitset
and using the appropriate non-class utility functions, for ex:
template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);
This way (1. or 2.) you can take advantage of the functionalities std::bitset
already offers.
$endgroup$
not directly answering your question, but just a notice:
I would say the more elegant way would be just extending the std::bitset
and add the extra methods you need, for ex. to_bytes()
:
template <size_t N>
class bitpattern : public std::bitset<N>
{
public:
using byte_t = uint8_t;
static constexpr size_t num_bytes = N/8 + ((N % 8 == 0) ? 0 : 1);
using bytes_t = std::array<byte_t, num_bytes>;
// declare approprite constructors and forward to the base class
// using base class implementation
// declare the extra functions you need, for ex.
// (this is not the efficienst method, but just for demonstration)
bytes_t to_bytes() const noexcept
{
bytes_t bytes;
for (size_t bix = 0; bix < num_bytes; bix++)
{
byte b = 0;
for (size_t bitix = 0; (bitix<8) && (bix*8+bitix < N); bitix++)
if (this->operator (bix*8 + bitix))
b |= (0x01 << bitix);
bytes[bix] = b;
}
return bytes;
}
};
Another way would be stay at std::bitset
and using the appropriate non-class utility functions, for ex:
template <size_t N>
std::vector<uint8_t> to_bytes(const std::bitset<N>&);
This way (1. or 2.) you can take advantage of the functionalities std::bitset
already offers.
edited Dec 31 '18 at 18:24
Sᴀᴍ Onᴇᴌᴀ
9,55562164
9,55562164
answered Dec 31 '18 at 17:54
StPiereStPiere
1713
1713
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
add a comment |
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
$begingroup$
Good answer. I think it would be interesting to compare the two approaches for efficiency.
$endgroup$
– Edward
Dec 31 '18 at 18:38
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210631%2fc-data-type-to-store-and-manipulate-individual-bits%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown