4
\$\begingroup\$

I want to improve this code with better logic and using STL.

#include <iostream>
#include <vector>

void addition(const std::vector<int>& A,
              const std::vector<int>& B,
                    std::vector<int>& C)
{
   int size_A = A.size();
   int size_B = B.size();
   int max_size;
   if (size_A >= size_B)
   {
      max_size = size_A;
   }
   else
   {
      max_size = size_B;
   }

   int carry = 0, sum = 0;

   int i = size_A - 1, j = size_B - 1, k = max_size;
   C.resize(k + 1);

   while ( i >= 0 && j >= 0 && k >= 0)
   {
      sum = A[i] + B[j] + carry;

      if (sum == 0)
      {
         carry = 0;
         C[k] = 0;
      }
      else if (sum == 1)
      {
         carry = 0;
         C[k] = 1;
      }
      else if (sum == 2)
      {
         carry = 1;
         C[k] = 0;
      }
      else if (sum == 3)
      {
         carry = 1;
         C[k] = 1;
      }
      i--;
      j--;
      k--;
   }
  //if size of first binary number is greter than first
  if (max_size == size_A)
  {
     while (i >= 0 && k >= 0)
     {
        sum = A[i] + carry;

        if (sum == 0)
        {
           carry = 0;
           C[k] = 0;
        }
        else if (sum == 1)
        {
           carry = 0;
           C[k] = 1;
        }
        else if (sum == 2)
        {
           carry = 1;
           C[k] = 0;
        }
        else if (sum == 3)
        {
           carry = 1;
           C[k] = 1;
        }
        i--;
        k--;
     }
  }
  //If size of second binary number is greater than first
  else if (max_size == size_B)
  {
     while (j >= 0 && k >= 0)
     {
       sum = B[j] + carry;

       if (sum == 0)
       {
          carry = 0;
          C[k] = 0;
       }
       else if (sum == 1)
       {
          carry = 0;
          C[k] = 1;
       }
       else if (sum == 2)
       {
          carry = 1;
          C[k] = 0;
       }
       else if (sum == 3)
       {
          carry = 1;
          C[k] = 1;
       }
       j--;
       k--;
     }
  }
  C[0] = carry;
}

int main()
{
   int n1, n2, val;
   std::cout << "Enter the  number of bits for first binary numbers \n";
   std::cin >> n1;
   std::cout << "Enter the  number of bits for second binary numbers \n";
   std::cin >> n2;

   std::vector<int> A;
   std::vector<int> B;
   std::vector<int> C;

   std::cout << "Enter bits for first binary number \n";
   for (int i = 0; i < n1; i++)
   {
      std::cin >> val;
      A.push_back(val);
   }

   std::cout << "Enter bits for second binary number \n";
   for (int i = 0; i < n2; i++)
   {
     std::cin >> val;
     B.push_back(val);
   }

   std::cout << "First number    : ";
   for (int i = 0; i < A.size(); i++)
   {
      std::cout << A[i];
   }

   std::cout << "\nSecond number   : ";
   for (int i = 0; i < B.size(); i++)
   {
      std::cout << B[i];
   }

   addition(A, B, C);

   std::cout << "\nResult          : ";
   for (int i = 0; i < C.size(); i++)
   {
     std::cout << C[i];
   }
   std::cout << "\n";
}
\$\endgroup\$
1

3 Answers 3

5
\$\begingroup\$

Write DRY code:

DRY - Don't repeat yourself.

std::cout << "Enter bits for first binary number \n";
for (int i = 0; i < n1; i++)
{
   std::cin >> val;
   A.push_back(val);
}

std::cout << "Enter bits for second binary number \n";
for (int i = 0; i < n2; i++)
{
  std::cin >> val;
  B.push_back(val);
}

These two bits of code are way to similar. Make a function that does this work and pass as parameters any differences.

Highest order bit is where?

  std::cin >> val;
  B.push_back(val);

With this code your most significant bit is at location 0. This gives you no room to expand the number. Put the least significant bit at 0 and the more significant bits at higher locations. This will make it easier to do the standard maths operations in the long run.

This looks like a switch:

  if (sum == 0)
  {
     carry = 0;
     C[k] = 0;
  }
  else if (sum == 1)
  {
     carry = 0;
     C[k] = 1;
  }
  else if (sum == 2)
  {
     carry = 1;
     C[k] = 0;
  }
  else if (sum == 3)
  {
     carry = 1;
     C[k] = 1;
  }

I would write as:

  switch (sum) {
      case 0: carry = 0;C[k] = 0;break;
      case 1: carry = 0;C[k] = 1;break;
      case 2: carry = 1;C[k] = 0;break;
      case 3: carry = 1;C[k] = 1;break;
      default: throw std::exception("Something very wrong happened");
  }

Another case of DRY:

  while ( i >= 0 && j >= 0 && k >= 0)
  {
      sum = A[i] + B[j] + carry;
      // STUFF
      k--;i--;j--;
  }
  //if size of first binary number is greter than first
  if (max_size == size_A)
  {
     while (i >= 0 && k >= 0)
     {
        sum = A[i] + carry;
        // STUFF
        k--;i--;
     }
  }
  //If size of second binary number is greater than first
  else if (max_size == size_B)
  {
     while (j >= 0 && k >= 0)
     {
       sum = B[j] + carry;
       // STUFF
      k--;j--;
     }
  }

Not only can all the "stuff" by factored out into its own function. But those three loops can be combined into a single loop.

  for(;k >= 0;--k)
  {
      int a = (i > 0) ? A[i--] : 0
      int b = (j > 0) ? B[j--] : 0;
      sum = a + b + carry;
      // STUFF
  }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I thought of a switch when I read that, but then thought carry = a&b; result = a^b;. You might even be able to use std::transform() with a stateful functor to hold the carry. \$\endgroup\$ Feb 12, 2018 at 18:52
