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); };

You should add unary operators - e.g. see here. Note too that it shouldn't be bigInteger& operator+ (bigInteger& other); but bigInteger operator+(const bigInteger& other); i.e. return by value and take the argument by const reference. You may want to write bigInteger& operator+=(const bigInteger& other); (and operator-=), then you can write + as a non-member function like this: bigInteger operator+(bigInteger lgs, const bigInteger& rhs) { return lhs += rhs; }. — Tony Delroy
– Tony Delroy, Commented Oct 29, 2014 at 4:52
Similarly, friend ostream& operator<<(ostream& os, bigInteger& n); should take const bigInteger& n. — Tony Delroy
– Tony Delroy, Commented Oct 29, 2014 at 4:53
Thanks for your suggestions @TonyD. But, may i ask some questions? Would you mind to explain what the use of unary operator is? Also, what is the function of += and -=? — user2847449
– user2847449, Commented Oct 29, 2014 at 5:05
I don't understand your question. And it's unlikely the code you've posted is enough for anyone to help you. (Also, "reversely" is not a word.) — ooga
– ooga, Commented Oct 29, 2014 at 5:15
@user2847449: sure - questions welcome. Say you have bigInteger x; and write -x, if there's no "left hand side" to subtract x from, the compiler will look for a bigInteger bigInteger::operator-() function and call that - it should return the negation of *this - that's explained at the linked question above. += and -= add and subtract an amount from the value on the left hand side, so x = x + 3 can be conveniently shortened to x += 3 if the operators are implemented "normally". If you're writing + and - people will kind of expect += and -= too. — Tony Delroy
– Tony Delroy, Commented Oct 29, 2014 at 5:43

Spektre · Accepted Answer · 2016-03-16 07:50:58Z

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.

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 ...
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

Just my hunch, but given the question says "internal linked-list for storing digits", I suspect there's a digit per list element, and the bit-wise operations / 2s complement aspects you've documented and would need to know about for an efficiently packed and fast bigInteger type aren't needed for this beginner assignment.....
@TonyD hmm I assumed 2^8+ integer base but yes it is more probable they are just digits. the second half of answer should cover the rest if not it is up to she/him to clarify what is missing to the puzzle...

Collectives™ on Stack Overflow

bigInt addition and subtraction matters

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related