[CPP] Xử lý số lớn trong lập trình

Trong lập trình, có nhiều bài toán yêu cầu xử lý các số nguyên rất lớn, vượt quá giới hạn của các kiểu dữ liệu thông thường như int, long hay thậm chí là long long trong C++.

Ví dụ: tính giai thừa của một số lớn như 100!, hoặc cộng/trừ/nhân các số có hàng trăm chữ số. Khi đó, ta cần triển khai các thuật toán xử lý số lớn (Big Integer) để thao tác trực tiếp trên từng chữ số của số đó dưới dạng chuỗi hoặc mảng.

Kỹ thuật xử lý số lớn là một kỹ năng quan trọng trong các bài toán thuật toán và thi lập trình, đặc biệt là khi làm việc với các số nguyên có hàng chục hoặc hàng trăm chữ số. Trong C++. Ngoài cách tự cài đặt như ví dụ dưới đây, ta cũng có thể sử dụng thư viện hỗ trợ như GMP, hoặc chuyển sang dùng ngôn ngữ hỗ trợ sẵn như Python.

Ý tưởng:

• Lưu trữ: Dùng string để lưu số nguyên lớn, mỗi ký tự là một chữ số, đảm bảo không bị tràn kiểu dữ liệu.
• Nguyên tắc tính toán: Mô phỏng phép toán tiểu học (cộng, trừ, nhân…) bằng cách xử lý từng chữ số và số nhớ.
• Phép cộng minh họa:
  • Viết hai số thẳng hàng theo cột, từ hàng đơn vị sang trái.
  • Cộng từng cặp chữ số cùng cột, cộng thêm số nhớ.
  • Ghi kết quả vào chuỗi mới, xử lý số nhớ cuối nếu còn.
• Ví dụ:

     7654
+  123456
---------
   131110

• Thực hiện theo thứ tự từ phải sang trái: 4+6=10 (viết 0 nhớ 1), 5+5+1(nhớ)=11 (viết 1 nhớ 1), 6+4+1(nhớ)=11 (viết 1 nhớ 1), 7+3+1(nhớ)=11 (viết 1 nhớ 1), 0+2+1(nhớ)=3, 0+1(nhớ)=1.

Cài đặt tham khảo

Cộng hai số nguyên lớn bằng C++ (ver1)

#include <iostream>
#include <string>
using namespace std;

string addBigNumbers(string a, string b) {
    string result = "";
    int carry = 0;

    int i = a.length() - 1;
    int j = b.length() - 1;

    // Duyệt từ cuối chuỗi về đầu
    while (i >= 0 || j >= 0 || carry) {
        int digitA = (i >= 0) ? (a[i] - '0') : 0;
        int digitB = (j >= 0) ? (b[j] - '0') : 0;
        int sum = digitA + digitB + carry;
        result.insert(result.begin(), (sum % 10) + '0'); // chèn vào đầu chuỗi kết quả
        carry = sum / 10;
        i--;
        j--;
    }
    return result;
}

int main() {
    string num1 = "9876543210123456789";
    string num2 = "1234567890987654321";
    cout << "Tổng hai số là: " << addBigNumbers(num1, num2) << endl;
    return 0;
}

