Basic binary number container

Question

Summary: a templated class, whose main purpose is to store a binary representation of a decimal number. I choose array of booleans as a storage, since bitset was forbidden. One of the requirements was to overload every arithmetic operation, i.e. every operation should be bitwise.

Note: at this moment relational operators (such as <, >) have not been implemented yet, therefore, it's barely possible for me to define a division.

What could be improved, in terms of algorithms and code style? What are the general mistakes?

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <string>

/*  g++ 8.1.0: compile parameters -O3 -march=native
 *  has not yet been tested under MSVC, although there are no specific features used
 */

template <std::size_t SIZE> class Binary {

  #define AND          &&
  #define BIT_AND      &
  #define BIT_OR       |
  #define NOT          !
  #define OR           ||
  #define XOR          ^

  #define XNOR(a, b)   \
  { return !(a XOR b); }

  #define __SIZE_ASSERTION__ \
  static_assert(!((SIZE != 0) && ((SIZE & (SIZE - 1)))) && !(SIZE > 32));
  using bytearray_t = std::array<bool, SIZE>;


 public:

  Binary() { __SIZE_ASSERTION__ }

  //! explicit constructor to avoid implicit convert from char
  explicit Binary(int32_t num) {
    __SIZE_ASSERTION__
    for (std::size_t idx = SIZE; idx-- > 0;)
      num & (1 << (SIZE - 1 - idx)) ? bytearray[idx] = 1 : bytearray[idx] = 0;
  }

  static int32_t B2D(const bytearray_t& that) noexcept {
    int32_t decimal;
    for (std::size_t idx = 0; idx < SIZE; idx++)
      decimal = decimal << 1 BIT_OR that[idx];
    return decimal;
  }

  inline bytearray_t getField() const noexcept { return this->bytearray; }

  friend std::ostream& operator<<(std::ostream& os, const Binary& that) {
    os << "[";
    for (const auto& bit : that.bytearray) os << bit;
    os << "] -> " << Binary::B2D(that.bytearray);
    return os;
  }

  Binary operator=(const Binary& that) noexcept {
    this->bytearray = that.bytearray;
    return *this;
  }

  Binary operator+(const Binary& that) noexcept {
    Binary temp = *this;
    temp.bytearray = Binary::add(this->bytearray, that.bytearray);
    return temp;
  }

  Binary operator-(const Binary& that) noexcept {
    Binary temp = *this;
    temp.bytearray = Binary::sub(this->bytearray, that.bytearray);
    return temp;
  }

  Binary operator*(const Binary& that) noexcept {
    Binary temp = *this;
    temp.bytearray = Binary::mul(this->bytearray, that.bytearray);
    return temp;
  }

  /*

  Binary operator/(const Binary& that) noexcept {
    Binary temp = *this;
    temp.bytearray = Binary::div(this->bytearray, that.bytearray);
    return temp;
  }

  */

  // bit-shifting overloading
  Binary operator<<(unsigned shift) {
    for (std::size_t i = 0; i < shift; ++i) lsh(bytearray);
    return *this;
  }

  Binary operator>>(unsigned shift) {
    for (std::size_t i = 0; i < shift; ++i) rsh(bytearray);
    return *this;
  }

  friend bool operator==(const Binary& lhs, const Binary& rhs) {
    for (std::size_t idx = 0; idx < SIZE; ++idx) {
      if (lhs.bytearray[idx] XOR rhs.bytearray[idx])
        return false;
    }
    return true;
  }

  friend bool operator!=(const Binary& lhs, const Binary& rhs) {
    return !(lhs == rhs);
  }

  //==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//==//

 private:

  bytearray_t bytearray;

  static bool ifExists(const bytearray_t& that, const bool& param) noexcept {
    return std::find(std::begin(that), std::end(that), param) != std::end(that);
  }

  static void lsh(bytearray_t& that) noexcept {
    for (std::size_t idx = 0; idx < SIZE - 1; idx++) that[idx] = that[idx + 1];
    that[SIZE - 1] = 0;
  }

  static void rsh(bytearray_t& that) noexcept {
    for (std::size_t idx = SIZE - 1; idx > 0; idx--) that[idx] = that[idx - 1];
    that[0] = 0;
  }

  static bytearray_t add(const bytearray_t& lhs, const bytearray_t& rhs) {
    bytearray_t res = {0};
    bool rem = 0;
    for (std::size_t idx = SIZE; idx-- > 0;) {
      res[idx] = (lhs[idx] XOR rhs[idx]) XOR rem;
      rem =
          (lhs[idx] BIT_AND rhs[idx]) BIT_OR (rem BIT_AND(lhs[idx] XOR rhs[idx]));
    }
    return res;
  }

  static bytearray_t sub(const bytearray_t& lhs, const bytearray_t& rhs) {
    bytearray_t res = {0};
    bool rem = 0;
    for (std::size_t idx = SIZE; idx-- > 0;) {
      res[idx] = rem XOR (lhs[idx] XOR rhs[idx]);
      rem = (not lhs[idx] BIT_AND rhs[idx]) or (not lhs[idx] BIT_AND rem) or
            (rhs[idx] BIT_AND rem);
    }
    return res;
  }

  static bytearray_t mul(bytearray_t lhs, bytearray_t rhs) {
    bytearray_t res = {0};
    for (; ifExists(lhs, 1); ) {
      if (rhs[SIZE - 1] BIT_AND 1) res = Binary::add(res, lhs);
      rsh(rhs); lsh(lhs);
    }
    return res;
  }

  /*
  [[deprecated("... doesn't work for non-integer results")]]
  static bytearray_t div(bytearray_t lhs, bytearray_t rhs) {
    bytearray_t res = {0};
    for (; ifExists(lhs, 1);) {
      lhs = sub(lhs, rhs);
      res = add(res, Binary(1).getField());
    }
    return res;
  }
  */

};

