Template số nguyên lớn (Bigint)🤠

Bạn mệt mỏi khi phải chuyển sang python mỗi khi gặp một bài toán yêu cầu xử lý số nguyên lớn? Bạn lười viết hàm xử lý số nguyên lớn? Trong bài blog này, mình sẽ chia sẻ template bigint của mình mà các bạn có thể tha hồ xài!!

Credits

Template Bigint của mình dựa trên “Num” (Andrew He) và bản cải tiến của Nguyễn Huy trên diễn đàn VNOI. Mình đã hoàn thiện thêm bằng cách sửa một số lỗi tiềm ẩn và thêm các thao tác bitwise cũng như bitshift😎

Template

class bigint {
public:
    using word = uint64_t;
    static constexpr word BASE_DIGIT = 10;
    vector<word> words;
    bool is_negative = false;
    static constexpr bool SAFE_INITIALIZATION = false;

    bigint() : is_negative(false) {
    };

    bigint(const size_t n, const word w, const bool negative = false) : words(n, w), is_negative(negative) {
    }

    [[maybe_unused]] bigint(const word* a, const word* b, const bool negative = false) : words(a, b),
        is_negative(negative) {
    }

    bigint(const bigint& a) { words = a.words, is_negative = a.is_negative; }

    bigint& operator=(const bigint& a) = default;

    static constexpr char MIN_NUMERIC_CHARACTER = '0';

    template<class type>
    // ReSharper disable once CppNonExplicitConvertingConstructor
    bigint(type number) {
        static_assert(is_same_v<type, int8_t> || is_same_v<type, int16_t> || is_same_v<type, int32_t> || is_same_v<type, int64_t>, "type must be int8, int16, int32, or int64");
        if (number < 0) {
            is_negative = true;
            word val = -static_cast<word>(number);
            if (val > 0) words.push_back(val);
        }
        else if (number > 0) {
            words.push_back(number);
        }
    }

    void read(const string& s) {
        words.clear();
        this->is_negative = false;
        size_t i = 0;
        const size_t end = s.size();
        if (s[i] == '-') {
            ++i;
            is_negative = true;
        }
        for (; i != end; ++i) {
            mul_word(BASE_DIGIT);
            if constexpr (SAFE_INITIALIZATION) {
                assert(isdigit(s[i]));
            }
            word carry = s[i] - MIN_NUMERIC_CHARACTER;
            if (words.empty()) words.resize(1);
            for (size_t j = 0; j < words.size() && carry; j++) carry = add_carry(&words[j], carry);
            if (carry) words.push_back(carry);
            while (!words.empty() && words.back() == 0) words.pop_back();
        }
    }

    [[maybe_unused]] explicit bigint(const string& s) : is_negative(false) { read(s); }

    [[maybe_unused]] explicit bigint(const char* s) : is_negative(false) { read(s); }

    word& operator[](const size_t i) { return words[i]; }

    const word& operator[](const size_t i) const { return words[i]; }

    bool is_zero() const { return words.empty(); }

    bigint& set_negative(const bool b) {
        this->is_negative = b;
        return *this;
    }

    bigint& truncate() {
        while (!words.empty() && words.back() == 0) words.pop_back();
        return *this;
    }

    size_t bit_size() const {
        if (words.empty()) return 0;
        const size_t last = words.size() - 1;
        const size_t result = word_bit_size(words[last]) + last * 64;
        return result;
    }

    static int cmp_abs(const bigint& a, const bigint& b) {
        if (a.words.size() != b.words.size()) {
            return a.words.size() < b.words.size() ? -1 : 1;
        }
        if (a.words.empty()) {
            return 0;
        }
        for (int i = a.words.size() - 1; i >= 0; --i) {
            if (a.words[i] != b.words[i]) {
                return a.words[i] < b.words[i] ? -1 : 1;
            }
        }
        return 0;
    }

    static int cmp(const bigint& a, const bigint& b) {
        if (a.words.empty() && b.words.empty()) return 0;
        if (!a.is_negative && !b.is_negative) return +cmp_abs(a, b);
        if (a.is_negative && b.is_negative) return -cmp_abs(a, b);
        return a.is_negative && !b.is_negative ? -1 : +1;
    }

