Below is the updated binary mathematics class from the feedback provided here.
It was decided that the project should simply be written with an expectation of using C++20 as the minimum version to use.
The template was removed. Once removed I found there was a binary overflow happening in a bit shift that was masked by the template. Lesson learned. Make what you need now, and don’t worry about what you may need later.
Added friend overloads for move semantics on operators. Please let me know if additional changes are needed.
Converted the comp method to the <=> operator.
I had been under the impression that the compiler would automatically create the needed move, and assignment operator and constructor overloads. This post clarified the misunderstanding on my part.
I am keeping twos compliment. It is primarily used later as a method for confirming commutations done using other methods through tests. It really isn’t used otherwise.
There are additional classes for whole number, up through complex numbers. But I need to cascade what was learned here to them before I post them. If there is no additional feedback, I will create a new post for whole numbers next, and go from there.
note - If this wasn't the right way to follow up on the class, please let me know. :-)
binary_register.h
#include <bitset>
#include <limits>
#include <vector>
#include "../support_files/Type_Defines.h"
namespace Olly {
/********************************************************************************************/
//
// 'binary_register' class
//
// The binary_register class implements a series of binary registers sized to
// the integral type passed during to the template at definition.
//
// Support for all of the binary operation is provides, along with binary
// based mathematical operations. The implementation is little endian.
//
/********************************************************************************************/
class binary_register {
public:
#if _WIN32 || _WIN64
#if _WIN64
using Word = unsigned long int;
using Double_Word = unsigned long long int;
#else
using Word = unsigned int;
using Double_Word = unsigned long int;
#endif
#endif
#if __GNUC__
#if __x86_64__ || __ppc64__
using Word = unsigned long int;
using Double_Word = unsigned long long int;
#else
using Word = unsigned int;
using Double_Word = unsigned long int;
#endif
#endif
using Register = std::vector<Word>;
static const Word MASK = ~Word(0);
static const std::size_t BITS = std::numeric_limits<Word>::digits;
binary_register();
binary_register(const Text& value, Text base = "10");
binary_register(const std::size_t& size, Word value);
explicit
binary_register(const std::size_t& size);
virtual ~binary_register();
binary_register(binary_register&& obj) = default;
binary_register(const binary_register& obj) = default;
binary_register& operator=(binary_register&& obj) = default;
binary_register& operator=(const binary_register& obj) = default;
friend void swap(binary_register& first, binary_register& second);
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 lead_reg() const; // Return the leading register.
Word last_reg() const; // Return the last register.
bool at_bit(std::size_t index) const; // Return the value of a bit at the index.
Word& at_reg(std::size_t index); // Return the word at the indexed register.
Word at_reg(std::size_t index) const;
Text to_string() const; // Return a string representation at radix 10.
Text to_string(Word 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 register.
std::size_t size_regs() const; // Get the total size of words in the register.
binary_register& resize_regs(std::size_t size); // Resize the register to 'size' number of elements.
binary_register& resize_regs(std::size_t size, Word n);
binary_register& set(); // Set all bits to true.
binary_register& set(std::size_t index); // Set a bit at 'index' to true.
binary_register& reset(); // Set all bits to false.
binary_register& reset(std::size_t index); // Set a bit at 'index' to false.
binary_register& flip(); // Flip the truth of every bit in the register.
binary_register& flip(std::size_t index); // Flip the truth of a bit at 'index'.
bool operator==(const binary_register& b) const;
bool operator!=(const binary_register& b) const;
std::partial_ordering operator<=>(const binary_register& b) const;
binary_register& operator&=(const binary_register& other);
binary_register& operator|=(const binary_register& other);
binary_register& operator^=(const binary_register& other);
binary_register operator&(const binary_register& b) const;
binary_register operator|(const binary_register& b) const;
binary_register operator^(const binary_register& b) const;
binary_register operator~() const;
friend binary_register operator&(binary_register&& a, const binary_register& b);
friend binary_register operator|(binary_register&& a, const binary_register& b);
friend binary_register operator^(binary_register&& a, const binary_register& b);
binary_register& operator<<=(std::size_t index);
binary_register& operator>>=(std::size_t index);
binary_register operator<<(std::size_t index) const;
binary_register operator>>(std::size_t index) const;
friend binary_register operator<<(binary_register&& a, std::size_t index);
friend binary_register operator>>(binary_register&& a, std::size_t index);
binary_register& operator+=(const binary_register& other);
binary_register& operator-=(const binary_register& other);
binary_register& operator*=(const binary_register& other);
binary_register& operator/=(const binary_register& other);
binary_register& operator%=(const binary_register& other);
binary_register operator+(const binary_register& b) const;
binary_register operator-(const binary_register& b) const;
binary_register operator*(const binary_register& b) const;
binary_register operator/(const binary_register& b) const;
binary_register operator%(const binary_register& b) const;
friend binary_register operator+(binary_register&& a, const binary_register& b);
friend binary_register operator-(binary_register&& a, const binary_register& b);
friend binary_register operator*(binary_register&& a, const binary_register& b);
friend binary_register operator/(binary_register&& a, const binary_register& b);
friend binary_register operator%(binary_register&& a, const binary_register& b);
binary_register& operator++();
binary_register operator++(int);
binary_register& operator--();
binary_register operator--(int);
template<typename I>
Word to_integral() const; // Cast the register to an integral of type T.
binary_register bin_comp() const; // Return the binary compliment of the register.
// Get both the qotient and the remainder of the regester divided by 'other'.
void div_rem(binary_register& other, binary_register& qot, binary_register& rem) const;
binary_register& trim(); // Remove all trailing zeros, from the register.
// But leave atleast one register, even if a value of zero.
private:
typedef std::bitset<BITS> single_prc_bitset;
static const Word ONE = 1;
Register _reg;
void get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const;
void divide_remainder(const binary_register& x, binary_register y, binary_register& q, binary_register& r) const;
Text get_string(Word base) const;
void left_shift_bits(std::size_t& word_index, std::size_t& bit_index);
void right_shift_bits(std::size_t& word_index, std::size_t& bit_index);
};
/********************************************************************************************/
//
// 'binary_register' template implimentation
//
/********************************************************************************************/
template<typename I>
binary_register::Word binary_register::to_integral() const {
static_assert(std::numeric_limits<I>::is_integer, "Integral required.");
if (!_reg.empty()) {
auto bits_of_I = std::numeric_limits<I>::digits;
if (bits_of_I >= BITS && !_reg.empty()) {
return I(_reg.front());
}
I n = 0;
for (int i = BITS / bits_of_I; i >= 0; i -= 1) {
n <<= bits_of_I;
n += at_reg(i);
}
return static_cast<Word>(n);
}
return I(0);
}
}
binary_register.cpp
#include "binary_register.h"
namespace Olly {
binary_register::binary_register() : _reg(1, 0) {
}
binary_register::binary_register(const std::size_t& size) : _reg((size > 0 ? size : 1), 0) {
}
binary_register::binary_register(const std::size_t& size, Word value) : _reg((size > 0 ? size : 1), value) {
}
binary_register::binary_register(const Text& value, Text base) : _reg(1, 0) {
binary_register::Word base_radix = to<Word>(base); // Get the base radix to use.
binary_register radix(1, base_radix); // Define a binary_register to act as the radix.
for (auto i : value) { // Loop through each digit and add it to the binary_register.
Text digit_str = "";
digit_str.push_back(i);
binary_register::Word n = to<Word>(digit_str);
if (n < base_radix) {
binary_register digit(1, n);
operator*=(radix);
operator+=(digit);
}
}
}
binary_register::~binary_register() {
}
void swap(binary_register& left, binary_register& right) {
auto temp = std::move(left);
left = std::move(right);
right = std::move(temp);
}
bool binary_register::is() const {
for (auto i : _reg) {
if (i) {
return true;
}
}
return false;
}
bool binary_register::all() const {
for (auto i : _reg) {
if (i != MASK) {
return false;
}
}
return true;
}
std::size_t binary_register::count() const {
std::size_t count = 0;
for (const auto i : _reg) {
auto n = i;
while (n > 0) {
if (n & 1) {
count += 1;
}
n >>= 1;
}
}
return count;
}
std::size_t binary_register::lead_bit() const {
std::size_t word_index = _reg.size();
binary_register::Word mask = (ONE << (BITS - ONE));
for (auto i = _reg.crbegin(); i != _reg.crend(); ++i) {
word_index -= 1;
auto a = *i;
std::size_t bit_index = BITS;
while (a) {
if (a & mask) {
return bit_index + (word_index * BITS);
}
a <<= 1;
bit_index -= 1;
}
}
return 0;
}
std::size_t binary_register::last_bit() const {
std::size_t word_index = 0;
binary_register::Word mask = 1;
for (auto i = _reg.cbegin(); i != _reg.cend(); ++i) {
auto a = *i;
std::size_t bit_index = 1;
while (a) {
if (a & mask) {
return bit_index + (word_index * BITS);
}
a >>= 1;
bit_index += 1;
}
word_index += 1;
}
return 0;
}
binary_register::Word binary_register::lead_reg() const {
if (_reg.empty()) {
return Word(0);
}
return _reg.back();
}
binary_register::Word binary_register::last_reg() const {
if (_reg.empty()) {
return Word(0);
}
return _reg.front();
}
bool binary_register::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 < _reg.size()) {
return _reg[reg_index] & (ONE << (bit_index - ONE));
}
return false;
}
binary_register::Word& binary_register::at_reg(std::size_t index) {
if (index >= _reg.size()) {
_reg.resize(index + 1, 0);
}
return _reg[index];
}
binary_register::Word binary_register::at_reg(std::size_t index) const {
if (index < _reg.size()) {
return _reg[index];
}
return Word(0);
}
Text binary_register::to_string() const {
return to_string(10);
}
Text binary_register::to_string(Word 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 binary_register::to_string(Text_Stream& stream) const {
std::size_t i = _reg.size();
while (i-- > 1) {
stream << "word[" << i << "] = " << single_prc_bitset(_reg[i]).to_string() << "\n";
}
stream << "word[" << 0 << "] = " << single_prc_bitset(_reg[i]).to_string();
}
std::size_t binary_register::size_bits() const {
return _reg.size() * BITS;
}
std::size_t binary_register::size_regs() const {
return _reg.size();
}
binary_register& binary_register::resize_regs(std::size_t size) {
_reg.resize(size);
return *this;
}
binary_register& binary_register::resize_regs(std::size_t size, Word n) {
_reg.resize(size, n);
return *this;
}
binary_register& binary_register::set() {
for (auto i = _reg.begin(); i != _reg.end(); ++i) {
*i = MASK;
}
return *this;
}
binary_register& binary_register::set(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _reg.size()) {
_reg.resize(reg_index + 1, 0);
}
_reg[reg_index] |= (ONE << (bit_index - ONE));
return *this;
}
binary_register& binary_register::reset() {
for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
_reg[i] = Word(0);
}
return *this;
}
binary_register& binary_register::reset(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _reg.size()) {
_reg.resize(reg_index + 1, 0);
}
_reg[reg_index] &= ~(1 << (bit_index - 1));
return *this;
}
binary_register& binary_register::flip() {
for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
_reg[i] = ~_reg[i];
}
return *this;
}
binary_register& binary_register::flip(std::size_t index) {
std::size_t reg_index, bit_index;
get_shift_index(index, reg_index, bit_index);
if (reg_index >= _reg.size()) {
_reg.resize(reg_index + 1, 0);
}
_reg[reg_index] ^= (1 << (bit_index - 1));
return *this;
}
bool binary_register::operator==(const binary_register& b) const {
return operator<=>(b) == std::partial_ordering::equivalent;
}
bool binary_register::operator!=(const binary_register& b) const {
return operator<=>(b) != std::partial_ordering::equivalent;
}
std::partial_ordering binary_register::operator<=>(const binary_register& b) const {
std::size_t i = size_regs() > b.size_regs() ? size_regs() : b.size_regs();
while (i-- > 0) {
auto x = at_reg(i);
auto y = b.at_reg(i);
if (x > y) {
return std::partial_ordering::greater;
}
if (x < y) {
return std::partial_ordering::less;
}
}
return std::partial_ordering::equivalent;
}
binary_register& binary_register::operator&=(const binary_register& other) {
if (_reg.size() < other._reg.size()) {
_reg.resize(other._reg.size(), 0);
}
for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
_reg[i] &= other.at_reg(i);
}
return *this;
}
binary_register& binary_register::operator|=(const binary_register& other) {
if (_reg.size() < other._reg.size()) {
_reg.resize(other._reg.size(), 0);
}
for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
_reg[i] |= other.at_reg(i);
}
return *this;
}
binary_register& binary_register::operator^=(const binary_register& other) {
if (_reg.size() < other._reg.size()) {
_reg.resize(other._reg.size(), 0);
}
for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
_reg[i] ^= other.at_reg(i);
}
return *this;
}
binary_register binary_register::operator&(const binary_register& b) const {
binary_register a(*this);
a &= b;
return a;
}
binary_register binary_register::operator|(const binary_register& b) const {
binary_register a(*this);
a |= b;
return a;
}
binary_register binary_register::operator^(const binary_register& b) const {
binary_register a(*this);
a ^= b;
return a;
}
binary_register binary_register::operator~() const {
binary_register a = *this;
for (std::size_t i = 0, end = a._reg.size(); i < end; i += 1) {
a._reg[i] = ~a._reg[i];
}
return a;
}
binary_register operator&(binary_register&& a, const binary_register& b) {
return a &= b;
}
binary_register operator|(binary_register&& a, const binary_register& b) {
return a |= b;
}
binary_register operator^(binary_register&& a, const binary_register& b) {
return a ^= b;
}
binary_register& binary_register::operator<<=(std::size_t index) {
std::size_t word_index, bit_index;
get_shift_index(index, word_index, bit_index);
if (word_index) {
_reg.insert(_reg.begin(), word_index, 0);
}
if (bit_index) {
left_shift_bits(word_index, bit_index);
}
return *this;
}
binary_register& binary_register::operator>>=(std::size_t index) {
std::size_t word_index, bit_index;
get_shift_index(index, word_index, bit_index);
if (word_index) {
if (word_index < _reg.size()) {
_reg.erase(_reg.begin(), _reg.begin() + word_index);
}
else {
for (auto i = _reg.begin(), end = _reg.end(); i != end; ++i) {
*i = 0;
}
return *this;
}
}
if (bit_index) {
right_shift_bits(word_index, bit_index);
}
return *this;
}
binary_register binary_register::operator<<(std::size_t index) const {
binary_register a(*this);
a <<= index;
return a;
}
binary_register binary_register::operator>>(std::size_t index) const {
binary_register a(*this);
a >>= index;
return a;
}
binary_register operator<<(binary_register&& a, std::size_t index) {
return a <<= index;
}
binary_register operator>>(binary_register&& a, std::size_t index) {
return a >>= index;
}
binary_register& binary_register::operator+=(const binary_register& other) {
binary_register b(other);
binary_register c;
while (b.is()) {
c = (*this & b) << 1;
*this ^= b;
b = c;
}
return *this;
}
binary_register& binary_register::operator-=(const binary_register& other) {
if (other >= *this) {
return reset();
}
binary_register b = other;
if (b.size_regs() < size_regs()) {
b._reg.resize(size_regs(), 0);
}
b = b.bin_comp();
b._reg.push_back(0); // Add a word to handle the two's compliment overflow.
*this += b;
_reg.pop_back(); // Get rid of the two's compliment overflow.
return *this;
}
binary_register& binary_register::operator*=(const binary_register& other) {
*this = *this * other;
return *this;
}
binary_register& binary_register::operator/=(const binary_register& other) {
*this = *this / other;
return *this;
}
binary_register& binary_register::operator%=(const binary_register& other) {
*this = *this % other;
return *this;
}
binary_register binary_register::operator+(const binary_register& b) const {
binary_register a = *this;
a += b;
return a;
}
binary_register binary_register::operator-(const binary_register& b) const {
binary_register a = *this;
a -= b;
return a;
}
binary_register binary_register::operator*(const binary_register& b) const {
std::size_t count = 0;
binary_register x;
binary_register y = b;
while (y.is()) {
if (y.at_bit(1)) {
x += (*this << count);
}
count += 1;
y >>= 1;
}
return x;
}
binary_register binary_register::operator/(const binary_register& b) const {
binary_register q;
binary_register r = *this;
divide_remainder(*this, b, q, r);
return q;
}
binary_register binary_register::operator%(const binary_register& b) const {
binary_register q;
binary_register r = *this;
divide_remainder(*this, b, q, r);
return r;
}
binary_register operator+(binary_register&& a, const binary_register& b) {
return a += b;
}
binary_register operator-(binary_register&& a, const binary_register& b) {
return a -= b;
}
binary_register operator*(binary_register&& a, const binary_register& b) {
return a *= b;
}
binary_register operator/(binary_register&& a, const binary_register& b) {
return a /= b;
}
binary_register operator%(binary_register&& a, const binary_register& b) {
return a &= b;
}
binary_register& binary_register::operator++() {
binary_register one(1, 1);
operator+=(one);
return *this;
}
binary_register binary_register::operator++(int) {
binary_register a(*this);
operator++();
return a;
}
binary_register& binary_register::operator--() {
binary_register one(1, 1);
operator-=(one);
return *this;
}
binary_register binary_register::operator--(int) {
binary_register a(*this);
operator--();
return a;
}
binary_register binary_register::bin_comp() const {
binary_register a = ~*this;
binary_register one(1, 1);
a += one;
return a;
}
void binary_register::div_rem(binary_register& other, binary_register& qot, binary_register& rem) const {
rem = *this;
divide_remainder(*this, other, qot, rem);
}
binary_register& binary_register::trim() {
while (!_reg.empty() && _reg.back() == 0) {
_reg.pop_back();
}
if (_reg.empty()) {
_reg.push_back(0);
}
return *this;
}
void binary_register::get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const {
if (index) {
if (index >= BITS) {
reg_index = index / BITS;
bit_index = index % BITS;
if (!bit_index) {
--reg_index;
bit_index = BITS;
}
return;
}
reg_index = 0;
bit_index = index;
return;
}
reg_index = 0;
bit_index = 0;
}
void binary_register::divide_remainder(const binary_register& x, binary_register y, binary_register& q, binary_register& 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 binary_register::get_string(Word base) const {
binary_register radix(1, base);
binary_register n = *this;
Text_Stream stream;
while (n.is()) {
binary_register q;
binary_register r = n;
divide_remainder(n, radix, q, r);
n = q;
stream << r.at_reg(0);
}
Text res = stream.str();
std::reverse(res.begin(), res.end());
return res;
}
void binary_register::left_shift_bits(std::size_t& word_index, std::size_t& bit_index) {
std::size_t i = _reg.size();
_reg.push_back(0);
auto bit_mask = Double_Word(MASK);
while (i-- > 0) {
auto buffer = Double_Word();
buffer |= Double_Word(_reg[i]);
buffer <<= bit_index;
_reg[i] = static_cast<Word>(buffer & bit_mask);
buffer >>= BITS;
buffer |= Double_Word(_reg[i + 1]);
_reg[i + 1] = static_cast<Word>(buffer);
}
if (_reg.back() == 0) {
_reg.pop_back();
}
}
void binary_register::right_shift_bits(std::size_t& word_index, std::size_t& bit_index) {
bool pop_back = word_index ? false : true;
if (word_index) {
word_index -= 1;
}
_reg.push_back(0);
auto inv_index = BITS - bit_index;
std::size_t end = (_reg.size() - 1);
auto bit_mask = Double_Word(MASK);
for (std::size_t i = 0; i < end; i += 1) {
auto buffer = Double_Word();
buffer |= Double_Word(_reg[i + 1]);
buffer <<= inv_index;
_reg[i] >>= bit_index;
_reg[i] |= static_cast<Word>(buffer & bit_mask);
}
_reg[end] >>= bit_index;
while (word_index-- > 0) {
_reg.push_back(0);
}
if (pop_back) {
_reg.pop_back();
}
}
}
