Big Int implementation, how to handle leading zeros?

286 views Asked by At

In my quest to learn how to make a big integer class I am yet faced with another problem. This time I know how things work and they work well except for a simple big problem: how do I handle leading zeros?

Example: imagine I have a vector of ints and I decide that each int can only have 3 digits each, thus making 1000 the limit where it overflows. If I sum 445 and 555 I get 1000, then I subtract 1000 and I got 0 and a carry of 1. My problem is, how do I represent 000?

I thought about adding a string member to my class: the idea would be turning the numbers into strings, compare their sizes, update the string and then add the leading zeros. However I don't know how good this solution is.

To wrap it all, what are your thoughts about what I've achieved so far?

    // Input strings:
    // 73864783264783264738264738246387246827364872364
    // 744444444432432424234234324234344346

    std::list<long long unsigned> data;        

    void split(std::string p_input) {
        if (p_input.back() == '-') {
            p_input.pop_back();
            positive = !positive;
        }
        reverse(begin(p_input), end(p_input));
        for (size_t i {}; i < p_input.size(); i += 19) {
            std::string qq {p_input.substr(i, 19)};
            reverse(begin(qq), end(qq));
            data.push_front(stoull(qq));
        }
    }

    big_int & operator +=(big_int & p_input) {
        if (data.size() < p_input.data.size()) {
            std::swap(data, p_input.data);
        }
        if (p_input.data.size() != data.size()) {
            size_t size {data.size() - 1};
            while (size != 0) {
                p_input.data.push_front(0);
                --size;
            }
        }

// 73 864 783 265 527 709 182 697 170 670 621 481 151 599 216 710
// 73 864 783 265 527 709 182 697 170 67  621 481 151 599 216 710
//                                      ^
//                                      Best way to fix missing zero/s?
        auto arit {rbegin(data)};
        auto brit {rbegin(p_input.data)};
        unsigned carry {};
        while (arit != rend(data)) {
            long long unsigned result {*arit + *brit + carry};
            if (result >= 10000000000000000000) {
                *arit = result - 10000000000000000000;
                carry = 1;
            } else {
                *arit = result;
                carry = 0;
            }
            ++arit;
            ++brit;
        }
        return *this;
    }
0

There are 0 answers