Large integer class for storing integer data as a char array

Question

I am working on a LargeInteger class to store Integers beyond the size of long long as a dynamic character array. I have overloaded most of the relevant operators to be used with the large integers.

I would like to find a way to further streamline the addition/subtraction. I think it ought to be possible to only use a single loop and manipulate the signs and order to produce the proper result, but all attempts thus far have failed.

The only things I am unwilling to change:

• Storing the data as a dynamic char array
• The attributes of the operators (friend, overloaded, return type, parameters)

This does not use proper C++ components such as std::vector, std::copy and others. My goals in this project were to avoid the use of the standard (or other) library aside from I/O.

Everything else is fair game, and I welcome any and all criticisms. This is one of the first C++ classes I have made, so I expect that my coding is sub-par.

LargeInt.h

#ifndef LARGEINT_H
#define LARGEINT_H

#include <iostream>

typedef unsigned int Counter;
typedef char Digit;
typedef unsigned int Index;
typedef bool Sign;

const bool kSignPositive = 0;
const bool kSignNegative = 1;
const bool kCarryTrue = 1;
const bool kCarryFalse = 0;
const bool kBorrowTrue = 1;
const bool kBorrowFalse = 0;

const Counter kDefaultCounterValue = 0;

const Digit kDefaultDigitValue = 0;
const Digit kMinDigitValue = 0;
const Digit kMaxDigitValue = 9;
const Digit kRadix = 10;

const Index kFirstIndex = 0;

const size_t kByteSize = 8;
const size_t kMinLength = 1;

namespace helper_templates
{
    // Count Digits
    template <typename T>
    Counter TCountDigits(T x);

    // Get Sign
    template <typename T>
    bool TGetSign(T x);
}

class LargeInt
{
    private:
        Sign sign_;
        size_t length_;
        Digit* data_;

    public:
        /*
         * Constructors
         */

        // Default
        LargeInt();

        // Copy
        LargeInt(const LargeInt& x);

        // Copy and Resize
        LargeInt(const Sign sign, const size_t length, const Digit* data);

        // Integer Type
        LargeInt(const long long x);

        /*
         * Destructor
         */

        ~LargeInt();

        /*
         * Operators
         */

        // Assignemnt
        LargeInt& operator=(const LargeInt& x);

        // Negation
        LargeInt operator-();

        // Addition
        friend LargeInt operator+(LargeInt x, const LargeInt& y);

        // Addition Assignment
        LargeInt& operator+=(const LargeInt& x);

        // Subtraction
        friend LargeInt operator-(LargeInt x, const LargeInt& y);

        // Subtraction Assignment
        LargeInt& operator-=(const LargeInt& x);

        // Preincrement
        LargeInt& operator++();

        // Postincrement
        LargeInt operator++(int);

        // Predecrement
        LargeInt& operator--();

        // Postdecrement
        LargeInt operator--(int);

        // Not
        bool operator!();

        // Equality
        friend bool operator==(const LargeInt& x, const LargeInt& y);

        // Inequality
        friend bool operator!=(const LargeInt& x, const LargeInt& y);

        // Greater Than
        friend bool operator>(const LargeInt& x, const LargeInt& y);

        // Greater Than or Equal To
        friend bool operator>=(const LargeInt& x, const LargeInt& y);

        // Less Than
        friend bool operator<(const LargeInt& x, const LargeInt& y);

        // Less Than or Equal To
        friend bool operator <=(const LargeInt& x, const LargeInt& y);

        // Insertion
        friend std::ostream& operator<<(std::ostream& out,
            const LargeInt& x);

        /*
         * Functions
         */

        // Absolute Value
        LargeInt Abs() const;
};

#endif

LargeInt.C

#include "LargeInt.h"

// Count Digits
template <typename T>
Counter helper_templates::TCountDigits(T x)
{
    Counter c = kDefaultCounterValue;
    while(x)
    {
        x /= kRadix;
        c++;
    }
    return c;
}

// Get Sign
template <typename T>
Sign helper_templates::TGetSign(T x)
{
    long long mask = 0;
    mask |= 1 << ((sizeof(x) * kByteSize) - 1);
    return (mask & x) >> ((sizeof(x) * kByteSize) - 1);
}

/*
 * Constructors
 */

 // Default
LargeInt::LargeInt()
    : sign_(kSignPositive), length_(kMinLength), data_(new Digit[kMinLength])
{
     data_[kFirstIndex] = kDefaultDigitValue;
}

// Copy
LargeInt::LargeInt(const LargeInt& x)
    : sign_(x.sign_), length_(x.length_), data_(new Digit[x.length_])
{
    for(Index i = kFirstIndex; i < length_; i++)
    {
        data_[i] = x.data_[i];
    }
}

// Copy and Resize
LargeInt::LargeInt(const Sign sign, const size_t length, const Digit* data)
    : sign_(sign), length_(length), data_(new Digit[length_])
{
    for(Index i = kFirstIndex; i < length_; i++)
    {
        data_[i] = data[i];
    }
}