int main() { std::cout << (Binary<16>(4) << 2) << "\n"; }

Updated versions of this code are on GitHub.

Answer 1

I wanted to expand on @vnp's comment about the #defines, and focus on the use of the preprocessor overall. I would say every use of the preprocessor here, not counting the #includes, is a mistake.

First, as @vnp points out, defining the logical operators like this has little value. 99.999% of C++ programmers will prefer to type a && b rather than a AND b. The 0.001% who really like to spell those operations out will write a and b... because and, bitand, xor, and so on, are all already keywords.

So all those #defines could be removed, and your code would change from stuff like:

res[idx] = rem XOR (lhs[idx] XOR rhs[idx]);
rem = (not lhs[idx] BIT_AND rhs[idx]) or (not lhs[idx] BIT_AND rem) or (rhs[idx] BIT_AND rem);

(Which, I noted, already uses or and not instead of OR and NOT.) The code could become like:

res[idx] = rem xor (lhs[idx] xor rhs[idx]);
rem = (not lhs[idx] bitand rhs[idx]) or (not lhs[idx] bitand rem) or (rhs[idx] bitand rem);

Which is almost no difference. (Though, most C++ programmers would balk, and prefer you use the symbolic operators.)

I suppose there's no xnor. But if you really wanted one, a macro is a terrible idea. Better would be a template:

template <typename T, typename U>
constexpr auto xnor(T&& t, U&& u)
    noexcept(noexcept(bool(std::forward<T>(t) xor std::forward<U>(u))))
{
    return !bool(std::forward<T>(t) xor std::forward<U>(u));
}

Even better would be to restrict to the template to your own class or namespace, to avoid collisions with other people's definitions of xnor. But at any rate, XNOR is never used, so it can just be removed.

The other problematic use of the preprocessor is __SIZE_ASSERTION__. The first thing wrong with this is that __SIZE_ASSERTION__ is an illegal identifier. It breaks at least three rules:

• Don't start identifiers with an underscore in the global scope. (All preprocessor macros are global scope.)
• Don't start identifiers with an underscore and a capital letter anywhere.
• Don't use double underscores in identifiers anywhere.

You could rename the macro, but there's really no point. You seem to misunderstand how static assertions work. Static assertions aren't done at run-time - they aren't done when a function (like the constructor) is called. Static assertions are done when something is instantiated at compile-time.

In other words, all you need to do is this:

template <std::size_t SIZE>
class Binary {
public:
    static_assert(!((SIZE != 0) && ((SIZE & (SIZE - 1)))) && !(SIZE > 32));

    // ...

The assertion will be checked whenever the class is instantiated.

In other words, even if you just do this:

Binary<3>::B2D({}); // Note: no Binary constructors called

The assertion will fire. Hell, the assertion will fire even if you just do this:

sizeof(Binary<3>);

Since you only need the assertion in one place, there is no need for a macro to repeat it in every constructor.

I would also add that that static assertion is monstrous. In fact, I suspect it might be incorrect (do you intend for 0 to be valid? I suspect not). It would be much clearer and more maintainable if you broke it up:

template <std::size_t SIZE>
class Binary {
public:
    static_assert(SIZE > 0);
    static_assert(SIZE <= 32);
    static_assert(SIZE & (SIZE - 1), "size must be a power of 2");

