阿里面试 大整数加法的实现

5
同符号加法溢出 3. 考虑负数的存在。

关键是想好怎么设计一个出Bigint结构体。

enum Status{invalid = 0, valid};

struct Bign {
    int arr[128];
    int len;
    int minus;
    Status g_status;
    Bign() {
        memset(arr, 0, sizeof(arr));
        len = 1;
        minus = 1;
        g_status = invalid;
    }
};

具体实现：

#include <vector>
#include <string>
#include <assert.h>

using namespace std;

enum Status{invalid = 0, valid};

struct Bign {
    int arr[128];
    int len;
    int minus;
    Status g_status;
    Bign() {
        memset(arr, 0, sizeof(arr));
        len = 1;
        minus = 1;
        g_status = invalid;
    }
};

Bign initFromStr(string str) {
    Bign a;
    if((int)str.size() == 0)
        return a;
    
    // size >= 1
    if(str[0] == '-') {
        a.minus = -1;
        str.erase(str.begin());
    }
    else if(str[0] == '+')
        str.erase(str.begin());
    
    // delete prefix zeroes
    while(str.size() > 1 && str[0] == '0')
        str.erase(str.begin());
    
    if(str.size() > 128)
        return a;
    
    if(str.size() == 1 && str[0] == '0') {
        a.len = 1;
        a.g_status = valid;
        return a;
    }
    
    for(int i = 0; i < str.size(); i++) {
        if(str[i] < '0' || str[i] > '9') {
            return a;
        }
        a.arr[i] = str[str.size() - i - 1] - '0';
    }
    
    a.len = (int)str.size();
    a.g_status = valid;
    
    return a;
}

Bign plus(Bign a, Bign b) {
    Bign c;
    if(a.g_status == invalid || b.g_status == invalid)
        return c;
    
    if(a.minus + b.minus != 0) { // 符号相同
        c.minus = a.minus;
        
        // be careful for the overflow
        int cax = 0;
        for(int i = 0; i < 128; i++) {
            int sum = a.arr[i] + b.arr[i] + cax;
            cax = sum / 10;
            c.arr[i] = sum % 10;
            
            if(i == 127 && cax != 0) {
                c.g_status = invalid;
                return c;
            }
        }
        
        int i = 127;
        while(i >= 1 && c.arr[i] == 0 ) {
            i--;
        }
        c.len = i + 1;
        
        c.g_status = valid;
        
        return c;
    }
    else { // 符号不同
        if(a.len < b. len || ((a.len == b.len) && (a.arr[a.len - 1] < b.arr[b.len - 1])))
            return plus(b,a);
        
        c.minus = a.minus;
        
        int borrow = 0;
        for(int i = 0; i < 128; i++) {
            if(borrow == 1) {
                a.arr[i]--;
                borrow = 0;
            }
            
            if(a.arr[i] < b.arr[i]) {
                borrow = 1;
                a.arr[i] += 10;
            }
            
            c.arr[i] = a.arr[i] - b.arr[i];
        }
        
        int i = 127;
        while(i >= 1 && c.arr[i] == 0 ) {
            i--;
        }
        c.len = i + 1;
        
        c.g_status = valid;
        
        return c;
    }
}

void printBign(Bign num) {
    if(num.g_status == invalid) {
        printf("invalid Bign, can not print!\n");
        return;
    }
    
    printf("Bign = ");
    
    if(num.len == 1 && num.arr[0] == 0) {
        printf("0\n");
        return;
    }
    
    
    if(num.minus == -1)
        printf("-");
    
    for(int i = num.len - 1; i >= 0; i--)
        printf("%d", num.arr[i]);
    
    printf("\n");
}


int main(int argc, char *argv[])
{
    Bign n1;
    Bign n2;
    
    string str1 = "-1234560000000000";
    n1 = initFromStr(str1);
    printBign(n1);
    
    string str2 = "20000000000";
    n2 = initFromStr(str2);
    printBign(n2);
    
    Bign n3;
    n3 = plus(n1, n2);
    printBign(n3);
    
    return 0;
}