    static size_t word_bit_size(const word a) {
        for (int i = 64 - 1; i >= 0; i--) {
            if ((a >> i) & 1) return i + 1;
        }
        return 0;
    }

    static word add_carry(word* a, const word b) { return (*a += b) < b; }

    static word sub_carry(word* a, word b) {
        const word tmp = *a;
        return (*a = tmp - b) > tmp;
    }

    static word word_mul_high(const word a, const word b) {
        const word a_high = a >> 32;
        const word a_low = a & UINT_MAX;
        const word b_low = b & UINT_MAX;
        const word b_high = b >> 32;
        word tmp = ((a_low * b_low) >> 32) + a_high * b_low;
        tmp = (tmp >> 32) + ((a_low * b_high + (tmp & UINT_MAX)) >> 32);
        return tmp + a_high * b_high;
    }

    static bigint& add_unsigned_overwrite(bigint& a, const bigint& b) {
        const size_t na = a.words.size();
        const size_t nb = b.words.size();
        size_t i;
        const size_t n = max(na, nb);
        a.words.resize(n);
        word carry = 0;
        for (i = 0; i < nb; i++) {
            carry = add_carry(&a[i], carry);
            carry += add_carry(&a[i], b[i]);
        }
        for (; i < n && carry; i++) carry = add_carry(&a[i], carry);
        if (carry) a.words.push_back(carry);
        return a.truncate();
    }

    static bigint& sub_unsigned_overwrite(bigint& a, const bigint& b) {
        size_t i;
        const size_t nb = b.words.size();
        const size_t na = a.words.size();
        word carry = 0;
        for (i = 0; i < nb; i++) {
            carry = sub_carry(&a[i], carry);
            carry += sub_carry(&a[i], b[i]);
        }
        for (; i < na && carry; i++) carry = sub_carry(&a[i], carry);
        return a.truncate();
    }

    static bigint native_multiple(const bigint& a, const bigint& b) {
        const size_t na = a.words.size();
        const size_t nb = b.words.size();
        const size_t nc = na + nb + 1;
        bigint c(nc, 0, a.is_negative ^ b.is_negative), carries(nc, 0);
        for (size_t ia = 0; ia < na; ia++) {
            for (size_t ib = 0; ib < nb; ib++) {
                const size_t i = ia + ib;
                const size_t j = i + 1;
                carries[i + 1] += add_carry(&c[i], a[ia] * b[ib]);
                carries[j + 1] += add_carry(&c[j], word_mul_high(a[ia], b[ib]));
            }
        }
        return add_unsigned_overwrite(c, carries).truncate();
    }

    static void split(const bigint& a, bigint& lhs, bigint& rhs, const size_t size_) {
        size_t i = 0;
        lhs.words.resize(size_);
        for (size_t j = 0; j < size_ && i < a.words.size(); j++) lhs[j] = a[i++];
        lhs = lhs.truncate();
        rhs.words.resize(a.words.size() - size_);
        for (size_t j = 0; j < a.words.size() - size_ && i < a.words.size(); j++) rhs[j] = a[i++];
        rhs = rhs.truncate();
    }

    static bigint karatsuba_multiple(const bigint& a, const bigint& b) {
        const size_t na = a.words.size();
        const size_t nb = b.words.size();
        const size_t n = max(na, nb);
        size_t m2 = n / 2 + (n & 1);
        bigint a0, a1, b0, b1;
        split(a, a0, a1, m2);
        split(b, b0, b1, m2);
        m2 *= 64;
        const bigint z0 = a0 * b0;
        const bigint z1 = (a0 + a1) * (b0 + b1);
        const bigint z2 = a1 * b1;
        bigint result = z2;
        result <<= m2;
        result += z1 - z2 - z0;
        result <<= m2;
        result += z0;
        return result;
    }

    static constexpr size_t threshold = 20;

    static bigint multiple(const bigint& a, const bigint& b) {
        return (a.words.size() > threshold && b.words.size() > threshold
            ? karatsuba_multiple(a, b)
            : native_multiple(a,
                b));
    }

    static bigint add_signed(const bigint& a, bool a_negative, const bigint& b, bool b_negative) {
        if (a_negative == b_negative) return add_unsigned(a, b).set_negative(a_negative);
        if (cmp_abs(a, b) >= 0) return sub_unsigned(a, b).set_negative(a_negative);
        return sub_unsigned(b, a).set_negative(b_negative);
    }

