C++实现大整数GCD时触发vector下标越界错误求助

我需要用vector实现超大整数的最大公约数（GCD）计算，当前代码对部分数对能正常运行，但输入24和18、52和18这类数对时，会出现vector subscript out of range错误。尝试打印中间结果但未能定位问题，代码如下：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int num_cmp(const vector<int>& num1, const vector<int>& num2)
{

    /* function comparing two numbers whose digits are stored in vectors
    return -1 if smaller, 1 if larger, and 0 if equal */

    // compare number of digits first
    int len1 = num1.size(), len2 = num2.size();
    int msb = 0;
    while (num1[msb] == 0) {  // skip zeros
        --len1;
        ++msb;
    }
    msb = 0;
    while (num2[msb] == 0) {  // skip zeros
        --len2;
        ++msb;
    }
    if (len1 > len2)
        return 1;
    else if (len1 < len2)
        return -1;
    else {
        // if same length, compare digit by digit
        for (int i = 0; i < len1; ++i) {
            if (num1[i] > num2[i])
                return 1;
            else if (num1[i] < num2[i])
                return -1;
        }
    }
    return 0;
}

void vec_intfromchar(vector<int>& a, const vector<char>& num)
{
    /* convert char vector to int vector
     two vectors are assumed to have same size  */
    for (int i = 0; i < a.size(); ++i)
        a[i] = num[i] - '0';
    return;
}

void print_vec(vector<int>& a)
{
    int start = 0;
    while (start < a.size() && a[start++] == 0); // skip zeros
    for (int i = start - 1; i < a.size(); ++i)
        cout << a[i];
    cout << "\n";

    return;
}

bool is_even(vector<int>& a)
{
    return a[a.size() - 1] % 2 == 0;
}

bool is_zero(vector<int>& a)
{
    for (int i = 0; i < a.size(); ++i)
        if (a[i] != 0)
            return false;
    return true;
}

void substract(vector<int>& b, vector<int>& a)
{
    // b = b - a
    while (a.size() < b.size())
        a.insert(a.begin(), 0); // sign extension
    while (a.size() > b.size())
        b.insert(b.begin(), 0); // sign extension
    print_vec(a);
    print_vec(b);

    for (int i = b.size() - 1; i >= 0; --i) {
        if (b[i] < a[i]) {
            b[i] = b[i] - a[i] + 10;
            --b[i - 1];  // borrow
        }
        else
            b[i] -= a[i];
    }
    return;
}

void divide_by2(vector<int>& a)
{
    int dividend = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        dividend = dividend * 10 + a[i];
        a[i] = dividend / 2;
        dividend %= 2;
    }
    return;
}

void multiply_by2(vector<int>& a)
{
    int mult = 0, carry = 0;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        mult = a[i] * 2 + carry;
        carry = mult / 10;
        a[i] = mult % 10;
    }
    return;
}

void addition(vector<int>& a, vector<int>& b)
{
    // a = a + b

    while (a.size() < b.size())
        a.insert(a.begin(), 0); // sign extension
    while (b.size() < a.size())
        b.insert(b.begin(), 0); // sign extension

    int add = 0, carry = 0;
    for (int i = a.size() - 1; i >= 0; --i) {
        add = a[i] + b[i] + carry;
        carry = add / 10;
        a[i] = add % 10;
    }
    return;
}

vector<int> multiply(vector<int>& a, vector<int>& b) {

    vector<int> acc(a.size() + b.size(), 0); // the final result

    for (int i = b.size() - 1; i >= 0; --i) {
        int mult = 0, carry = 0;
        vector<int> result(a.size() + 1, 0);   // middle result

        for (int j = a.size() - 1; j >= 0; --j) {
            mult = a[j] * b[i] + carry;
            carry = mult / 10;
            // cout << "mult: " << mult << "\n";
            // cout << "carry: " << carry << "\n";
            result[j + 1] = mult % 10;
            if (j == 0)
                result[0] = carry;
        }


        // append zeros to the oprand
        for (int k = i + 1; k < b.size(); ++k)
            result.insert(result.end(), 0);
        
        // acumulation
        addition(acc, result);
        
    }
    return acc;
}



int main() {
    string str1, str2;
    cin >> str1 >> str2;
    vector<char> num1(str1.begin(), str1.end());
    vector<char> num2(str2.begin(), str2.end());

    // initial values for a, b, and ans
    vector<int> ans(1, 1);
    vector<int> a(num1.size());
    vector<int> b(num2.size());
    vec_intfromchar(a, num1);
    vec_intfromchar(b, num2);

    if (num_cmp(a, b) != -1)
        a.swap(b);  // set a to be the smaller one

    // Binary Algorithm for gcd
    while (!is_zero(a) && !is_zero(b)) {
        if (is_even(a) && is_even(b)) {
            multiply_by2(ans);
            divide_by2(a);
            divide_by2(b);
        }
        else if (is_even(a)) {
            divide_by2(a);
        }
        else if (is_even(b)) {
            divide_by2(b);
        }

        if (num_cmp(a, b) == 1)  // a > b
            a.swap(b);
        substract(b, a);    // b = b - a
    }
    vector<int> gcd = multiply(a, ans);
    print_vec(gcd);

    return 0;
}