    // ...

This will also give you more specific error messages when the assertion fails.

So, to summarize: Every use of the preprocessor in this code is either superfluous, ill-advised, or straight-up incorrect. Generally, in modern C++, you should avoid the preprocessor like the plague... except for #include. And once we get modules, that's out, too.

---

The practical answer to the question is: No, there's no difference between having functions for the operations and writing the operators using those functions, versus doing the operations in the operators themselves. In theory doing the operations in functions means there's an extra cost of a function call in your operators. In reality, that will just be inlined away. So it really doesn't matter.

In fact, in this case in particular, I think it would be a good idea, because the static functions could return more information... in this case, the leftover carry bit.

But as @JDługosz mentions, normal practice is to define the assignment version of binary ops, then write the binary op version in terms of it. You can still do that with static funcs, but you'd have to refactor your static funcs:

// could be private
static bool add_to(bytearray_t& lhs, bytearray_t const& rhs) noexcept
{
    // do your addition here basically as you already have in add(),
    // except without res, putting the result at each loop iteration
    // in lhs instead. return the leftover carry bit
}

// to return the carry bit in add(), you'd probably have to return a
// std::tuple<bytearray_t, bool>
static std::tuple<bytearray_t, bool> add(bytearray_t lhs, bytearray_t const& rhs) noexcept
{
    auto carry = add_to(lhs, rhs);
    return std::tuple<bytearray_t, bool>{lhs, carry};
}

Binary& operator+=(Binary const& that) noexcept
{
    add_to(*this, that); // ignore the leftover carry
    return *this;
}

// this should be *outside* of the class
// note a is taken by val to get a copy (or move)
template <std::size_t SIZE>
Binary<SIZE> operator+(Binary<SIZE> a, Binary<SIZE> const& b) noexcept
{
    a += b;
    return a;

    // or:
    //   auto [ result, carry ] = add(a, b);
    //   return result;
    // or:
    //   return std::get<0>(add(a, b));
}

There's nothing wrong with writing a += b in terms of a + b (and by extension, add_to(a, b) in terms of add(a, b))... but it's not really efficient because you'd effectively have to do auto c = a + b; a = std::move(c);, which introduces an unnecessary temporary. (And because you're using arrays internally, moves aren't cheap.)

My advice would be to:

• have a non-member friend add_to(Binary&, Binary const&). It should return the leftover carry bit, which could be useful information (never throw useful information away!).
• have a non-member friend (or not) add(Binary const&, Binary const&) (or add(Binary, Binary const&)) in terms of add_to(). It should return a std::tuple<Binary, bool> - that's the addition result and the leftover carry bit.
• write operator+= (inside the class) in terms of add_to()
• write operator+ (outside the class) in terms of add().

So if you need the carry bit, you'd do auto [ add_result, carry_bit ] = add(a, b);. If you don't care about the carry bit, you'd just do auto add_result = a + b;.

A possible extra would be to have both add() and add_to() take an optional third parameter bool defaulted to false, so you can start with a non-zero carry bit if you like. Or a set overloads that take a bool& as the third parameter, and use it as an in/out parameter for the carry bit, so the functions don't need to put the carry bit in the return, I suppose. Or even have an add_with_carry() to handle all that carry bit stuff, and leave add() as it is ignoring it.

For even more syntactic bliss, you could define the addition function as a non-member using:

template <std::size_t N, std::size_t M>
auto add(Binary<N>, Binary<M> const&, bool = false) noexcept ->
    std::enable_if_t<(N >= M), std::tuple<Binary<N>, bool>>
{
    // ...
    // probably in terms of add_to()
}

template <std::size_t N, std::size_t M>
auto add(Binary<N> const& lhs, Binary<M> const& rhs, bool carry = false) noexcept ->
    std::enable_if_t<(N < M), std::tuple<Binary<M>, bool>>
{
    // Since add is commutative:
    return add(rhs, lhs, carry);
}

template <std::size_t N, std::size_t M>
auto operator+(Binary<N> const& lhs, Binary<M> const& rhs) noexcept ->
    std::enable_if_t<(N >= M), Binary<N>>
{
    return std::get<0>(add(lhs, rhs));
}

template <std::size_t N, std::size_t M>
auto operator+(Binary<N> const& lhs, Binary<M> const& rhs) noexcept ->
    std::enable_if_t<(N < M), Binary<M>>
{
    // Since add is commutative:
    return rhs + lhs;
}

// for, add_to and operator+=, you'll probably want to static_assert that
// the rhs bit size is <= the lhs bit size... if you want to do something
// like "Binary<4> a; Binary<8> b; a += b;", you'll just have to require
// a cast: "Binary<4> a; Binary<8> b; a += Binary<4>(b);")

which would allow you to do Binary<4>{1} + Binary<8>{1} in any order and get Binary<8>{2} as the result.

It all comes down to what interface you'd like.

Answer 2

• I don't see the value in #define standard operators.

• I see no reason in limiting bitwidth to powers of 2. A 24-bit integers have an equal right to exist. If you insist on powers of 2, it is better to template<std::size_t LOG_SIZE> class Binary using the exponent as a template parameter. At least the assertion would become as simple as LOG_SIZE < 5.

• A Binary(int32_t num) constructor feels inside out. Consider