    bigint& operator>>=(size_t n_bits) {
        if (is_zero() || n_bits == 0) return *this;
        const size_t n_words = n_bits / 64;
        if (n_words >= words.size()) {
            words.resize(0);
            return *this;
        }
        n_bits %= 64;
        if (n_bits == 0) {
            for (size_t i = 0; i < words.size() - n_words; i++) {
                words[i] = words[i + n_words];
            }
        }
        else {
            word low = words[n_words];
            for (size_t i = 0; i < words.size() - n_words - 1; i++) {
                const word high = words[i + n_words + 1];
                words[i] = (high << (64 - n_bits)) | (low >> n_bits);
                low = high;
            }
            words[words.size() - n_words - 1] = low >> n_bits;
        }
        words.resize(words.size() - n_words);
        return truncate();
    }

    bigint& operator<<=(size_t n_bits) {
        if (n_bits == 0) return *this;
        const size_t n_words = n_bits / 64;
        n_bits %= 64;
        const size_t old_size = words.size();
        const size_t n = old_size + n_words + (n_bits != 0);
        words.resize(n);
        if (n_bits == 0) {
            for (size_t i = n; i-- > n_words;) words[i] = words[i - n_words];
        }
        else {
            word high = 0;
            for (size_t i = n - 1; i > n_words; i--) {
                const word low = words[i - n_words - 1];
                words[i] = (high << n_bits) | (low >> (64 - n_bits));
                high = low;
            }
            words[n_words] = high << n_bits;
        }
        for (size_t i = 0; i < n_words; i++) words[i] = 0;
        return truncate();
    }

    static void div_mod(const bigint& generator, bigint denominator, bigint& quotient, bigint& remainder) {
        quotient = 0;
        remainder = generator;
        if (cmp_abs(remainder, denominator) >= 0) {
            int n = static_cast<int>(generator.bit_size() - denominator.bit_size());
            denominator <<= n;
            for (; n >= 0; n--) {
                if (cmp_abs(remainder, denominator) >= 0) {
                    sub_unsigned_overwrite(remainder, denominator);
                    quotient.set_bit(n);
                }
                denominator >>= 1;
            }
        }
        quotient.set_negative(generator.is_negative ^ denominator.is_negative);
        remainder.set_negative(generator.is_negative);
    }

    static void div_mod_half_word(const bigint& generator, bigint& quotient, word& remainder) {
        remainder = 0;
        bigint dst(generator.words.size(), 0);
        for (size_t i = generator.words.size(); i-- > 0;) {
            word dst_word = 0;
            const word src_word = generator[i];

            const word part_0 = src_word >> 32, part_1 = src_word & UINT_MAX;
            remainder <<= 32;
            remainder |= part_0;
            word div_word = remainder / BASE_DIGIT;
            word mod_word = remainder % BASE_DIGIT;
            remainder = mod_word;
            dst_word <<= 32;
            dst_word |= div_word;

            remainder <<= 32;
            remainder |= part_1;
            div_word = remainder / BASE_DIGIT;
            mod_word = remainder % BASE_DIGIT;
            remainder = mod_word;
            dst_word <<= 32;
            dst_word |= div_word;

            dst[i] = dst_word;
        }
        quotient = dst.truncate().set_negative(generator.is_negative);
    }

    static bigint div(const bigint& generator, const bigint& denominator) {
        bigint quotient, remainder;
        div_mod(generator, denominator, quotient, remainder);
        return quotient;
    }

    static bigint mod(const bigint& generator, const bigint& denominator) {
        bigint quotient, remainder;
        div_mod(generator, denominator, quotient, remainder);
        return remainder;
    }

    static bigint add_unsigned(const bigint& a, const bigint& b) {
        bigint result(a);
        return add_unsigned_overwrite(result, b);
    }

    static bigint sub_unsigned(const bigint& a, const bigint& b) {
        bigint result(a);
        return sub_unsigned_overwrite(result, b);
    }

    static bigint add(const bigint& a, const bigint& b) {
        bigint result = add_signed(a, a.is_negative, b, b.is_negative);
        return result;
    }

    static bigint sub(const bigint& a, const bigint& b) {
        bigint result = add_signed(a, a.is_negative, b, !b.is_negative);
        return result;
    }

