BigInt class in C++

Question

I made a BigInt class that supports almost all functions an int would.

The code seems too bulky and there might be a few bugs lurking here and there.
I would like to simplify my code as much as possible and increase performance.

#include <iostream>
#include <algorithm>

class BigInt {
public:
    bool neg = false;
    std::string number = "0";

    BigInt(){}

    BigInt(const BigInt& other){
        this -> neg = other.neg;
        this -> number = other.number;
    }

    BigInt(int number){
        if(number < 0){
            this -> neg = true;
            number *= -1;
        }

        if(number == 0){
            this -> number = "0";
            return;
        }

        this -> number = "";

        while(number > 0){
            this -> number += (number % 10) + '0';
            number /= 10;
        }
    }

    BigInt(long long int number){
        if(number < 0){
            this -> neg = true;
            number *= -1;
        }

        if(number == 0){
            this -> number = "0";
            return;
        }

        this -> number = "";

        while(number > 0){
            this -> number += (number % 10) + '0';
            number /= 10;
        }
    }

    BigInt(unsigned long long int number){
        if(number < 0){
            this -> neg = true;
            number *= -1;
        }

        if(number == 0){
            this -> number = "0";
            return;
        }

        this -> number = "";

        while(number > 0){
            this -> number += (number % 10) + '0';
            number /= 10;
        }
    }

    BigInt(const char *number){
        std::string number_(number);
        *(this) = number_;
    }

    BigInt(std::string number){
        while(number[0] == '-'){
            this -> neg = !this -> neg;
            number.erase(0, 1);
        }

        reverse(number.begin(), number.end());

        while(number.size() > 1 && number[number.size() - 1] == '0')
            number.erase(number.size() - 1, number.size());

        if(number == "")
            number = "0";

        this -> number = number;

        if(number == "0")
            this -> neg = false;
    }

    friend bool operator == (BigInt first, BigInt second){
        return first.number == second.number && second.neg == first.neg;
    }

    friend bool operator != (BigInt first, BigInt second){
        return !(first == second);
    }

    friend bool operator < (BigInt first, BigInt second){
        if(first.neg && !second.neg) return true;
        if(!first.neg && second.neg) return false;

        if(first.neg && second.neg){
            first.neg = false;
            second.neg = false;

            return first > second;
        }

        if((first.number).size() < (second.number).size()) return true;
        if((first.number).size() > (second.number).size()) return false;

        std::string temp1 = first.number; reverse(temp1.begin(), temp1.end());
        std::string temp2 = second.number; reverse(temp2.begin(), temp2.end());

        for(unsigned int i = 0; i < temp1.size(); i++)
            if(temp1[i] < temp2[i])
                return true;
            else if(temp1[i] > temp2[i])
                return false;

        return false;
    }

    friend bool operator <= (BigInt first, BigInt second){
        return (first == second) || (first < second);
    }

    friend bool operator > (BigInt first, BigInt second){
        if(!first.neg && second.neg) return true;
        if(first.neg && !second.neg) return false;

        if(first.neg && second.neg){
            first.neg = false;
            second.neg = false;

            return first < second;
        }

        if((first.number).size() > (second.number).size()) return true;
        if((first.number).size() < (second.number).size()) return false;

        std::string temp1 = first.number; reverse(temp1.begin(), temp1.end());
        std::string temp2 = second.number; reverse(temp2.begin(), temp2.end());

        for(unsigned int i = 0; i < temp1.size(); i++)
            if(temp1[i] > temp2[i])
                return true;
            else if(temp1[i] < temp2[i])
                return false;

        return false;
    }

    friend bool operator >= (BigInt first, BigInt second){
        return (first == second) || (first > second);
    }

    void operator = (unsigned long long int number){
        if(number < 0){
            this -> neg = true;
            number *= -1;
        }

        this -> number = "";

        while(number > 0){
            this -> number += (number % 10) + '0';
            number /= 10;
        }
    }

