BigInteger(大整數)

• BigInteger(大整數)
  • 實作的功能
  • 實作原理
    • 儲存
    • 加法
    • 乘法
    • 負數
  • 完整代碼

實作的功能

• 負數
• vector動态配置設定記憶體
• 普通整數

  long long

  ,

  int

  , 字元串

  string

  指派
• 加法
• 乘法
• 重載了

  +

  ,

  +=

  ,

  *

  ,

  =

  ,

  -

  ,

  ==

  ,

  >

  ,

  <

實作原理

儲存

把一個整數每四位分解成一段儲存到

vector

中, 如把

7842365473734

分解成

3734

6547

8423

7

儲存

加法

把每一段分别相加, 然後把超過

10000

的部分加到

vector

下一個元素中

for (int i = ,x = ; x !=  || i < s.size() || i < b.s.size(); ++i) {
        if (i < s.size()) x += s[i];
        if (i < b.s.size()) x += b.s[i];
        c.s.push_back(x % BASE);
        x /= BASE;
    }
           

乘法

和列豎式做乘法類似, 每段分别交叉相乘

假如

BASE = 100

, 計算

1234 * 3421

, 每段儲存2位, 結果不會超過8位, 所有最多需要四段儲存

設

A = 1234

,

B = 3421

,

C = A * B

1
A	12
B	34

3	2	1
B[0] * A[1]
B[1] * A[1]	B[1] * A[0]
408	252 + 1156
C	4	22	15

類似豎式乘法, 超過

BASE

需要進位(多出的儲存到下一個元素)

是以如果用

int

來儲存每段資料, 要保證相乘再相加的結果依然在

int

範圍中.

sqrt[(2 ^ 31 - 1) / 2] =32767

, 是以我把

BASE

設為

10000

不會超過範圍

負數

一個正整數加一個負整數可能會出現有分段為負數有分段為正數的情況

如

-5445843685798 + 7842365473734 = 2396521787936

按照加法函數的運算結果為

3	2	1
2	3965	2179	-2064

最後一段為負值, 其餘段都是正數, 但是結果是正确的. 隻需要把

1

位置上退一位給

即可, 也就是

1

位置上的值變為

2178

,

位置上的值變為

10000 - 2064 = 7936

按照上述思路我們可以寫個

maintain

函數來維護各段的值符号相同

隻需要在輸出的時候調用, 因為即使符合不同, 儲存的值本質上還是相同的

void maintain() {
        if (s[s.size() - ] > )
            for (int i = ; i < s.size() - ; ++i)
                if (s[i] >= ) continue;
                else {
                    s[i + ]--;
                    s[i] += BASE;
                }
        else
            for (int i = ; i < s.size() - ; ++i)
                if (s[i] <= ) continue;
                else {
                    s[i + ]++;
                    s[i] -= BASE;
                }
    }
           

完整代碼

struct BigInteger {
    static const int BASE = ;
    static const int WIDTH = ;
    vector<int> s;

    BigInteger(int num) { *this = num; }

    BigInteger(long long num = ) { *this = num; }

    BigInteger operator=(long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num != );
        return *this;
    }

    BigInteger(string str) {
        *this = str;
    }

    BigInteger(const char s[]) {
        string str(s);
        *this = str;
    }

    BigInteger operator=(const string &str) {
        s.clear();
        int sign = ;
        int length = str.length();
        int left = ;//記錄數字的開始結束位置
        int right = length;
        if (str.at() == '-') {
            sign = -;
            length--;
            left++;
        }
        int n = (length - ) / WIDTH + ;//vector數目
        for (int i = ; i < n; ++i) {
            int end = right - i * WIDTH;
            int start = max(left, end - WIDTH);
            int x;
            sscanf(str.substr(start, end - start).c_str(), "%d", &x);
            s.push_back(x * sign);
        }
        return *this;
    }

    BigInteger operator+(const BigInteger &b) const {
        BigInteger c;
        c.s.clear();
        for (int i = , x = ; x !=  || i < s.size() || i < b.s.size(); ++i) {
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            x /= BASE;//需要進位的部分
        }
        return c;
    }

    BigInteger operator-(const BigInteger &b) const {
        BigInteger c;
        c.s.clear();
        for (int i = , x = ; x !=  || i < s.size() || i < b.s.size(); ++i) {
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x -= b.s[i];
            c.s.push_back(x % BASE);
            x /= BASE;//需要進位的部分
        }
        c.clean();
        return c;
    }


    BigInteger operator-=(const BigInteger &b) {
        *this = *this - b;
        return *this;
    }

    BigInteger operator+=(const BigInteger &b) {
        *this = *this + b;
        return *this;
    }

    bool operator==(const BigInteger &b) {
        if (b.s.size() != s.size()) return false;
        for (int i = s.size() - ; i >= ; i--)
            if (s[i] != b.s[i]) return false;
        return true;
    }

    bool operator>(const BigInteger &b) {
        if (s.front() >  && b.s.front() <= ) return true;
        else if (s.front() <  && b.s.front() >= ) return false;
        return (*this - b).s.front() > ;
    }

    bool operator<(const BigInteger &b) {
        if (s.front() >  && b.s.front() <= ) return false;
        else if (s.front() <  && b.s.front() >= ) return true;
        return (*this - b).s.front() < ;
    }

    BigInteger operator*(const BigInteger &b) const {
        BigInteger res;
        res.s.resize(s.size() + b.s.size());
        for (int i = ; i < b.s.size(); ++i)
            for (int j = ; j < s.size(); ++j)
                res.s[i + j] += b.s[i] * s[j];
        //進位
        for (int i = ; i < res.s.size() - ; ++i) {
            res.s[i + ] += res.s[i] / BASE;
            res.s[i] %= BASE;
        }
        //最後的一段上可能沒有值, 是以需要pop
//        if (res.s[res.s.size() - 1] == 0)
//            res.s.pop_back();
        res.clean();
        return res;
    }

    void clean() {
        int i = s.size();
        while (s[--i] == )
            s.pop_back();
    }

    void maintain() {
        //一個數的符号僅由它的最前面一段決定, 也就是vector中最後的元素
        if (s[s.size() - ] > )
            for (int i = ; i < s.size() - ; ++i)
                if (s[i] >= ) continue;
                else {
                    s[i + ]--;//後面位置小于0, 需要前面位置退位
                    s[i] += BASE;
                }
        else
            for (int i = ; i < s.size() - ; ++i)
                if (s[i] <= ) continue;
                else {
                    s[i + ]++;
                    s[i] -= BASE;
                }
    }

    void print() {
        maintain();
        printf("%d", s[s.size() - ]);
        for (int i = s.size() - ; i >= ; i--)
            //負數隻需要輸出第一段的符号即可, 後面沒有滿4位的應該用0補到4位
            printf("%04d", abs(s[i]));
    }
}