    bigint& set_bit(const int i) {
        const size_t i_word = i / 64;
        const size_t i_bit = i % 64;
        if (words.size() <= i_word) words.resize(i_word + 1);
        words[i_word] |= static_cast<word>(1) << i_bit;
        return *this;
    }

    void mul_word(const word b) {
        word carry = 0;
        for (word& i : words) {
            const word a = i;
            word tmp = a * b;
            carry = add_carry(&tmp, carry);
            carry += word_mul_high(a, b);
            i = tmp;
        }
        if (carry) words.push_back(carry);
        while (!words.empty() && words.back() == 0) words.pop_back();
    }

    string to_string() const {
        if (words.empty()) return "0";
        string result;
        bigint tmp(*this);
        while (!tmp.words.empty()) {
            word remainder;
            div_mod_half_word(tmp, tmp, remainder);
            result.push_back(static_cast<char>(MIN_NUMERIC_CHARACTER + remainder));
        }
        if (is_negative) result.push_back('-');
        reverse(result.begin(), result.end());
        return result;
    }
    void to_twos_complement(size_t n_bits) {
        if (!is_negative) {
            size_t n_words = (n_bits + 63) / 64;
            if (words.size() < n_words) {
                words.resize(n_words, 0);
            }
            return;
        }

        size_t n_words = (n_bits + 63) / 64;
        if (words.size() < n_words) {
            words.resize(n_words, 0);
        }
        for (size_t i = 0; i < words.size(); ++i) {
            words[i] = ~words[i];
        }
        size_t last_word_bits = n_bits % 64;
        if (last_word_bits > 0) {
            word mask = (static_cast<word>(1) << last_word_bits) - 1;
            words.back() &= mask;
        }
        for (size_t i = 0; i < n_words; ++i) {
            if (++words[i] != 0) break;
        }
        is_negative = false;
        truncate();

    }
    void from_twos_complement(size_t n_bits) {
        if (is_zero()) return;

        size_t sign_bit_word_idx = (n_bits - 1) / 64;
        size_t sign_bit_idx_in_word = (n_bits - 1) % 64;

        if (words.size() <= sign_bit_word_idx || !((words[sign_bit_word_idx] >> sign_bit_idx_in_word) & 1)) {
            is_negative = false;
        }
        else {
            is_negative = true;
            size_t n_words = (n_bits + 63) / 64;

            for (size_t i = 0; i < n_words; ++i) {
                if (words[i]-- != 0) break;
            }

            for (size_t i = 0; i < words.size(); ++i) {
                words[i] = ~words[i];
            }

            size_t last_word_bits = n_bits % 64;
            if (last_word_bits > 0) {
                word mask = (static_cast<word>(1) << last_word_bits) - 1;
                words.back() &= mask;
            }
        }
        truncate();
    }
    bigint operator&(const bigint& other) const {
        if (this->is_zero() || other.is_zero()) {
            return bigint(0);
        }
        bigint a = *this, b = other;
        size_t n_bits = max(a.bit_size(), b.bit_size()) + 1;
        a.to_twos_complement(n_bits);
        b.to_twos_complement(n_bits);

        size_t n_words = (n_bits + 63) / 64;
        bigint result;
        a.words.resize(n_words, 0);
        b.words.resize(n_words, 0);
        result.words.resize(n_words);
        for (size_t i = 0; i < n_words; ++i) {
            result.words[i] = a.words[i] & b.words[i];
        }
        result.from_twos_complement(n_bits);
        return result;
    }
    bigint operator|(const bigint& other) const {
        if (this->is_zero()) {
            return other;
        }
        if (other.is_zero()) {
            return *this;
        }
        bigint a = *this, b = other;
        size_t n_bits = max(a.bit_size(), b.bit_size()) + 1;
        a.to_twos_complement(n_bits);
        b.to_twos_complement(n_bits);

        size_t n_words = (n_bits + 63) / 64;
        bigint result;
        a.words.resize(n_words, 0);
        b.words.resize(n_words, 0);
        result.words.resize(n_words);
        for (size_t i = 0; i < n_words; ++i)
            result.words[i] = a.words[i] | b.words[i];

        result.from_twos_complement(n_bits);
        return result;
    }
    bigint operator^(const bigint& other) const {
        if (this->is_zero()) {
            return other;
        }
        if (other.is_zero()) {
            return *this;
        }
        bigint a = *this, b = other;
        size_t n_bits = max(a.bit_size(), b.bit_size()) + 1;
        a.to_twos_complement(n_bits);
        b.to_twos_complement(n_bits);
        size_t n_words = (n_bits + 63) / 64;
        bigint result;
        a.words.resize(n_words, 0);
        b.words.resize(n_words, 0);
        result.words.resize(n_words);
        for (size_t i = 0; i < n_words; ++i)
            result.words[i] = a.words[i] ^ b.words[i];

        result.from_twos_complement(n_bits);
        return result;
    }
    bigint operator~() const {
        // ~x == -x - 1
        return -(*this) - bigint(1);
    }
    bigint& operator&=(const bigint& other) { *this = *this & other; return *this; }
    bigint& operator|=(const bigint& other) { *this = *this | other; return *this; }
    bigint& operator^=(const bigint& other) { *this = *this ^ other; return *this; }
    bigint operator<<(const bigint& b) const {
        if (b.is_negative || this->is_zero()) {
            return *this;
        }
        if (b.words.size() > 1) {
            return bigint(0);
        }

        size_t shift_val = b.is_zero() ? 0 : b.words[0];
        shift_val %= 64;
        size_t n_bits = this->bit_size() + shift_val + 1;
        bigint temp = *this;
        temp.to_twos_complement(n_bits);
        temp <<= shift_val;

        size_t required_words = (n_bits + 63) / 64;
        if (temp.words.size() > required_words) {
            temp.words.resize(required_words);
        }
        size_t last_word_bits = n_bits % 64;
        if (last_word_bits > 0) {
            if (!temp.words.empty()) {
                word mask = (static_cast<word>(1) << last_word_bits) - 1;
                temp.words.back() &= mask;
            }
        }
        temp.truncate();

        temp.from_twos_complement(n_bits);
        return temp;
    }
    bigint operator>>(const bigint& b) const {
        if (b.is_negative || this->is_zero()) {
            return *this;
        }
        if (b.words.size() > 1) {
            return this->is_negative ? bigint(-1) : bigint(0);
        }
        size_t shift_val = b.is_zero() ? 0 : b.words[0];
        shift_val %= 64;
        if (!this->is_negative) {
            return bigint(*this) >>= shift_val;
        }
        bigint divisor = bigint(1) << shift_val;
        bigint quotient = *this / divisor;
        bigint remainder = *this % divisor;
        if (!remainder.is_zero()) {
            quotient -= 1;
        }
        return quotient;
    }
    bigint& operator+=(const bigint& b) { return *this = add(*this, b); }
    bigint& operator-=(const bigint& b) { return *this = sub(*this, b); }
    bigint& operator*=(const bigint& b) { return *this = multiple(*this, b); }
    bigint& operator/=(const bigint& b) {
        assert(!b.is_zero());
        return *this = div(*this, b);
    }
    bigint& operator%=(const bigint& b) {
        assert(!b.is_zero());
        return *this = mod(*this, b);
    }
    bool operator==(const bigint& b) const { return cmp(*this, b) == 0; }
    bool operator!=(const bigint& b) const { return cmp(*this, b) != 0; }
    bool operator<=(const bigint& b) const { return cmp(*this, b) <= 0; }
    bool operator>=(const bigint& b) const { return cmp(*this, b) >= 0; }
    bool operator<(const bigint& b) const { return cmp(*this, b) < 0; }
    bool operator>(const bigint& b) const { return cmp(*this, b) > 0; }
    bigint operator+(const bigint& b) const { return add(*this, b); }
    bigint operator-(const bigint& b) const { return sub(*this, b); }
    bigint operator*(const bigint& b) const { return multiple(*this, b); }
    bigint operator/(const bigint& b) const {
        assert(!b.is_zero());
        return div(*this, b);
    }
    bigint operator%(const bigint& b) const {
        assert(!b.is_zero());
        return mod(*this, b);
    }
    bigint operator-() const { return bigint(*this).set_negative(!is_negative); }
    bigint operator>>(const size_t n_bits) const { return bigint(*this) >>= n_bits; }
    bigint operator<<(const size_t n_bits) const { return bigint(*this) <<= n_bits; }
    friend istream& operator>>(istream& stream, bigint& v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
    friend ostream& operator<<(ostream& stream, const bigint& v) {
        cout << v.to_string();
        return stream;
    }
    bool operator!() const noexcept { return is_zero(); }
    explicit operator bool() const noexcept {
        return !is_zero();
    }
    template<class type>
    void operator*=(type number) {
        static_assert(is_same_v<type, int8_t> || is_same_v<type, int16_t> || is_same_v<type, int32_t> || is_same_v<type, int64_t>, "type must be int8, int16, int32, or int64");
        if (number < 0) {
            is_negative = !is_negative;
            word val = -static_cast<word>(number);
            mul_word(val);
        }
        else mul_word(static_cast<word>(number));
    }
};

Test template

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string random_int(int n) {
    string s;
    for (int i = 0; i < n; i++) { //random số gồm n chữ số ngẫu nhiên
        s += uniform_int_distribution<int>('0', '9')(rng);
    }
    if (uniform_int_distribution<int>(0, 1)(rng) == 1 && s != "0") { //random số dương, số âm
        s.insert(0, 1, '-');
    }
    return s;
}

void test() {

    const int TEST_CASES = 100000;

    // kiểm tra cộng (1 -> 18 chữ số)
    cout << "Testing addition... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a + b;

        ll result = stoll(first) + stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " + " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra trừ (1 -> 18 chữ số)
    cout << "Testing subtraction... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a - b;

        ll result = stoll(first) - stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " - " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra nhân (1 -> 9 chữ số)
    cout << "Testing multiplication... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 9)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a * b;

        ll result = stoll(first) * stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " * " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra chia (1 -> 18 chữ số)
    cout << "Testing division... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        if (b == 0) continue;
        bigint ans = a / b;

        ll result = stoll(first) / stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " / " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra chia lấy dư (1 -> 18 chữ số)
    cout << "Testing modulo... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        if (b == 0) continue;
        bigint ans = a % b;

        ll result = stoll(first) % stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " % " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử Bitwise AND (1 -> 18 chữ số)
    cout << "Testing AND operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a & b;

        ll result = stoll(first) & stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " & " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử Bitwise OR (1 -> 18 chữ số)
    cout << "Testing OR operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a | b;

        ll result = stoll(first) | stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " | " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử Bitwise XOR (1 -> 18 chữ số)
    cout << "Testing XOR operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string second = random_int(n);

        bigint a(first), b(second);
        bigint ans = a ^ b;

        ll result = stoll(first) ^ stoll(second);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " ^ " << b << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử Bitwise NOT (1 -> 18 chữ số)
    cout << "Testing NOT operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);

        bigint a(first);
        bigint ans = ~a;

        ll result = ~stoll(first);
        if (ans != result) {
            cout << "failed. (~" << a << " = " << ans << "), expected: " << result;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử BITSHIFT LEFT (1 -> 9 chữ số)
    cout << "Testing LEFT SHIFT operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 9)(rng);
        string first = random_int(n);

        int shift_val = uniform_int_distribution<int>(0, 30)(rng);

        bigint a(first), b_shift(shift_val);
        bigint ans = a << b_shift;

        ll result = stoll(first) << shift_val;
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " << " << shift_val << " = " << ans << "), expected: " << result << nl;
            exit(0);
        }
    }
    cout << "passed!" << nl;

    // kiểm tra toán tử BITSHIFT RIGHT (1 -> 18 chữ số)
    cout << "Testing RIGHT SHIFT operation... ";
    for (int i = 1; i < TEST_CASES + 1; i++) {
        int n = uniform_int_distribution<int>(1, 18)(rng);
        string first = random_int(n);
        string shift_val = random_int(n);


        bigint a(first), b_shift(shift_val);
        if (b_shift < 0) continue;
        bigint ans = a >> b_shift;

        ll result = stoll(first) >> stoll(shift_val);
        if (ans != result) {
            cout << "failed at case #" << i << ". (" << a << " >> " << shift_val << " = " << ans << "), expected: " << result << nl;
            exit(0);
        }
    }
    cout << "passed!" << nl;
}

Quan trọng

Dù sao đi nữa thì template của mình vẫn chưa thực sự hoàn hảo nên các bạn có thể cải tiến, tối ưu hoặc thêm gì đó, cheers:3