Cộng hai số nguyên lớn bằng C++ (ver2)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// Hàm cộng hai số lớn dưới dạng chuỗi
string addBigNumbers(string a, string b) {
    // Đảm bảo chuỗi a dài hơn hoặc bằng b
    if (a.length() < b.length()) swap(a, b);

    // Đảo ngược chuỗi để cộng từ phải sang trái
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string result = "";
    int carry = 0;
    for (size_t i = 0; i < a.length(); i++) {
        int digitA = a[i] - '0';
        int digitB = i < b.length() ? b[i] - '0' : 0;
        int sum = digitA + digitB + carry;
        result += (sum % 10) + '0';
        carry = sum / 10;
    }

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

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

int main() {
    string num1 = "9876543210123456789";
    string num2 = "1234567890987654321";
    cout << "Tổng hai số là: " << addBigNumbers(num1, num2) << endl;
    return 0;
}

Cộng hai số nguyên lớn bằng C++ (ver3)

Ta sẽ nghiên cứu thêm một cách xử lý số lớn khác bằng cách sử dụng vector<int> để lưu trữ từng chữ số theo thứ tự ngược, tức là chữ số hàng đơn vị nằm ở đầu vector. Cách làm này rất thuận tiện khi thực hiện các phép toán như cộng, nhân do dễ thao tác từ chữ số thấp lên cao và trong trường hợp cần mở rộng chữ số (?).

Ý tưởng:

• Lưu trữ (vector đảo ngược):
  • Mỗi chữ số lưu trong một phần tử của vector<int>, thứ tự ngược (hàng đơn vị ở chỉ số 0).
  • Giúp việc cộng/trừ dễ dàng hơn vì có thể duyệt từ chỉ số 0 lên.
  • Nếu có phát sinh thêm chữ số mới thì chỉ cần thêm phần tử vào cuối vector là được.
• Ví dụ cộng:
  • Số A = 123456 → {6,5,4,3,2,1}
  • Số B = 7654 → {4,5,6,7}
  • Cộng từng phần tử: {0,1,1,1,3,1} → đảo ngược lại thành 131110.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// Chuyển chuỗi số sang vector<int> lưu theo thứ tự ngược
vector<int> stringToVector(const string& s) {
    vector<int> v;
    for (int i = s.length() - 1; i >= 0; --i) {
        v.push_back(s[i] - '0');
    }
    return v;
}

// Chuyển vector<int> về chuỗi số
string vectorToString(const vector<int>& v) {
    string result;
    bool leadingZero = true;
    for (int i = v.size() - 1; i >= 0; --i) {
        if (leadingZero && v[i] == 0) continue;
        leadingZero = false;
        result += (v[i] + '0');
    }
    return result.empty() ? "0" : result;
}

// Cộng hai số lớn lưu trong vector
vector<int> addBigNumbers(const vector<int>& a, const vector<int>& b) {
    vector<int> result;
    int carry = 0;
    size_t n = max(a.size(), b.size());
    for (size_t i = 0; i < n; ++i) {
        int digitA = (i < a.size()) ? a[i] : 0;
        int digitB = (i < b.size()) ? b[i] : 0;
        int sum = digitA + digitB + carry;
        result.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry) result.push_back(carry);
    return result;
}

int main() {
    string s1 = "9876543210123456789";
    string s2 = "1234567890987654321";

    vector<int> num1 = stringToVector(s1);
    vector<int> num2 = stringToVector(s2);

    vector<int> result = addBigNumbers(num1, num2);

    cout << "Tổng hai số là: " << vectorToString(result) << endl;
    return 0;
}

Để thống nhất và thuận tiện trong việc xử lý, Trong các phép toán tiếp theo chúng ta sẽ xử lý dựa trên cấu trúc vector<int>

Các hàm bổ trợ

Để việc xử lý được thuận tiện, ta cần thiết kế một số hàm bổ trợ phục vụ việc chuyển đổi, so sánh các số lớn, dưới đây là một số hàm được thiết kế sẵn để bạn có thể tham khảo thêm và sử dụng tùy theo cấu trúc bài toán yêu cầu:

// Xóa các số 0 vô nghĩa ở đầu (trong lưu ngược là ở cuối vector)
void trim(vector<int> &a) {
    while (a.size() > 1 && a.back() == 0) a.pop_back();
}

// Chuyển từ chuỗi thập phân ("0".."9") sang vector<int> lưu ngược
vector<int> fromString(const string &s) {
    if (s.empty()) return {0};
    vector<int> a; a.reserve(s.size());
    size_t i = 0; if (s[0] == '+') i = 1;
    for (size_t k = s.size(); k-- > i; ) {
        if (!isdigit((unsigned char)s[k])) throw invalid_argument("Non-digit");
        a.push_back(s[k] - '0');
    }
    trim(a);
    return a;
}

// Chuyển từ số nguyên không âm (64-bit) sang vector<int> lưu ngược
vector<int> fromULL(unsigned long long x) {
    if (x == 0) return {0};
    vector<int> a;
    while (x) { a.push_back(int(x % 10)); x /= 10; }
    return a;
}

// So sánh hai số lớn: trả về -1 nếu A < B, 0 nếu A==B, 1 nếu A > B
int cmp(const vector<int> &A, const vector<int> &B) {
    if (A.size() != B.size()) return (A.size() < B.size()) ? -1 : 1;
    for (int i = (int)A.size() - 1; i >= 0; --i) {
        if (A[i] != B[i]) return (A[i] < B[i]) ? -1 : 1;
    }
    return 0;
}

// Chuyển vector<int> lưu ngược về chuỗi thập phân
string toString(const vector<int> &a) {
    string s; s.reserve(a.size());
    for (int i = (int)a.size() - 1; i >= 0; --i) s.push_back(char('0' + a[i]));
    return s;
}

// In số lớn trực tiếp
void printBig(const vector<int> &a) {
    for (int i = (int)a.size() - 1; i >= 0; --i) cout << a[i];
    cout<<endl;
}

Phép trừ hai số lớn

Ta xét ví dụ phép trừ với a > b, trường hợp ngược lại có thể xử lý thêm dấu âm bằng nhiều cách (- xin dành cho bạn đọc làm thử thách ^.~ )

// Trừ trị tuyệt đối: giả định |a| >= |b|
vector<int> subtractAbs(const vector<int> &a, const vector<int> &b) {
    vector<int> result;
    result.reserve(a.size());
    int borrow = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        int digitA = a[i];
        int digitB = (i < b.size()) ? b[i] : 0;
        int sub = digitA - digitB - borrow;
        if (sub < 0) {
            sub += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result.push_back(sub);
    }
    trim(result); // Loại bỏ chữ số 0 vô nghĩa
    return result;
}

// Trừ hai số lớn A - B (có xét dấu)
vector<int> subtractBigNumbers(const vector<int> &a, const vector<int> &b, int &sign) {
    int c = cmp(a, b);
    if (c == 0) {
        sign = 1;
        return {0};
    } else if (c > 0) {
        sign = 1;
        return subtractAbs(a, b);
    } else {
        sign = -1;
        return subtractAbs(b, a);
    }
}

Phép nhân hai số lớn

// Nhân trị tuyệt đối hai số lớn
vector<int> multiplyAbs(const vector<int> &a, const vector<int> &b) {
    vector<int> result(a.size() + b.size(), 0);
    for (size_t i = 0; i < a.size(); ++i) {
        int carry = 0;
        for (size_t j = 0; j < b.size(); ++j) {
            long long mul = 1LL * a[i] * b[j] + result[i + j] + carry;
            result[i + j] = int(mul % 10);
            carry = int(mul / 10);
        }
        if (carry) result[i + b.size()] += carry;
    }
    trim(result);
    return result;
}

// Nhân hai số lớn có xét dấu (signA, signB là ±1)
vector<int> multiplyBigNumbers(const vector<int> &a, const vector<int> &b, int signA, int signB, int &signOut) {
    if (a.size() == 1 && a[0] == 0) { signOut = 1; return {0}; }
    if (b.size() == 1 && b[0] == 0) { signOut = 1; return {0}; }
    signOut = (signA == signB) ? 1 : -1;
    return multiplyAbs(a, b);
}

Tính lũy thừa (BigPow)

Hướng dẫn cách thiết kế hàm BigPow() cho số lớn dựa trên code nhân 2 số lớn đã có.

Luôn nhớ:

Số lớn lưu trong vector<int> cơ số 10, thứ tự chữ số ngược (chữ số cuối cùng lưu ở v[0]).

Bổ sung thêm hàm hỗ trợ (so sánh, chuẩn hóa, chia 2, kiểm tra chẵn/lẻ), phép nhân hai số lớn, và 3 hàm pow:

• BigPow(int base, int exp) -> vector<int>
• BigPow(vector<int> base, int exp) -> vector<int>
• BigPow(vector<int> base, vector<int> exp) -> vector<int>

Dùng kỹ thuật Lũy thừa nhị phân (binary exponentiation).

inline vector<int> one() { return {1}; }
inline vector<int> zero() { return {0}; }
inline bool isZero(const vector<int> &x) { return x.size() == 1 && x[0] == 0; }
inline bool isOdd(const vector<int> &x) { return !x.empty() && (x[0] & 1); }

void div2(vector<int> &exp) {
    int carry = 0;
    for (int i = (int)exp.size() - 1; i >= 0; --i) {
        int cur = carry * 10 + exp[i];
        exp[i] = cur / 2;
        carry = cur % 2;
    }
    trim(exp);
}

vector<int> BigPow(int base, int exp) {
    if (exp < 0) throw invalid_argument("Negative exponent not supported");
    if (base == 0) return (exp == 0) ? one() : zero();
    int signBase = (base < 0) ? -1 : 1;
    vector<int> b = fromULL((unsigned long long) llabs((long long)base));
    vector<int> res = one();
    while (exp > 0) {
        if (exp & 1) res = multiplyAbs(res, b);
        if (exp > 1) b = multiplyAbs(b, b);
        exp >>= 1;
    }
    if (signBase < 0 && (exp & 1)) {
        // xử lý dấu nếu cần
    }
    return res;
}

vector<int> BigPow(vector<int> base, int exp) {
    if (exp < 0) throw invalid_argument("Negative exponent not supported");
    if (isZero(base)) return (exp == 0) ? one() : zero();
    vector<int> res = one();
    while (exp > 0) {
        if (exp & 1) res = multiplyAbs(res, base);
        if (exp > 1) base = multiplyAbs(base, base);
        exp >>= 1;
    }
    return res;
}

vector<int> BigPow(vector<int> base, vector<int> exp) {
    if (isZero(exp)) return one();
    if (isZero(base)) return zero();
    vector<int> res = one();
    while (!isZero(exp)) {
        if (isOdd(exp)) res = multiplyAbs(res, base);
        div2(exp);
        if (!isZero(exp)) base = multiplyAbs(base, base);
    }
    return res;
}

Ghi chú nhanh

• Các hàm xử lý đều dựa trên vector<int> lưu ngược.
• multiplyAbs nhân theo cách nhân dọc tiểu học, cộng dồn vào đúng vị trí và xử lý số nhớ.
• multiplyBigNumbers xét dấu kết quả dựa trên dấu của hai toán hạng.
• trim loại bỏ các chữ số 0 vô nghĩa ở cuối vector (do lưu ngược).
• Phần lũy thừa dùng Binary exponentiation (bình phương-nhân) với ba phiên bản BigPow .
• Với số mũ là số lớn, dùng chia 2 trên số lưu ngược (div2).

Phần kết

Việc xử lý số nguyên lớn là một kỹ năng cần biết trong lập trình (khi sử dụng các ngôn ngữ chưa hỗ trợ xử lý số lớn), đặc biệt khi giải quyết các bài toán liên quan đến mật mã, tính toán khoa học, hay các thuật toán yêu cầu độ chính xác cao. Bằng cách mô phỏng các phép toán cơ sở trên cấu trúc dữ liệu như string hoặc vector<int> lưu ngược, lập trình viên có thể xây dựng các phép cộng, trừ, nhân, chia, lũy thừa cho số lớn một cách linh hoạt.

Trong tương lai, bạn có thể nghiên cứu thêm:

• Tối ưu thuật toán nhân (Karatsuba, Toom-Cook, FFT) để xử lý số có hàng triệu chữ số.
• Xây dựng lớp (class) BigInteger hỗ trợ đầy đủ các toán tử và tương tác trực tiếp như kiểu dữ liệu chuẩn.
• Mở rộng sang số nguyên lớn có dấu hoặc số thực lớn (BigDecimal).
• Ứng dụng trong mật mã học (RSA, ECC) hoặc tính toán song song để tăng tốc xử lý.

Những kỹ năng này không chỉ giúp giải quyết bài toán cụ thể mà còn là nền tảng vững chắc để nghiên cứu và phát triển trong lĩnh vực khoa học máy tính và an toàn thông tin.