5
\$\begingroup\$

Code Organization

Rather than having multiple sections of code that execute conditionally depending on whether A is smaller than B or vice versa, I'd start by finding the smaller and larger of the two inputs, and then operate on them (independent of whether they were originally A or B).

Return what's Created

I'd also have the Addition return the result it creates. The days of needing to avoid returning large values to avoid needless copying are pretty much a bit of ancient lore, better forgotten.

Use Verbs when appropriate

You addition should really be add--you're dealing with a function. It does something, so the appropriate kind of work to use as its name is a verb.

Store the Data little-endian

Most of the time, it's much easier to deal with data being stored little-endian. That is, the least significant bit is stored as element 0 of each vector, element 1 is more significant, and on up to the maximum subscript storing the most significant bit of that number.

Use Functions where Appropriate

Right now, your main has a number of lines of code to read in some bits, write out some bits, and so on. At least IMO, each of these chunks of code should become a function.

std::string show(std::vector<int> const &t) {
    std::string ret;
    for (auto p = t.rbegin(); p != t.rend(); p++)
        ret += *p ? '1' : '0';
    return ret;
}

std::vector<int> read_bin(std::string_view const &prompt, int size) {
    std::vector<int> ret;
    std::cout << prompt << ": ";

    for (int i = 0; i < size; i++)
    {
        int val;
        std::cin >> val;
        ret.push_back(val);
    }
    return { ret.rbegin(), ret.rend() };
}

Use Appropriate Logic

Right now, you're implementation of addition depends on a having an addition operator that already knows how to add two bits and create a carry out to the next bit from them. IOW, your implementation depends on the pre-existence of exactly what it's supposed to implement. Unfortunately, the task isn't quite as simple as @TobySpeight's comment would tend to imply. While he's nearly correct that the result can use an xor, it has to be a 3-way XOR, not just two way (the inputs are the previous carry, A[i] and B[i]).

Generating the carry correctly is a bit trickier: since you have three inputs, the carry needs to be set of any two of the inputs is set. Unfortunately, the only way I know of to do that is to enumerate the three possibilities:

carry = (A[i] & B[i]) | (A[i] & carry) | (B[i] & carry);

One possibility that might seem obvious would be to just count the results from the three sub-expressions there--but that gets us back to addition depending on addition, since counting is just addition in disguise.

Consider Using a class to store and Manipulate a number

Instead of having an add, read_bin and show to manipulate data in a couple of vectors, consider creating a class that stores the data, and implements the operations on the numbers using the normal conventions (+ to add, << to display, >> to read.

class binary {
    std::vector<int> data;

    int &operator[](std::size_t index) { return data[index]; }
    int const &operator[](std::size_t index) const { return data[index]; }
public:
    auto size() const { return data.size(); }

    binary() = default;

    binary(size_t size) : data(size) {}

    friend std::ostream &operator<<(std::ostream &os, binary const &t) {
        std::string ret;
        for (auto p = t.data.rbegin(); p != t.data.rend(); p++)
            ret += *p ? '1' : '0';
        return os << ret;
    }

    friend std::istream &operator>>(std::istream &is, binary &b) {
        std::vector<int> ret;
        b.data.resize(is.width());

        for (auto p = b.data.rbegin(); p != b.data.rend(); p++) {
            int val;
            is >> val;
            *p = val ? 1 : 0;
        }
        return is;
    }

    friend binary operator+(binary const &A, binary const &B) {
        binary const &smaller = A.size() < B.size() ? A : B;
        binary const &larger = &smaller == &A ? B : A;

        binary ret(larger.size() + 1);

        int carry = 0;
        int sum;
        int i;

        for (i = 0; i < smaller.size(); i++) {
            sum = smaller[i] ^ larger[i] ^ carry;
            carry = (smaller[i] & larger[i]) | (smaller[i] & carry) | (larger[i] & carry);

            ret.data[i] = sum;
        }

        for (; i < larger.size(); i++) {
            ret.data[i] = larger[i] ^ carry;
            carry &= larger[i];
        }
        return ret;
    }
};

Using these, our main becomes somewhat more manageable as well:

int main() {
   int n1, n2, val;
   std::cout << "Enter the  number of bits for first binary numbers \n";
   std::cin >> n1;
   std::cout << "Enter the  number of bits for second binary numbers \n";
   std::cin >> n2;

   std::cout << "Enter bits for first number: ";
   binary A;
   std::cin >> std::setw(n1) >> A;

   std::cout << "Enter bits for second number: ";
   binary B;
   std::cin >> std::setw(n2) >> B;

   auto C = A + B;
   auto width = C.size();

   std::cout << std::setw(15) << "First number: " << std::setw(width) << A << "\n";
   std::cout << std::setw(15) << "Second number: " << std::setw(width) << B << "\n";
   std::cout << std::setw(15) << "Sum: " << std::setw(width) << C << "\n";
}
\$\endgroup\$
1
\$\begingroup\$

In addition to other answers, I'd add replacing

if (sum == 0)
{
   carry = 0;
   C[k] = 0;
}
else if (sum == 1)
{
   carry = 0;
   C[k] = 1;
}
else if (sum == 2)
{
   carry = 1;
   C[k] = 0;
}
else if (sum == 3)
{
   carry = 1;
   C[k] = 1;
}

with

C[k]  = sum % 2;
carry = sum / 2;

or, perhaps better:

C[k]  = sum & 1;
carry = (sum & 2) >> 1;
\$\endgroup\$
1
  • \$\begingroup\$ This retains the fundamental problem of the original: it's using addition to implement addition. If you already have working addition, there's no point in doing this at all. \$\endgroup\$ Mar 12, 2018 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.