// Integer Type
LargeInt::LargeInt(long long x)
    : sign_(helper_templates::TGetSign(x)),
        length_(helper_templates::TCountDigits(x)),
        data_(new Digit[length_])
{
    if(sign_ == kSignNegative)
    {
        x = -x;
    }
    for(Index i = kFirstIndex; i < length_; i++)
    {
        Digit d = x % kRadix;
        data_[i] = d;
        x /= kRadix;
    }
}

/*
 * Destructor
 */

LargeInt::~LargeInt()
{
    delete [] data_;
}

/*
 * Operators
 */

// Assignment
LargeInt& LargeInt::operator=(const LargeInt& x)
{
    if(this != &x)
    {
        this->sign_ = x.sign_;
        this->length_ = x.length_;
        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }
    }
    return *this;
}

// Negation
LargeInt LargeInt::operator-()
{
    return LargeInt(!this->sign_, this->length_, this->data_);
}

// Addition
LargeInt operator+(LargeInt x, const LargeInt& y)
{
    return x += y;
}

// Addition Assignment
LargeInt& LargeInt::operator+=(const LargeInt& x)
{
    LargeInt sum;
    Digit d;
    Digit carry = kCarryFalse;
    Index i;
    if(this->sign_ == kSignPositive && x.sign_ == kSignPositive)
    {
        if(*this >= x)
        {
            sum.length_ = this->length_ + kMinLength;
            for(i = kFirstIndex; i < x.length_; i++)
            {
                d = this->data_[i] + x.data_[i] + carry;
                if(d > kMaxDigitValue)
                {
                    d %= kRadix;
                    carry = kCarryTrue;
                }
                else
                {
                    carry = kCarryFalse;
                }
                sum.data_[i] = d;
            }
            while(i < this->length_)
            {
                d = this->data_[i] + carry;
                if(d > kMaxDigitValue)
                {
                    d %= kRadix;
                    carry = kCarryTrue;
                }
                else
                {
                    carry = kCarryFalse;
                }
                sum.data_[i] = d;
                i++;
            }
            if(!carry)
            {
                *this = LargeInt(sum.sign_, sum.length_ - kMinLength,
                    sum.data_);
            }
            else
            {
                *this = sum;
            }
        }
        else
        {
            *this = x + *this;
        }
    }
    else if(this->sign_ == kSignPositive)
    {
        *this = *this - x;
    }
    else if(x.sign_ == kSignPositive)
    {
        *this = x - *this;
    }
    else
    {
        *this = -(x.Abs() + this->Abs());
    }
    return *this;
}

// Subtraction
LargeInt operator-(LargeInt x, const LargeInt& y)
{
    return x -= y;
}

// Subtraction Assignment
LargeInt& LargeInt::operator-=(const LargeInt& x)
{
    LargeInt difference;
    Digit d;
    Digit borrow = kBorrowFalse;
    Index i;
    if(x.sign_ == kSignNegative)
    {
        *this = *this + x.Abs();
    }
    else if(this->sign_ == kSignNegative)
    {
        *this = -(this->Abs() + x);
    }
    else
    {
        if(*this > x)
        {
            difference.length_ = this->length_;
            for(i = kFirstIndex; i < x.length_; i++)
            {
                d = this->data_[i] - x.data_[i] - borrow;
                if(d < kDefaultDigitValue)
                {
                    d += kRadix;
                    borrow = kBorrowTrue;
                }
                else
                {
                    borrow = kBorrowFalse;
                }
                difference.data_[i] = d;
            }
            while(i < this->length_)
            {
                d = this->data_[i] - borrow;
                if(d < kDefaultDigitValue)
                {
                    d += kRadix;
                    borrow = kBorrowTrue;
                }
                else
                {
                    borrow = kBorrowFalse;
                }
                difference.data_[i] = d;
                i++;
            }
            for(i = difference.length_; i > kFirstIndex; i--)
            {
                if(difference.data_[i - 1] == kDefaultDigitValue)
                {
                    difference.length_--;
                }
                else
                {
                    break;
                }
            }
            *this = LargeInt(kSignPositive, difference.length_,
                difference.data_);
        }
        else if(x > *this)
        {
            *this = -(x - *this);
        }
        else
        {
            *this = LargeInt();
        }
    }
    return *this;
}

// Preincrement
LargeInt& LargeInt::operator++()
{
    *this += 1;
    return *this;
}

// Postincrement
LargeInt LargeInt::operator++(int)
{
    LargeInt temp(*this);
    ++*this;
    return temp;
}

// Predecrement
LargeInt& LargeInt::operator--()
{
    *this -= 1;
    return *this;
}

// Postdecrement
LargeInt LargeInt::operator--(int)
{
    LargeInt temp(*this);
    --*this;
    return temp;
}

// Not
bool LargeInt::operator!()
{
    bool isNot;
    if(*this == LargeInt())
    {
        isNot = true;
    }
    else
    {
        isNot = false;
    }
    return isNot;
}