问题分析与修复 #

1. num_cmp函数的越界问题 #

当传入的vector全为0时，while (num1[msb] == 0)会持续递增msb，直到超出vector的下标范围（msb >= num1.size()），此时访问num1[msb]会触发下标越界。

修复方案：在循环中增加msb < num1.size()的判断，同时优化全零数的比较逻辑：

int num_cmp(const vector<int>& num1, const vector<int>& num2)
{
    int len1 = num1.size(), len2 = num2.size();
    int msb = 0;
    // 跳过前导零，同时避免越界
    while (msb < num1.size() && num1[msb] == 0) {
        --len1;
        ++msb;
    }
    msb = 0;
    while (msb < num2.size() && num2[msb] == 0) {
        --len2;
        ++msb;
    }
    if (len1 > len2)
        return 1;
    else if (len1 < len2)
        return -1;
    else {
        // 找到第一个非零位开始逐位比较
        int start1 = 0, start2 = 0;
        while (start1 < num1.size() && num1[start1] == 0) start1++;
        while (start2 < num2.size() && num2[start2] == 0) start2++;
        // 全零则相等
        if (start1 == num1.size() && start2 == num2.size()) return 0;
        for (; start1 < num1.size() && start2 < num2.size(); ++start1, ++start2) {
            if (num1[start1] > num2[start2])
                return 1;
            else if (num1[start1] < num2[start2])
                return -1;
        }
    }
    return 0;
}

2. substract函数的借位越界问题 #

当i=0（最高位）时，执行--b[i-1]会访问b[-1]，这是非法内存访问，直接触发下标越界。此外，函数没有处理减完后的前导零，可能导致后续逻辑出错。

修复方案：确保调用substract时b >= a，同时在借位时判断i != 0，最后移除前导零：

void substract(vector<int>& b, vector<int>& a)
{
    // 统一长度
    while (a.size() < b.size())
        a.insert(a.begin(), 0);
    while (b.size() < a.size())
        b.insert(b.begin(), 0);

    for (int i = b.size() - 1; i >= 0; --i) {
        if (b[i] < a[i]) {
            // 最高位不会需要借位，因为b >= a
            if (i == 0) {
                cerr << "错误：substract函数中b < a" << endl;
                return;
            }
            b[i] += 10;
            --b[i - 1];
        }
        b[i] -= a[i];
    }

    // 移除前导零，避免后续操作异常
    while (!b.empty() && b[0] == 0) {
        b.erase(b.begin());
    }
    if (b.empty()) {
        b.push_back(0);
    }
    // 同步清理a的前导零
    while (!a.empty() && a[0] == 0) {
        a.erase(a.begin());
    }
    if (a.empty()) {
        a.push_back(0);
    }
}

3. 主循环的逻辑漏洞 #

当a == b时，num_cmp(a,b)返回0，不会执行交换，此时b - a = 0，后续循环中is_zero(a)为假但is_zero(b)为真，可能触发异常。此外，每次执行substract前需确保b >= a。

修复方案：在主循环中增加a == b的判断，直接退出循环：

// Binary Algorithm for gcd
while (!is_zero(a) && !is_zero(b)) {
    if (is_even(a) && is_even(b)) {
        multiply_by2(ans);
        divide_by2(a);
        divide_by2(b);
    }
    else if (is_even(a)) {
        divide_by2(a);
    }
    else if (is_even(b)) {
        divide_by2(b);
    }

    int cmp = num_cmp(a, b);
    if (cmp == 1)  // a > b，交换后保证b >= a
        a.swap(b);
    else if (cmp == 0) {
        // a == b，GCD即为当前值，退出循环
        break;
    }
    substract(b, a);    // b = b - a
}

4. 其他优化 #

• 将is_zero函数改为const引用，避免不必要的拷贝：

bool is_zero(const vector<int>& a)
{
    for (int digit : a) {
        if (digit != 0)
            return false;
    }
    return true;
}

• 移除substract函数中的调试打印print_vec(a)和print_vec(b)，避免干扰输出。

修复后代码验证 #

输入24和18，输出应为6；输入52和18，输出应为2，均可正常运行且无越界错误。

内容的提问来源于stack exchange，提问作者Beth