    friend std::istream& operator >> (std::istream& in, BigInt &bigint){
        std::string number; in >> number;

        bigint.neg = false;

        while(number[0] == '-'){
            bigint.neg = !bigint.neg;
            number.erase(0, 1);
        }

        reverse(number.begin(), number.end());

        while(number.size() > 1 && number[number.size() - 1] == '0')
            number.erase(number.size() - 1, number.size());

        bigint.number = number;

        if(number == "0")
            bigint.neg = false;

        return in;
    }

    friend std::ostream& operator << (std::ostream& out, const BigInt &bigint){
        std::string number = bigint.number;
        reverse(number.begin(), number.end());

        if(bigint.neg)
            number = '-' + number;

        out << number;

        return out;
    }

    friend void swap(BigInt &first, BigInt &second){
        BigInt temp(first);

        first = second;
        second = temp;
    }

    friend BigInt abs(BigInt bigint){
        bigint.neg = false;

        return bigint;
    }

    friend BigInt operator + (BigInt first, BigInt second){
        bool neg = false;

        if(!first.neg && second.neg){
            second.neg = false; return first - second;
        }

        if(first.neg && !second.neg){
            first.neg = false; return second - first;
        }

        if(first.neg && second.neg){
            neg = true;
            first.neg = second.neg = false;
        }

        int n = first.number.size();
        int m = second.number.size();

        int carry = 0;

        std::string result;

        for(int i = 0; i < std::max(n, m); i++){
            int add = carry;

            if(i < n) add += first.number[i] - '0';
            if(i < m) add += second.number[i] - '0';

            carry = add / 10;

            result += add % 10 + '0';
        }

        if(carry != 0)
            result += carry + '0';

        reverse(result.begin(), result.end());

        BigInt result_(result);
        result_.neg = neg;

        return result_;
    }

    friend BigInt operator + (BigInt bigint){
        return bigint;
    }

    friend BigInt operator - (BigInt first, BigInt second){
        if(second.neg){
            second.neg = false;
            return first + second;
        }

        if(first.neg){
            second.neg = true;
            return first + second;
        }

        bool neg = false;

        if(first < abs(second)){
            neg = true;

            swap(first, second);
            first = abs(first);
        }

        int n = first.number.size();
        int m = second.number.size();

        int carry = 0;

        std::string result;

        for(int i = 0; i < std::max(n, m); i++){
            int add = carry;

            if(i < n) add += first.number[i] - '0';
            if(i < m) add -= second.number[i] - '0';

            if(add < 0){
                carry = -1;
                result += add + 10 + '0';
            }

            else {
                carry = 0;
                result += add + '0';
            }
        }

        reverse(result.begin(), result.end());

        BigInt result_(result);

        result_.neg = neg;

        return result_;
    }

    friend BigInt operator - (BigInt second){
        BigInt first("0"); return first - second;
    }

    friend BigInt operator * (BigInt first, BigInt second){
        bool neg = first.neg != second.neg;

        first.neg = false;
        second.neg = false;

        int n = first.number.size();
        int m = second.number.size();

        BigInt result_;

        for(int i = 0; i < n; i++){
            int carry = 0;

            std::string result;

            for(int j = 0; j < i; j++)
                result += '0';

            for(int j = 0; j < m; j++){
                int add = carry + (first.number[i] - '0') * (second.number[j] - '0');

                carry = add / 10;

                result += add % 10 + '0';
            }

            if(carry != 0)
                result += carry + '0';

            reverse(result.begin(), result.end());

            BigInt current(result);

            result_ += current;
        }

        result_.neg = neg;

        return result_;
    }