// Equality
bool operator==(const LargeInt& x, const LargeInt& y)
{
    bool isEqual;
    if(x.sign_ != y.sign_)
    {
        isEqual = false;
    }
    else if(x.length_ != y.length_)
    {
        isEqual = false;
    }
    else
    {
        for(Index i = kFirstIndex; i < x.length_; i++)
        {
            if(x.data_[i] != y.data_[i])
            {
                isEqual = false;
                break;
            }
            isEqual = true;
        }
    }
    return isEqual;
}

// Inequality
bool operator!=(const LargeInt& x, const LargeInt& y)
{
    return !(x == y);
}

// Greater Than
bool operator>(const LargeInt& x, const LargeInt& y)
{
    bool isGreater;
    if(x.sign_ == kSignPositive && y.sign_ == kSignPositive)
    {
        if(x.length_ == y.length_)
        {
            for(Index i = x.length_; i > kFirstIndex; i--)
            {
                if(x.data_[i - i] > y.data_[i - 1])
                {
                    isGreater = true;
                    break;
                }
                else
                {
                    isGreater = false;
                }
            }
        }
        else if(x.length_ > y.length_)
        {
            isGreater = true;
        }
        else
        {
            isGreater = false;
        }
    }
    else if(x.sign_ == kSignPositive)
    {
        isGreater = true;
    }
    else if(y.sign_ == kSignPositive)
    {
        isGreater = false;
    }
    else
    {
        isGreater = y.Abs() > x.Abs();
    }
    return isGreater;
}

// Greater Than or Equal To
bool operator>=(const LargeInt& x, const LargeInt& y)
{
    return (x > y) || (x == y);
}

// Less Than
bool operator<(const LargeInt& x, const LargeInt& y)
{
    return y > x;
}

// Less Than or Equal To
bool operator <=(const LargeInt& x, const LargeInt& y)
{
    return (x < y) || (x == y);
}

// Insertion
std::ostream& operator<<(std::ostream& out, const LargeInt& x)
{
    if(x.sign_ == kSignNegative)
    {
        out << '-';
    }
    for(Index i = x.length_; i > kFirstIndex; i--)
    {
        out << +x.data_[i - 1];
    }
    return out;
}

/*
 * Functions
 */

// Absolute Value
LargeInt LargeInt::Abs() const
{
    return LargeInt(kSignPositive, this->length_, this->data_);
}

Answer 1

The only things I am unwilling to change:

• Storing the data as a dynamic char array.
• The attributes of the operators (friend, overloaded, return type, parameters).

Well there is not much point doing more of a review. As both of these things are done incorrectly to start with. There are some major problems here to start with.

Storing

Separation of concerns is basically about a class only doing one thing. It either does resource allocation or business logic. Your class is doing both and as a result doing it badly.

Also there is already a specific class that does exactly this std::vector<char>. This class is highly efficient highly tested and is going to beat your memory management every time (unless you are experimenting you should be using it).

You miss move semantics. Which makes your code less efficient than it could be.

You also don't have the concept of capacity so you can't preallocate and must reallocate the correct size all the time which means sizing all the time which is very inefficient.

Friendship.

Your use of friendship is inconsistent. As a result it behaves differently than you would expect from (if you expect it to work like built in types).

int x = 5;
int y = 6;
int z = 3;

y = x += z; // This should work.

// Now with your type.

int      x = 5;
LargeInt y = 6;
LargeInt z = 3;

y = x += z; // Not sure why this would not work.

Assignment operator is broken

LargeInt& LargeInt::operator=(const LargeInt& x)
{
    if(this != &x)
    {
        this->sign_ = x.sign_;
      
        // This is wrong.
        // This is the size of the allocated area of memory.
        // If you don't keep this accurate you are going to 
        // overwrite the end of the array if you are not careful
        // You are mixing the concept of size and capacity into a
        // single variable.
        this->length_ = x.length_;


        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }
    }
    return *this;
}

Algorithms.

You spend way to much time re-writing the same loop.

        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }

Much easier to use algorithms to all this kind of work.

        std::copy(x.data + kFirstIndex, x.data + length, data);

DRY

Is the += operator not basically the same as the -= operator? I am sure you can reuse about 90% of that code.

Operator !

If you have this pattern

if (x)
      return true;
else  return false;

This can be replaced with:

return x;

The test itself is very ineffecient:

if (*this == LargeInt())

Here you are creating a LargeInt() object each time you do the test. Which means memory allocation and de-allocation every time. It may be worth creating a static function object so that it is only created once.

Minus 0

Also is -0 not the same as +0 (in terms of testability). I don't think your test actually gets that correct.

LargeInt   x;        // +0
LargeInt   y = -x;   // -0

if (x == y)
{
    // I would expect this to be true.
    // If you expect this to be different then I would document
    // that fact somewhere.
}

Enum

The following could all be enum values.

const bool kSignPositive = 0;
const bool kSignNegative = 1;
const bool kCarryTrue = 1;
const bool kCarryFalse = 0;
const bool kBorrowTrue = 1;
const bool kBorrowFalse = 0;

Radix

Using a radix of 10 is very eneffecient.

const Digit kDefaultDigitValue = 0;
const Digit kMinDigitValue = 0;
const Digit kMaxDigitValue = 9;
const Digit kRadix = 10;

This not only causes extra storage but also extra operations when moving through each digit.