      byte array[idx] = num & 0x01;
      num >>= 1;
  

• Addition, subtraction, and left shift must convey carry bit back to the caller.

  Multiplication also must signal an overflow. Consider a possibility to multiply into a double-width array.

• I recommend to rename lsh and rsh to lsl and lsr respectively, to be more in line with the standard assembly mnemonic.

  Speaking of which, without an arithmetic shift the picture seems incomplete (there are also rotates, with or without carry, right shift with carry, etc, which are sometimes immensely important).

• ifExists looks like a premature micro-optimization. A loop over all the bits would be much cleaner.

Answer 3

I assume this is to learn how arithmetic works inside a CPU’s ALU on the bit level. That is an interesting idea, and in real life I recall implementing multiply on an 8-bit CPU and coming to understand how it works when figuring that out.

---

Your constructor taking int32_t will have issues with negative numbers. Also, it iterates the mask shifting over the SIZE, and that may be larger than 32! Besides being extra work, the shifting off the end of the word will not give you a meaningful test.

num & (1 << (SIZE - 1 - idx)) ? bytearray[idx] = 1 : bytearray[idx] = 0;

You have the same stuff on the left hand side of both assignments. So you should write:

bytearray[idx] = num & (1 << (SIZE - 1 - idx)) ?  1 :  0;

But, you could use a simple means of forcing the result of the test to a 0 or 1 instead of the ternary operation. But, if the bytearray constructor initializes everything to zero, then you only need to set the 1’s anyway.

Shift the parameter down, rather than shifting the mask up. This way you can quit early when you have nothing but zeros left in the high order bits, and it has the advantage of the & always giving you 0 or exactly 1.

explicit Binary (uint64_t num)
{
   size_t idx= 0;
   while (num) {
       if (num&1) {
          if (idx >= SIZE) throw std::invalid_argument("num too big");
          bytearray[idx] = 1;
       }
       num >>= 1;
       ++idx;
}

---

  static int32_t B2D(const bytearray_t& that) noexcept {
    int32_t decimal;
    for (std::size_t idx = 0; idx < SIZE; idx++)
      decimal = decimal << 1 BIT_OR that[idx];
    return decimal;
  }

You are making this a static member, and operating on a parameter of the same type? That is weird and useless. Instead of writing

  y= Binary<N>::B2D(variable);

(for the proper value of N to match what you are using), it is natural to have

  y= variable.to_int();

or something like that. I expect you may want this to be an operator uint32_t in fact.

---

inline bytearray_t getField() const noexcept { return this->bytearray; }

You don’t need say inline when it is defined inside the class like this.

Don’t use this-> to refer to your members.

---

  friend std::ostream& operator<<(std::ostream& os, const Binary& that) {
    os << "[";
    for (const auto& bit : that.bytearray) os << bit;
    os << "] -> " << Binary::B2D(that.bytearray);
    return os;
  }

Don’t make this a friend, since it can be implemented using only the public functions. Write it outside of the class, making it a template function.

---

  Binary operator=(const Binary& that) noexcept {
    this->bytearray = that.bytearray;
    return *this;
  }

Why return yourself by value?

You show that bytearray already knows how to assign itself. So why write this at all (and get it wrong)? Leave it off and the compiler will generate an optimal one automatically.

---

  Binary operator+(const Binary& that) noexcept {
    Binary temp = *this;
    temp.bytearray = Binary::add(this->bytearray, that.bytearray);
    return temp;
  }

It is normal and idiomatic to write this as a non-member taking two arguments. And, write it in terms of +=, which is written as a member.

Likewise for the other operators.

---

  friend bool operator==(const Binary& lhs, const Binary& rhs) {
    for (std::size_t idx = 0; idx < SIZE; ++idx) {
      if (lhs.bytearray[idx] XOR rhs.bytearray[idx])
        return false;
    }
    return true;
  }

Again, why is it a friend when it does not need special access to the internals? Why are you XORing every array element, instead of just letting == on the bytearray do its thing?

In a real library of custom number type, I would expect == to work between versions of different SIZE.

Likewise, a generalized version of the copy constructor that can convert numbers of a different SIZE.

---

The various static members you have in the private section taking a that parameter should just be normal members instead.

---

The left and right shift can be simply written using an std algorithm that copies everything, with the destination shifted one over from the source.