    friend BigInt operator / (BigInt first, BigInt second){
        if(second == "0")
            throw "Division with 0";

        bool neg = first.neg != second.neg;

        first.neg = false;
        second.neg = false;

        BigInt quotient;

        int i = first.size() - 1;

        BigInt current(first.number[i] - '0');

        --i;

        while(true){
            BigInt result = current;

            bool l = false;

            while(result < second && i >= 0){
                result = result * 10 + (first.number[i--] - '0');

                if(l)
                    quotient *= 10;

                l = true;
            }

            int c = 0;

            BigInt result_(result);

            while(result_ >= second){
                result_ -= second;
                c++;
            }

            quotient = quotient * 10 + c;

            current = result_;

            if(i < 0)
                break;
        }

        quotient.neg = neg;

        return quotient;
    }

    friend BigInt operator % (BigInt first, BigInt second){
        if(second == "0")
            throw "Modulo with 0";

        first.neg = false;
        second.neg = false;

        int i = first.size() - 1;

        BigInt current(first.number[i] - '0');

        --i;

        while(true){
            BigInt result = current;

            while(result < second && i >= 0)
                result = result * 10 + (first.number[i--] - '0');

            int c = 0;

            BigInt result_(result);

            while(result_ >= second){
                result_ -= second;
                c++;
            }

            current = result_;

            if(i < 0)
                break;
        }

        current.neg = second.neg;

        return current;
    }

    friend BigInt pow(BigInt x, BigInt y, BigInt mod = 0){
        if(mod != 0)
            x %= mod;

        BigInt res = 1;

        while(y != 0){
            if(y % 2 == 1){
                res *= x;

                if(mod != 0)
                    res %= mod;
            }

            x *= x;

            if(mod != 0)
                x %= mod;

            y /= 2;
        }

        return res;
    }

    friend BigInt operator & (BigInt first_, BigInt second_){
        std::string first = first_.int_to_base(2);
        std::string second = second_.int_to_base(2);

        unsigned int n = std::min(first.size(), second.size());

        reverse(first.begin(), first.end());
        reverse(second.begin(), second.end());

        std::string result(n, '~');

        for(unsigned int i = 0; i < n; i++){
            if(first[i] == '1' && second[i] == '1')
                result[i] = '1';
            else
                result[i] = '0';
        }

        reverse(result.begin(), result.end());

        return BigInt().base_to_int(result, 2);
    }

    friend BigInt operator | (BigInt first_, BigInt second_){
        std::string first = first_.int_to_base(2);
        std::string second = second_.int_to_base(2);

        unsigned int n = std::max(first.size(), second.size());

        reverse(first.begin(), first.end());
        reverse(second.begin(), second.end());

        std::string result(n, '~');

        for(unsigned int i = 0; i < n; i++){
            if(first.size() <= i || second.size() <= i){
                if(first.size() > i) result[i] = first[i];
                if(second.size() > i) result[i] = second[i];

                continue;
            }

            if(first[i] == '1' || second[i] == '1')
                result[i] = '1';
            else
                result[i] = '0';
        }

        reverse(result.begin(), result.end());

        return BigInt().base_to_int(result, 2);
    }

    friend BigInt operator ^ (BigInt first_, BigInt second_){
        std::string first = first_.int_to_base(2);
        std::string second = second_.int_to_base(2);

        unsigned int n = std::max(first.size(), second.size());

        reverse(first.begin(), first.end());
        reverse(second.begin(), second.end());

        std::string result(n, '~');

        for(unsigned int i = 0; i < n; i++){
            if(first.size() <= i || second.size() <= i){
                if(first.size() > i){
                    if(first[i] == '0')
                        result[i] = '0';
                    else
                        result[i] = '1';
                }

                if(second.size() > i){
                    if(second[i] == '0')
                        result[i] = '0';
                    else
                        result[i] = '1';
                }

                continue;
            }

            if(first[i] == second[i])
                result[i] = '0';
            else
                result[i] = '1';
        }

        reverse(result.begin(), result.end());

        return BigInt().base_to_int(result, 2);
    }

