Per feedback from here, below is the updated bitvector class.
The class was renamed from binary_register to bitvector so as to be more meaningful in context to C++.
Updated some of the class nomenclature to be more inline with standard library nomenclature. For example, the value_type was set to the bit width of the words used with the encapsulated vector.
Added a class to handle the text radix input.
Updated the class to use specific width integrals. The clarification provided was much appreciated.
The Text and Text_Stream aliases are retained. The reason being that within the greater project this is used in, there is a need to ensure character strings are managed consistently. The type aliasing is there to make sure any changes are consistent in the project. This maybe able to change in the future, with the inclusion of string_views. But there is a learning curve there that I would need to tackle first. Alternatives or other suggestions are always welcome! The less deviation from the standard library the better.
The use of both bit and word manipulation is also retained. The reason is that the class is intended to abstract away binary manipulation from other classes that make use of bitvector. Specifically, when using this class to create a whole number class. The added complexity of bit manipulation, made the other code unnecessarily complex, and hard to follow. Other standard library solutions like bitset, valarray, vector, etc., didn’t quite meet the need without additional abstraction.
Thanks again for the help!
bitvector.h
#include <bitset>
#include <limits>
#include <vector>
#include "../support_files/Type_Defines.h"
namespace Olly {
/********************************************************************************************/
//
// 'bitvector' class
//
// The bitvector class implements a series of unint32_t elements within a
// std::vector.
//
// Support for all of the binary operation is provides, along with binary
// based mathematical operations.
//
/********************************************************************************************/
class bitvector {
public:
using word_t = uint32_t;
using double_word_t = uint64_t;
static const word_t mask = ~word_t(0);
static const word_t value_type = std::numeric_limits<word_t>::digits;
bitvector();
bitvector(const Text& value, word_t base = 10);
bitvector(const Text& value, Text base = "10");
bitvector(const std::size_t& size, word_t value);
explicit
bitvector(const std::size_t& size);
virtual ~bitvector();
bitvector(bitvector&& obj) = default;
bitvector(const bitvector& obj) = default;
bitvector& operator=(bitvector&& obj) = default;
bitvector& operator=(const bitvector& obj) = default;
friend void swap(bitvector& first, bitvector& second);
operator bool() const;
bool is() const; // bool conversion.
bool all() const; // bool test for all bits being set to 1.
std::size_t count() const; // The count of bits set to 1.
std::size_t lead_bit() const; // Return the lead bit.
std::size_t last_bit() const; // Return the last bit.
word_t lead_word() const; // Return the leading bitvector.
word_t last_word() const; // Return the last bitvector.
bool at_bit(std::size_t index) const; // Return the value of a bit at the index.
word_t& at_word(std::size_t index); // Return the word_t at the indexed bitvector.
word_t at_word(std::size_t index) const;
Text to_string() const; // Return a string representation at radix 10.
Text to_string(word_t base) const; // Return a string representation at radix 'base'.
void to_string(Text_Stream& stream) const; // Send a string representation to a stream_type.
std::size_t size_bits() const; // Get the total size in bits of the bitvector.
std::size_t size_words() const; // Get the total size of words in the bitvector.
bitvector& resize_words(std::size_t size); // Resize the bitvector to 'size' number of elements.
bitvector& resize_words(std::size_t size, word_t n);
bitvector& set(); // Set all bits to true.
bitvector& set(std::size_t index); // Set a bit at 'index' to true.
bitvector& reset(); // Set all bits to false.
bitvector& reset(std::size_t index); // Set a bit at 'index' to false.
bitvector& flip(); // Flip the truth of every bit in the bitvector.
bitvector& flip(std::size_t index); // Flip the truth of a bit at 'index'.
bool operator==(const bitvector& b) const;
bool operator!=(const bitvector& b) const;
std::partial_ordering operator<=>(const bitvector& b) const;
bitvector& operator&=(const bitvector& other);
bitvector& operator|=(const bitvector& other);
bitvector& operator^=(const bitvector& other);
bitvector operator&(const bitvector& b) const;
bitvector operator|(const bitvector& b) const;
bitvector operator^(const bitvector& b) const;
bitvector operator~() const;
friend bitvector operator&(bitvector&& a, const bitvector& b);
friend bitvector operator|(bitvector&& a, const bitvector& b);
friend bitvector operator^(bitvector&& a, const bitvector& b);
bitvector& operator<<=(std::size_t index);
bitvector& operator>>=(std::size_t index);
bitvector operator<<(std::size_t index) const;
bitvector operator>>(std::size_t index) const;
friend bitvector operator<<(bitvector&& a, std::size_t index);
friend bitvector operator>>(bitvector&& a, std::size_t index);
bitvector& operator+=(const bitvector& other);
bitvector& operator-=(const bitvector& other);
bitvector& operator*=(const bitvector& other);
bitvector& operator/=(const bitvector& other);
bitvector& operator%=(const bitvector& other);
bitvector operator+(const bitvector& b) const;
bitvector operator-(const bitvector& b) const;
bitvector operator*(const bitvector& b) const;
bitvector operator/(const bitvector& b) const;
bitvector operator%(const bitvector& b) const;
friend bitvector operator+(bitvector&& a, const bitvector& b);
friend bitvector operator-(bitvector&& a, const bitvector& b);
friend bitvector operator*(bitvector&& a, const bitvector& b);
friend bitvector operator/(bitvector&& a, const bitvector& b);
friend bitvector operator%(bitvector&& a, const bitvector& b);
bitvector& operator++();
bitvector operator++(int);
bitvector& operator--();
bitvector operator--(int);
template<typename I>
word_t to_integral() const; // Cast the bitvector to an integral of type T.
bitvector bin_comp() const; // Return the binary compliment of the bitvector.
// Get both the qotient and the remainder of the regester divided by 'other'.
void div_rem(bitvector& other, bitvector& qot, bitvector& rem) const;
bitvector& trim(); // Remove all trailing zeros, from the bitvector.
// But leave atleast one bitvector, even if a value of zero.
private:
typedef std::bitset<value_type> single_prc_bitset;
static const word_t ONE = 1;
std::vector<word_t> _vec;
void get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const;
void divide_remainder(const bitvector& x, bitvector y, bitvector& q, bitvector& r) const;
Text get_string(word_t base) const;
void left_shift_bits(std::size_t& word_t_index, std::size_t& bit_index);
void right_shift_bits(std::size_t& word_t_index, std::size_t& bit_index);
void init_text_input(const Text& value, word_t base_radix);
};
/********************************************************************************************/
//
// 'bitvector' template implimentation
//
/********************************************************************************************/
template<typename I>
bitvector::word_t bitvector::to_integral() const {
static_assert(std::numeric_limits<I>::is_integer, "Integral required.");
if (!_vec.empty()) {
auto bits_of_I = std::numeric_limits<I>::digits;
if (bits_of_I >= value_type && !_vec.empty()) {
return I(_vec.front());
}
I n = 0;
for (int i = value_type / bits_of_I; i >= 0; i -= 1) {
n <<= bits_of_I;
n += at_word(i);
}
return static_cast<word_t>(n);
}
return I(0);
}
}
bitvector.cpp
#include "bitvector.h"
namespace Olly {
bitvector::bitvector() : _vec(1, 0) {
}
bitvector::bitvector(const std::size_t& size) : _vec((size > 0 ? size : 1), 0) {
}
bitvector::bitvector(const std::size_t& size, word_t value) : _vec((size > 0 ? size : 1), value) {
}
bitvector::bitvector(const Text& value, word_t base) : _vec(1, 0) {
init_text_input(value, base);
}
bitvector::bitvector(const Text& value, Text base) : _vec(1, 0) {
word_t base_radix = to<word_t>(base);
init_text_input(value, base_radix);
}
bitvector::~bitvector() {
}
void swap(bitvector& left, bitvector& right) {
bitvector temp = std::move(left);
left = std::move(right);
right = std::move(temp);
}
bitvector::operator bool() const {
return is();
}
bool bitvector::is() const {
for (auto i : _vec) {
if (i) {
return true;
}
}
return false;
}
bool bitvector::all() const {
for (auto i : _vec) {
if (i != mask) {
return false;
}
}
return true;
}
std::size_t bitvector::count() const {
std::size_t count = 0;
for (const auto i : _vec) {
auto n = i;
while (n > 0) {
if (n & 1) {
count += 1;
}
n >>= 1;
}
}
return count;
}
std::size_t bitvector::lead_bit() const {
std::size_t word_t_index = _vec.size();
bitvector::word_t mask = (ONE << (value_type - ONE));
for (auto i = _vec.crbegin(); i != _vec.crend(); ++i) {
word_t_index -= 1;
auto a = *i;
std::size_t bit_index = value_type;
while (a) {
if (a & mask) {
return bit_index + (word_t_index * value_type);
}
a <<= 1;
bit_index -= 1;
}
}
return 0;
}
std::size_t bitvector::last_bit() const {
std::size_t word_t_index = 0;
bitvector::word_t mask = 1;
for (auto i = _vec.cbegin(); i != _vec.cend(); ++i) {
auto a = *i;
std::size_t bit_index = 1;
while (a) {
if (a & mask) {
return bit_index + (word_t_index * value_type);
}
a >>= 1;
bit_index += 1;
}
word_t_index += 1;
}
return 0;
}
bitvector::word_t bitvector::lead_word() const {
if (_vec.empty()) {
return word_t(0);
}
return _vec.back();
}
bitvector::word_t bitvector::last_word() const {
if (_vec.empty()) {
return word_t(0);
}
return _vec.front();
}
bool bitvector::at_bit(std::size_t index) const {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index < _vec.size()) {
return _vec[reg_index] & (ONE << (bit_index - ONE));
}
return false;
}
bitvector::word_t& bitvector::at_word(std::size_t index) {
if (index >= _vec.size()) {
_vec.resize(index + 1, 0);
}
return _vec[index];
}
bitvector::word_t bitvector::at_word(std::size_t index) const {
if (index < _vec.size()) {
return _vec[index];
}
return word_t(0);
}
Text bitvector::to_string() const {
return to_string(10);
}
Text bitvector::to_string(word_t base) const {
if (base > 360) {
return "Radix must be between 0 and 360.";
}
if (base == 0) {
Text_Stream stream;
to_string(stream);
return stream.str();
}
if (!is()) {
return "0";
}
return get_string(base);
}
void bitvector::to_string(Text_Stream& stream) const {
std::size_t i = _vec.size();
while (i-- > 1) {
stream << "word_t[" << i << "] = " << single_prc_bitset(_vec[i]).to_string() << "\n";
}
stream << "word_t[" << 0 << "] = " << single_prc_bitset(_vec[i]).to_string();
}
std::size_t bitvector::size_bits() const {
return _vec.size() * value_type;
}
std::size_t bitvector::size_words() const {
return _vec.size();
}
bitvector& bitvector::resize_words(std::size_t size) {
_vec.resize(size);
return *this;
}
bitvector& bitvector::resize_words(std::size_t size, word_t n) {
_vec.resize(size, n);
return *this;
}
bitvector& bitvector::set() {
for (auto i = _vec.begin(); i != _vec.end(); ++i) {
*i = mask;
}
return *this;
}
bitvector& bitvector::set(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _vec.size()) {
_vec.resize(reg_index + 1, 0);
}
_vec[reg_index] |= (ONE << (bit_index - ONE));
return *this;
}
bitvector& bitvector::reset() {
for (std::size_t i = 0, end = _vec.size(); i < end; i += 1) {
_vec[i] = word_t(0);
}
return *this;
}
bitvector& bitvector::reset(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _vec.size()) {
_vec.resize(reg_index + 1, 0);
}
_vec[reg_index] &= ~(1 << (bit_index - 1));
return *this;
}
bitvector& bitvector::flip() {
for (std::size_t i = 0, end = _vec.size(); i < end; i += 1) {
_vec[i] = ~_vec[i];
}
return *this;
}
bitvector& bitvector::flip(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _vec.size()) {
_vec.resize(reg_index + 1, 0);
}
_vec[reg_index] ^= (1 << (bit_index - 1));
return *this;
}
bool bitvector::operator==(const bitvector& b) const {
return operator<=>(b) == std::partial_ordering::equivalent;
}
bool bitvector::operator!=(const bitvector& b) const {
return operator<=>(b) != std::partial_ordering::equivalent;
}
std::partial_ordering bitvector::operator<=>(const bitvector& b) const {
std::size_t i = size_words() > b.size_words() ? size_words() : b.size_words();
while (i-- > 0) {
auto x = at_word(i);
auto y = b.at_word(i);
if (x > y) {
return std::partial_ordering::greater;
}
if (x < y) {
return std::partial_ordering::less;
}
}
return std::partial_ordering::equivalent;
}
bitvector& bitvector::operator&=(const bitvector& other) {
if (_vec.size() < other._vec.size()) {
_vec.resize(other._vec.size(), 0);
}
for (std::size_t i = 0, end = _vec.size(); i < end; i += 1) {
_vec[i] &= other.at_word(i);
}
return *this;
}
bitvector& bitvector::operator|=(const bitvector& other) {
if (_vec.size() < other._vec.size()) {
_vec.resize(other._vec.size(), 0);
}
for (std::size_t i = 0, end = _vec.size(); i < end; i += 1) {
_vec[i] |= other.at_word(i);
}
return *this;
}
bitvector& bitvector::operator^=(const bitvector& other) {
if (_vec.size() < other._vec.size()) {
_vec.resize(other._vec.size(), 0);
}
for (std::size_t i = 0, end = _vec.size(); i < end; i += 1) {
_vec[i] ^= other.at_word(i);
}
return *this;
}
bitvector bitvector::operator&(const bitvector& b) const {
bitvector a(*this);
a &= b;
return a;
}
bitvector bitvector::operator|(const bitvector& b) const {
bitvector a(*this);
a |= b;
return a;
}
bitvector bitvector::operator^(const bitvector& b) const {
bitvector a(*this);
a ^= b;
return a;
}
bitvector bitvector::operator~() const {
bitvector a = *this;
for (std::size_t i = 0, end = a._vec.size(); i < end; i += 1) {
a._vec[i] = ~a._vec[i];
}
return a;
}
bitvector operator&(bitvector&& a, const bitvector& b) {
return a &= b;
}
bitvector operator|(bitvector&& a, const bitvector& b) {
return a |= b;
}
bitvector operator^(bitvector&& a, const bitvector& b) {
return a ^= b;
}
bitvector& bitvector::operator<<=(std::size_t index) {
std::size_t word_t_index, bit_index;
get_shift_index(index, word_t_index, bit_index);
if (word_t_index) {
_vec.insert(_vec.begin(), word_t_index, 0);
}
if (bit_index) {
left_shift_bits(word_t_index, bit_index);
}
return *this;
}
bitvector& bitvector::operator>>=(std::size_t index) {
std::size_t word_t_index, bit_index;
get_shift_index(index, word_t_index, bit_index);
if (word_t_index) {
if (word_t_index < _vec.size()) {
_vec.erase(_vec.begin(), _vec.begin() + word_t_index);
}
else {
for (auto i = _vec.begin(), end = _vec.end(); i != end; ++i) {
*i = 0;
}
return *this;
}
}
if (bit_index) {
right_shift_bits(word_t_index, bit_index);
}
return *this;
}
bitvector bitvector::operator<<(std::size_t index) const {
bitvector a(*this);
a <<= index;
return a;
}
bitvector bitvector::operator>>(std::size_t index) const {
bitvector a(*this);
a >>= index;
return a;
}
bitvector operator<<(bitvector&& a, std::size_t index) {
return a <<= index;
}
bitvector operator>>(bitvector&& a, std::size_t index) {
return a >>= index;
}
bitvector& bitvector::operator+=(const bitvector& other) {
bitvector b(other);
bitvector c;
while (b.is()) {
c = (*this & b) << 1ull;
*this ^= b;
b = c;
}
return *this;
}
bitvector& bitvector::operator-=(const bitvector& other) {
if (other >= *this) {
return reset();
}
bitvector b = other;
if (b.size_words() < size_words()) {
b._vec.resize(size_words(), 0);
}
b = b.bin_comp();
b._vec.push_back(0); // Add a word_t to handle the two's compliment overflow.
*this += b;
_vec.pop_back(); // Get rid of the two's compliment overflow.
return *this;
}
bitvector& bitvector::operator*=(const bitvector& other) {
*this = *this * other;
return *this;
}
bitvector& bitvector::operator/=(const bitvector& other) {
*this = *this / other;
return *this;
}
bitvector& bitvector::operator%=(const bitvector& other) {
*this = *this % other;
return *this;
}
bitvector bitvector::operator+(const bitvector& b) const {
bitvector a = *this;
a += b;
return a;
}
bitvector bitvector::operator-(const bitvector& b) const {
bitvector a = *this;
a -= b;
return a;
}
bitvector bitvector::operator*(const bitvector& b) const {
std::size_t count = 0;
bitvector x;
bitvector y = b;
while (y.is()) {
if (y.at_bit(1)) {
x += (*this << count);
}
count += 1;
y >>= 1;
}
return x;
}
bitvector bitvector::operator/(const bitvector& b) const {
bitvector q;
bitvector r = *this;
divide_remainder(*this, b, q, r);
return q;
}
bitvector bitvector::operator%(const bitvector& b) const {
bitvector q;
bitvector r = *this;
divide_remainder(*this, b, q, r);
return r;
}
bitvector operator+(bitvector&& a, const bitvector& b) {
return a += b;
}
bitvector operator-(bitvector&& a, const bitvector& b) {
return a -= b;
}
bitvector operator*(bitvector&& a, const bitvector& b) {
return a *= b;
}
bitvector operator/(bitvector&& a, const bitvector& b) {
return a /= b;
}
bitvector operator%(bitvector&& a, const bitvector& b) {
return a &= b;
}
bitvector& bitvector::operator++() {
bitvector one(1, 1);
operator+=(one);
return *this;
}
bitvector bitvector::operator++(int) {
bitvector a(*this);
operator++();
return a;
}
bitvector& bitvector::operator--() {
bitvector one(1, 1);
operator-=(one);
return *this;
}
bitvector bitvector::operator--(int) {
bitvector a(*this);
operator--();
return a;
}
bitvector bitvector::bin_comp() const {
bitvector a = ~*this;
bitvector one(1, 1);
a += one;
return a;
}
void bitvector::div_rem(bitvector& other, bitvector& qot, bitvector& rem) const {
rem = *this;
divide_remainder(*this, other, qot, rem);
}
bitvector& bitvector::trim() {
while (!_vec.empty() && _vec.back() == 0) {
_vec.pop_back();
}
if (_vec.empty()) {
_vec.push_back(0);
}
return *this;
}
void bitvector::get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const {
if (index) {
if (index >= value_type) {
reg_index = index / value_type;
bit_index = index % value_type;
if (!bit_index) {
--reg_index;
bit_index = value_type;
}
return;
}
reg_index = 0;
bit_index = index;
return;
}
reg_index = 0;
bit_index = 0;
}
void bitvector::divide_remainder(const bitvector& x, bitvector y, bitvector& q, bitvector& r) const {
if (!y.is() || !x.is() || x < y) {
return;
}
std::size_t lead_x = x.lead_bit();
std::size_t lead_y = y.lead_bit();
std::size_t bit_dif = (lead_x - lead_y);
y <<= bit_dif;
bit_dif += 2;
while (bit_dif-- > 1) {
if (r >= y) {
q.set(bit_dif);
r -= y;
}
y >>= 1;
}
}
Text bitvector::get_string(word_t base) const {
bitvector radix(1, base);
bitvector n = *this;
Text_Stream stream;
while (n.is()) {
bitvector q;
bitvector r = n;
divide_remainder(n, radix, q, r);
n = q;
stream << r.at_word(0);
}
Text res = stream.str();
std::reverse(res.begin(), res.end());
return res;
}
void bitvector::left_shift_bits(std::size_t& word_t_index, std::size_t& bit_index) {
std::size_t i = _vec.size();
_vec.push_back(0);
auto bit_mask = double_word_t(mask);
while (i-- > 0) {
auto buffer = double_word_t();
buffer |= double_word_t(_vec[i]);
buffer <<= bit_index;
_vec[i] = static_cast<word_t>(buffer & bit_mask);
buffer >>= value_type;
buffer |= double_word_t(_vec[i + 1]);
_vec[i + 1] = static_cast<word_t>(buffer);
}
if (_vec.back() == 0) {
_vec.pop_back();
}
}
void bitvector::right_shift_bits(std::size_t& word_t_index, std::size_t& bit_index) {
bool pop_back = word_t_index ? false : true;
if (word_t_index) {
word_t_index -= 1;
}
_vec.push_back(0);
auto inv_index = value_type - bit_index;
std::size_t end = (_vec.size() - 1);
auto bit_mask = double_word_t(mask);
for (std::size_t i = 0; i < end; i += 1) {
auto buffer = double_word_t();
buffer |= double_word_t(_vec[i + 1]);
buffer <<= inv_index;
_vec[i] >>= bit_index;
_vec[i] |= static_cast<word_t>(buffer & bit_mask);
}
_vec[end] >>= bit_index;
while (word_t_index-- > 0) {
_vec.push_back(0);
}
if (pop_back) {
_vec.pop_back();
}
}
void bitvector::init_text_input(const Text& value, word_t base_radix) {
bitvector radix(1, base_radix); // Define a bitvector to act as the radix.
for (auto i : value) { // Loop through each digit and add it to the bitvector.
Text digit_str = "";
digit_str.push_back(i);
bitvector::word_t n = to<word_t>(digit_str);
if (n < base_radix) {
bitvector digit(1, n);
operator*=(radix);
operator+=(digit);
}
}
}
}
binvectororbitvector? \$\endgroup\$bitvectorsorry for the typo. The class name had changed fromBinary_Register. Must have had "bin" stuck in the brain. \$\endgroup\$