C++ data type to store and manipulate individual bits
1
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 onceinstead 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
getwhile the corresponding method ofstd::bitsetis namedtest. I usedgetas 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::bitsetthat 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
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
1
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 onceinstead 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
getwhile the corresponding method ofstd::bitsetis namedtest. I usedgetas 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::bitsetthat 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
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
1
1
1
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 onceinstead 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
getwhile the corresponding method ofstd::bitsetis namedtest. I usedgetas 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::bitsetthat 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
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 onceinstead 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
getwhile the corresponding method ofstd::bitsetis namedtest. I usedgetas 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::bitsetthat 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
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 mins ago
ackh
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 mins ago
ackh
1062
asked 7 mins ago
ackh
1062
1062
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
ackh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
active
oldest
votes
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
});
}
});
ackh is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
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
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
ackh is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
ackh is a new contributor. Be nice, and check out our Code of Conduct.
ackh is a new contributor. Be nice, and check out our Code of Conduct.
ackh is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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