    friend BigInt operator << (BigInt first, BigInt second){
        BigInt x = pow(2, second);

        return first * x;
    }

    friend BigInt operator >> (BigInt first, BigInt second){
        BigInt x = pow(2, second);

        return first / x;
    }

    int to_int(BigInt bigint){
        int n = 0;

        for(int i = bigint.number.size() - 1; i >= 0; i--)
            n = (n * 10) + (bigint.number[i] - '0');

        return n;
    }

    std::string int_to_base(int base){
        std::string result;

        BigInt bigint(*this);

        while(bigint > 0){
            BigInt r = bigint % base;

            if(r >= 10)
                result += (char)(to_int(r / 10) + 'A');
            else
                result += (char)(to_int(r) + '0');

            bigint /= base;
        }

        reverse(result.begin(), result.end());

        return result;
    }

    BigInt base_to_int(std::string str, int base){
        BigInt result;

        for(unsigned int i = 0; i < str.size(); i++){
            BigInt add;

            if('0' <= str[i] && str[i] <= '9')
                add += str[i] - '0';
            else
                add += (str[i] - 'A') + 10;

            result = result * base + add;
        }

        return result;
    }

    int size(){
        return this -> number.size();
    }

    void operator ++ (){*(this) = *(this) + 1;}
    void operator -- (){*(this) = *(this) - 1;}

    void operator += (BigInt bigint){*(this) = *(this) + bigint;}
    void operator -= (BigInt bigint){*(this) = *(this) - bigint;}

    void operator *= (BigInt bigint){*(this) = *(this) * bigint;}
    void operator /= (BigInt bigint){*(this) = *(this) / bigint;}
    void operator %= (BigInt bigint){*(this) = *(this) % bigint;}

    void operator &= (BigInt bigint){*(this) = *(this) & bigint;}
    void operator |= (BigInt bigint){*(this) = *(this) | bigint;}
    void operator ^= (BigInt bigint){*(this) = *(this) ^ bigint;}

    void operator <<= (BigInt bigint){*(this) = *(this) << bigint;}
    void operator >>= (BigInt bigint){*(this) = *(this) >> bigint;}
};

If I'm missing any functions, please point it out!

Answer 1

We use std::string without including <string> - a possible portability bug.

Representation as a string of char isn't very compact, so we're quite wasteful of space for large numbers.

The modifying operators (++, *=, etc) all return void, but it's normal and expected that they return a reference to *this (act like the integers).

It's suspect to have a copy-constructor but no copy-assignment operator. In this case, the copy constructor adds no value and should be removed, allowing the compiler to generate default copy and move operations.

Some more that can be removed: we could get away with constructors taking std::intmax_t and std::uintmax_t and removing those that accept shorter integers. Standard integer promotion would then work for us.

It's probably not worth accepting const char*, given the implicit conversion to std::string.

Consider making some or all of the constructors explicit. Certainly the construction from string should be explicit.

In BigInt(std::string number), consider that it's more efficient to remove characters from the end of std::string, so reverse it before counting - signs (and we can use s.back() to access the last character more readably than s[s.size() - 1]).

There's no need to sprinkle this-> all over the place - that's just visual clutter. I would recommend renaming either the member or the parameter to many methods so that they are not both called number.

This comparison is never true:

