这些是 C++ 吗？为添加 2 个正大整数而优化的代码？

Question

我编写了一个程序来使用向量存储数字来计算（相加）2 个正大整数。

#include <cstdlib>
#include <cstdio> // sd sprintf()
#include <iostream>
#include <vector>// sd vector

typedef short TYPE;// alias

void input();
void makeArray();
void display(const std::vector<TYPE> Ar);
TYPE convertChar2T( char * ch);
void add();


static std::string num1;//store big integer as string
static std::string num2;

static std::vector<TYPE> Arr1;//store as vector 
static std::vector<TYPE> Arr2;

static std::vector<TYPE> result;

int main(int argc, char** argv) {
    input();
    makeArray();
    display(Arr1);
    display(Arr2);
    add();
    display(result);
    return 0;
}

//input 2 big integer number
void input(){
    std::cout << "Enter 1st number : " ;
    if (! std::getline(std::cin , num1) )
        std::cerr << "Not OK\n";
    std::cout << "Enter 2nd number : ";
    if (! std::getline(std::cin , num2) )
        std::cerr << "Not OK\n";
}

//grab into 2 arrays
void makeArray(){
    for (std::size_t i = 0; i < num1.size(); i++){
        char temp1[2] = { num1[i], '\0'};   //use array-of-char as it need '\0'
        Arr1.push_back( convertChar2T(temp1)  ); //push what is converted
    }
    for (std::size_t i = 0; i < num2.size(); i++){
        char temp2[2] = { num2[i], '\0'};
        Arr2.push_back( convertChar2T(temp2) );
    }
}

//convert char -> TYPE by using sscanf()
TYPE convertChar2T( char * ch){
    TYPE numb ;
    sscanf( ch, "%d", &numb );//NGUOC LAI SPRINTF
    return numb;
}

//display array
void display(const std::vector<TYPE> Ar){
    for (std::size_t i = 0; i < Ar.size(); i++)
        std::cout << Ar.at(i) << '\t';
    std::cout << '\n';
}

void add(){
    std::size_t i = Arr1.size(); // NEVER COMES TO ZERO ( 1 AT LEAST )
    std::size_t j = Arr2.size();

    //check original one and later one
    //3 cases : 1 - original one , not yet processed
    //          2 - original # one, not yet processed
    //          -1 - original # one or one, processed
    //NOTE: at first only value 1 or 2 ( not process )
    short check_one[2] = {
        ( i == 1 ) ? 1 : 2,
        ( j == 1 ) ? 1 : 2,
    };

    bool boost = 0;
    bool Arr1_isgood = true;// whether count to 1 or not
    bool Arr2_isgood = true;// good -> not yet 1

    short temp_result = 0;//temporary result to push into vector

    while ( Arr1_isgood || Arr2_isgood ){// while not all comes to 1


        // i == j : 2 cases
        //              1st: both 1 now - 3 cases
        //                  1.1 #1+not process original and processed
        //                  1.2 processed and #1+not processed
        //                  1.3 both 1 original + not processed
        //              2nd: both # 1
        if ( i == j ) {
            if (  check_one[0] == 2 && check_one[1] == -1 ){//#1+not process original and processed
                temp_result =  Arr1[i-1] + boost;
                check_one[0] == -1;
            }
            else if (  check_one[0] == -1 && check_one[1] == 2  ){//processed and #1+not processed
                temp_result = Arr2[j-1] + boost;
                check_one[1] = -1;
            }
            else//both 1 original + not processed OR both # 1
                temp_result = Arr1[i-1] + Arr2[j-1] + boost;

            //check result >= 10 or < 10
            if ( temp_result >= 10 ){
                temp_result = temp_result - 10 ;
                boost = 1;
            }
            else
                boost = 0;

            //result.begin() return iterator at beginning
            result.insert( result.begin() ,temp_result );

            //update info
            if ( i == j && i == 1){ // NOTE : NEU SD i==j==1 -> sai (vi luon true)
                Arr1_isgood = Arr2_isgood = false;
                continue;
            }
            else if ( i == j && i != 1){ // i == j # 1
                i--;
                j--;
            }
        }
        if (i != j){
            //check to set flag ( if one of two die )
            if ( i == 1 && j > 1 )
                Arr1_isgood = false;
            else if ( i > 1 && j == 1  )
                Arr2_isgood = false;

            // i die && j live OR vice versa
            if ( (!Arr1_isgood && Arr2_isgood) ||
                    (Arr1_isgood && !Arr2_isgood ) ){

                if (!Arr1_isgood && Arr2_isgood ){          //1st case
                    if ( check_one[0] == 1 || check_one[0] == 2){//not yet processed as  SET FLAG ABOVE first
                        temp_result = Arr1[i-1] + Arr2[j-1] + boost;
                        check_one[0] = -1 ;
                    }
                    else
                        temp_result = Arr2[j-1] + boost;
                    j--;
                }
                else if ( Arr1_isgood && !Arr2_isgood ){    //2nd case
                    if ( check_one[1] == 1 || check_one[1] == 2 ){//not yet processed as  SET FLAG ABOVE first
                        temp_result = Arr1[i-1] + Arr2[j-1] + boost;
                        check_one[1] = -1 ;
                    }
                    else
                        temp_result = Arr1[i-1] + boost;
                    i--;
                }
            }
            else {// both is good
                temp_result = Arr1[i-1] + Arr2[j-1] + boost;
                i--;
                j--;
            }

            //check result >= 10 or < 10
            if (temp_result >= 10) {
                temp_result -= 10;
                boost = 1;
            } else
                boost = 0;

            result.insert( result.begin() ,temp_result );
        }
    }

    //insert boost (if any exists)
    if (boost == 1)
        result.insert( result.begin(), boost);
}

我在使用“Arr1_isgood”布尔变量和 check_one 变量之间左右为难，似乎它们可以组合成一个变量？我尝试这样做，花了很多时间却没有得到正确的结果。 该数字可以存储在某种较小的数据结构而不是“短”类型中吗？因为“短”占用的比特数超过了所需的比特数。
另一件事是：似乎 std::size_t 的大小最多只能达到 40 亿，因为当 size_t 达到 1 时，我将其减少了几次，它达到了 40 亿？不是吗？ 我想知道这些代码是否可以进一步优化？

Answer 1

如果你想操作大整数，你应该使用 big-integer 库，例如GMP。

Answer 2

在您的机器中有 32 位整数，假设您将每个数字（无符号）表示为 31 位有符号整数数组，从最低有效位开始。
然后也许你可以做这样的事情：

// do c = a + b
int a[n], b[n], c[n];
int carry = 0;
for (i = 0; i < n; i++){
  // do the addition with carry
  c[i] = a[i] + b[i] + carry;
  // if the addition carried into the sign bit
  carry = (c[i] < 0);
  // detect it and remove it from the sum
  if (carry){
    c[i] &= 0x7fffffff;
  }
}

然后你可以弄清楚如何处理底片。