bigInt addition and subtraction matters

Question

I am currently doing a school assignment (I am sorry that my question is about my assignment, but I am not asking about the algorithms used in the codes). I am now currently doing the arithmetic part, addition and subtract. Since there are only two operators, there are 8 combinations of operation. In my program, I can do these four cases:

（+a）+（+b） （-a）+（-b） （-a）-（+b） （+a）-（-b）

However, I cannot figure out the way to do the other four cases, I.e.

（+a）+（-b） （-a）+（+b） （-a）-（-b） （+a）-（+b）

I sincerely hope that you guys can provide suggestions and advice on how to deal with these four cases.

Here is my code:

linkedListType.h: It is a common linked list header file therefore I don't post the whole code here.

bigInteger.h: The functions in this are quite long. Therefore, I skipped posting them out.

#ifndef BIG_INTEGER_H
#define BIG_INTEGER_H

#include <stack>  
#include <iostream>
#include "linkedListType.h"

using namespace std;

class bigInteger
{
private:
    int sign;                       // set 0 for positive, 1 for negative
    linkedListType<int> digits;     // internal linked-list for storing digits in reverse order

public:
    bigInteger();                           // default constructor
    bigInteger(const bigInteger& other);    // copy constructor

    // Overload constructor
    // Use an numerical string to construct this bigInteger
    // For negative number, the first char in the string is '-'
    // e.g. "-12345"
    bigInteger(const string& number);       

    // overload the assignment operator
    const bigInteger& operator= (const bigInteger& other);

    // Return a new bigInteger that is equal to *this + other
    // The contents of this and other should not be modified
    bigInteger& operator+ (bigInteger& other);

    // Return a new bigInteger that is equal to *this - other
    // The contents of this and other should not be modified
    bigInteger& operator- (bigInteger& other);

    // Print a big integer
    // Since the digits are stored in reverse order in the internal
    // list, you should print in reverse order
    // Print "undefined" if the digits list is empty
    friend ostream& operator<<(ostream& os, bigInteger& n);
};

Answer 1

well all the comments are handling the operator overload stuff but I suspect the OP is about how to compute all combinations of signs of operands for addition and substraction.

1. two's complement

   well most HW implementations of integer ALU use two's complement for signed numbers representation. That means:

   -X = (X^0xFFFFFFFF)+1; // 32 bit example
   

   that negative value obtained just by inverting of all bits and increment the result. So you can use single adder architecture for all add/sub and sign combinations while sign bit is still MSB. This encoding handles signed and unsigned operations the same so for addition you have no problem at all (nothing to do just add) and for substraction just invert signum of the second operand and add.

   C++ Implementation looks like this:

   bool bigInteger::sign() { return MSB_of_this; }
   bigInteger bigInteger::operator+ () { bigInteger z=*this; return z; }
   bigInteger bigInteger::operator- () { bigInteger z=*this; /* here negate all bits and increment z*/ return z' |z; }
   bigInteger bigInteger::operator+ (bigInteger& y)
    {
    bigInteger z;
    // here do z = *this + y as if all operands were positive
    return z;
    }
   
   bigInteger bigInteger::operator- (bigInteger& y0)
    {
    bigInteger z;
    y=-y0; // invert sign in temp variable to avoid changing input operand value !!!
    // here do z = *this + y as if all operands were positive
    return z;
    }
   

   note that I am not changing any input operand and all returns are separate variable (not using this even for unary+). It is due to chain-ability of operands. Some compilers have hard time to daisy chain more then 3 operators in a single line if not coded this way that means you can not compile lines like

   c=a+b-c*a*b/(s-d)+(23*q);
   

   instead you would have to break it down to more simple terms ...

2. In the case you do not use two's complement

   Then you have to handle the signs of input operand. The most common case is that you have sign flag as separate variable not inside the number bits. In this case you need some functions that does not take sign into account at all

   bigInteger uadd(bigInteger &a,bigInteger &b); //=|a|+|b|
   bigInteger usub(bigInteger &a,bigInteger &b); //=|a|-|b| but operands must be: |a|>|b|
   bool        ugeq(bigInteger &a,bigInteger &b); //=|a|>=|b| Unsigned Greater or EQual
   

   from this is easy

   Addition

   • you can add numbers only if they are the same sign if not the convert it to substraction

   Substraction

   • you can sub numbers only if they are the same sign and the first operand is greater or equal then the second one.

   So it would be something like this:

   bigInteger bigInteger::operator+ (bigInteger& y)
    {
    bigInteger z;
    bool sx,sy;
    sx=sign();
    sy=y.sign();
    if (sx==sy) z=uadd(*this,y);  // same signs is add
    else                            // not then first operand for (a-b) is the positive one
     {
     if (sx) return y-(*this);
     else    return (*this)-y;
     }
    // here set the sign to the same as operands
    z.set_sign(sx);
    return z;
    }
   

   as this is an assignment I will leave the - operator without code.

   It will be very similar to + operator but you need to sort the input operands by absolute size (using ugeq) and set the result sign from the abs bigger one. if you swapped operands invert the sign of result. Substract only if booth operands are the same sign other wise convert to (a+b) ...

Hope it helps a bit