BigInt(unsigned long long int number){
    if(number < 0){

An unsigned type is never less than 0. This is likely a symptom that you're compiling without a good set of warnings; I'm using g++ -Wall -Wextra -Wpedantic -Warray-bounds -Weffc++.

There's a more subtle issue here:

BigInt(long long int number){
    if(number < 0){
        this -> neg = true;
        number *= -1;
    }

On most systems, LLONG_MIN is less than -LLONG_MAX, meaning that there's at least one value that doesn't become positive when multiplied by -1.

Comparison operators should take const references, rather than needlessly copying:

friend bool operator == (const BigInt& first, const BigInt& second){
    return first.number == second.number && second.neg == first.neg;
}

And it's normal to make them member functions rather than friends if they need access to the object's private members:

bool operator==(const BigInt& other) const
{
    return number == other.number && neg == other.neg;
}

The inequality operators are somewhat inefficient - there's no need to re-implement std::string::operator<() in there. In fact, if we use <algorithm>, we don't need to make copies of the strings to reverse them; just use reverse iterators instead:

bool operator<(const BigInt& other) const
{
    if (neg != other.neg) {
        return neg;
    }
    if (neg) {
        // TODO: avoid making copies here
        return -other < *this;
    }

    if (number.size() != other.number.size()) {
        return number.size() < other.number.size();
    }

    return std::lexicographical_compare(number.rbegin(), number.rend(),
                                        other.number.rbegin(), other.number.rend());
}

We don't need to duplicate this logic to implement operator>():

bool operator>(const BigInt& other) const
{
    return other < *this;
}

bool operator>=(const BigInt& other) const
{
    return other <= *this;
}

The streaming-in operator, >> re-does much work that's done in the constructor. Here's a simpler version, that removes the duplication:

friend std::istream& operator>>(std::istream& in, BigInt &bigint)
{
    std::string number;
    in >> number;
    bigint = std::move(number);
    return in;
}

We don't need to use a temporary in swap() (and what we have is similar what std::swap() would give us for free, except copying instead of moving). Here's a more memory-efficient version:

void swap(BigInt &other)
{
    std::swap(neg, other.neg);
    std::swap(number, other.number);
}

It's more usual to implement + in terms of +=, rather than the other way around. Again, that reduces the amount of temporary memory needed.

Answer 2

Using a power-of-10 base for extended precision is unusual, and only a good choice for specific use-cases (like if you mostly want to convert to decimal strings, or if multiplying / dividing by 10 is a major part of your workload).

Choosing 10^1 specifically wastes more than half the bits in a char, and leads to a huge amount of operations for large numbers. log2(10) = 3.3 useful bits of data per char. But char is typically (and at least) 8-bit in C++. You could have used base 100 in char elements. (Then conversion to an ASCII string would convert each chunk to 2 decimal digits, with one normal-sized division per chunk.)

Even if you were to choose base 10, you likely don't want to store as actual ASCII; your number isn't ready-to-print anyway so you have the worst of both worlds: overhead during each step, and you still have to reverse (and maybe print a leading -) to produce a std::string in printing order. You could add '0' during the reversal. (And do out << '-' instead of prepending it to a potentially-long string.) The one advantage of std::string over std::vector is that common implementations store the string bytes within the object for small strings, instead of as a separate allocation.

(Related: Vectorize random init and print for BigInt with decimal digit array, with AVX2? has C with Intel intrinsics for a cache-blocked byte-reverse of an array into a tmp buf for fwrite, and for converting a vectorized xorshift128+ PRNG result to a vector of decimal digits. That part was an interesting problem to manually vectorize, but actual BigInt math ops can't easily be vectorized with SIMD. See @Mysticial's answer on Can long integer routines benefit from SSE? for some techniques that do work.)

---

A more sensible choice if you still care about easy / fast conversion to decimal is base 10^9 in uint32_t chunks. I used that in x86 asm for a code golf challenge of printing the first 1000 digits of Fibonacci(10^9) ; as the number got big, I could discard the least-significant 9 decimal digits by dropping one chunk, effectively dividing by 10^9 with a right shift by 1 chunk.

Conversion to a decimal string can convert each chunk separately to 9 digits (including leading zeros), avoiding division of the entire BigInt by 10. And letting you start with the most-significant chunk to get digit-groups in printing order.

Other than memory bandwidth / cache footprint, + between uint32_t integers costs about the same as (or less than) + between unsigned char, the way you're using it in a loop. (i.e. where it compiles to a normal add instruction instead of optimizing into part of something else.) Getting ~30 result bits for the same price as 3.3 bits is a huge win.

---

You might want to take a look at how GMP (the GNU MultiPrecision library) is implemented. Mostly with hand-written asm for the lowest levels, making efficient carry in/out easier, but with binary chunks (aka limbs) of the widest type the machine can do efficiently. (That's often unsigned long int). They do have pure C fallback implementations of everything, for platforms where they don't have asm.

---

And/or you might want to look at how the CPython interpreter implements extended precision; without the benefit of asm to do carry in/out to a chunk that uses the full range of a type, it's easier to use chunks of base 2^30. Using uint_least32_t is probably a good idea; it's guaranteed to be large enough to hold values up to 2^30. (And will typically be an efficient size like unsigned int, although you might consider loading array elements into local temporaries of uint_fast32_t inside your loop. Or not; some x86-64 implementations unwisely make uint_fast32_t a 64-bit type. You'll need a 64-bit type anyway for multiply and divide, though).

(You don't want to use a type that could potentially be 64-bit if you're only using 30 bits; that would waste more than half the space instead of just a couple bits.) CPython also has a fallback to using 15-bit chunks; I wouldn't bother with that especially for a toy implementation.

For multiply, full_result = x * (unsigned long long)y; doesn't lose any bits. If your compiler has unsigned __int128, using 64-bit chunks means half as many chunks, taking better advantage of 64-bit machines.

For addition, you just do the add normally, then sum & ((1UL<<30) - 1) to modulo this limb, and sum >> 30 to get the carry-in for the next limb.

• https://rushter.com/blog/python-integer-implementation/
• https://hg.python.org/cpython/file/db842f730432/Include/longintrepr.h#l10 has useful comments, too.

Unlike CPython, you probably don't need special fast-paths for single-limb integers. Unless you expect people to use your class for numbers that are usually small but can be big.

---

And BTW, your divide and modulo algorithms are really bad. For a narrow (single-limb) divisor, you can use the remainder of one division as the high half of the dividend for the next lower limb. You don't need repeated subtraction. There are lots of assembly-language questions on Stack Overflow about how to implement large divisions in terms of a 2N / N => N-bit division. (C++ of course doesn't have that, just use a 2N bit type and let your compiler (fail to) optimize it.)

(The general case of extended-precision division is hard, though, where the divisor is multiple limbs. Yet another reason to use large limbs so more divisors can be single-limb.)

Also, when you do % 2 as part of some other algorithm, you should just be looking at the low bit of the lowest limb!! For divisors that are factors of your base (2 and 5 for your case for base 10), you only need to look at the low limb. Numbers that end with an even digit are divisible by 2. Numbers that end with 0 or 5 are divisible by 5.

What should be checking a single bit in your multiply loop instead becomes a huge copy and iterate over the whole BigInt.

Answer 3

You are using a string as the underlying data structure. It's wasteful in memory (using 10 possible values out of 256). It's also super-slow, unless your primary use of BigInt is to print its decimal representation.

You should have chosen something like

class BigInt {
    long number;
    std::vector<unsigned long> extra; // for when number overflows
};

Discussing the rest kinda doesn't make sense in light of this.

Answer 4

These constructors are basically the same:

BigInt(int number)
BigInt(long long int number)
BigInt(unsigned long long int number)

So why not templatize them so you only have to write them once:

template<typename I>
BigInt(I number)

If you are worried about non integer types you can add a constraint to make sure that I is always integers.

template<typename I>
require std::is_integer<I> // C++20
BigInt(I number)

or

template<typename I, typename = std::enable_if_t<std::is_integral<I>::value>>
BigInt(I number)

Manually converting to a string:

    while(number > 0){
        this -> number += (number % 10) + '0';
        number /= 10;
    }

Seems like a lot of work:

    // This also works for zero.
    this->number = std::to_string(number);

You can then check the first character for '-' to set the negative flag (and then remove it).