11月 07, 2008

【作品】大數運算 - Large Integer

@
  在比完今年(96 年)的資訊學科能力測驗後,有一題因為需要輸出 122 位的整數而無法得分。後來才發現,這種超過變數所能代表的最大整數,稱為超長整數,或通稱為大數運算。

  因為沒解出來的怨念,所以過了不久,我就花了幾個晚上,使用類別的方式將它完成了。


程式說明

  這支程式(或者該說是一個函式庫)宣告了一個large類別。成員變數包含一個代表正負號的布林(boolean)變數,以及一個用來"裝"數字的"字元向量(vector)容器字串(string)"。

  至於大數的運算,我使用重載運算子(operator overloading)重載了許多的運算符號,因此可以直覺的使用運算符號來做大數的演算。

Constructors:
‧建構子
large(void);
large(const int &); UPDATE
large(const char[]); UPDATE
large(const std::string &); NEW
large(const large &); NEW

‧解構子
~large(void);

Operators:
‧指派運算子(支援大數、整數或C式字串)
void operator=(int);
void operator=(const char *);
void operator=(const std::string &); NEW

‧正負號
large operator+(void);
large operator-(void);

‧四則運算、取餘數
large operator+(large);
large operator-(large);
large operator*(large);
large operator/=(large);
large operator%(large);

‧複合運算子
large operator+=(large);
large operator-=(large);
large operator*=(large);
large operator/(large);
large operator%=(large);

‧(前置/後置)遞增、遞減
large operator++(int);
large operator++(void);
large operator--(int);
large operator--(void);

‧邏輯運算
bool operator>(large);
bool operator>=(large);
bool operator<(large);
bool operator<=(large);
bool operator==(large);
bool operator!=(large);

‧位元運算(使用十進位,非二進位)
large operator>>(int);
large operator<<(int);

‧標準輸入、標準輸出
friend std::istream& operator>>(std::istream &, large &);
friend std::ostream& operator<<(std::ostream &, const large &);

‧隱式型別轉換(large → char *)
operator char *(void);

Functions:
‧取得大數長度
int size(void);
int length(void); NEW

‧取絕對值
large abs(void);

‧傳回是否為負數
bool is_negative(void); NEW

‧傳回是否為零
bool is_zero(void); UPDATE

  要使用這個類別,直接引括"large.h"這個標頭檔,並在編譯器連結指令加上"-llarge",就可以了。

  以下是一個大數運算的使用範例:

#include <iostream>
#include "large.h"

using namespace std;

int main(void)
{
    large a, b;

    cout << "Please ENTER two number a and b: ";
    cin >> a >> b;
    cout << endl;

    cout << "a = "      << a        << endl;
    cout << "b = "      << b        << endl << endl;

    cout << "a > b ? "  << (a > b)  << endl;
    cout << "a < b ? "  << (a < b)  << endl;
    cout << "a = b ? "  << (a == b) << endl << endl;

    cout << "a + b = "  << a + b    << endl;
    cout << "a - b = "  << a - b    << endl;
    cout << "a * b = "  << a * b    << endl;
    cout << "a / b = "  << a / b    << endl;
    cout << "a % b = "  << a % b    << endl << endl;

    cout << "a++ = "    << a++      << endl;
    cout << "a   = "    << a        << endl;
    cout << "++a = "    << ++a      << endl;
    cout << "a   = "    << a        << endl << endl;

    cout << "b-- = "    << b--      << endl;
    cout << "b   = "    << b        << endl;
    cout << "--b = "    << --b      << endl;
    cout << "b   = "    << b        << endl << endl;

    cout << "a << 4 = " << (a << 4) << endl;
    cout << "a >> 1 = " << (a >> 1) << endl << endl;

    system("pause");
}

  假如有遺漏什麼運算子,麻煩提醒我。若是有什麼錯誤跟意見,也歡迎提出來。


程式下載

  


更新紀錄:
‧08/04/05 正式貼出此類別庫。
‧08/05/04 將類別庫從 big 改名(正名?)為 large。
‧08/09/19 將程式改寫成可標準輸入超過 500 位的數字。
‧08/11/07 將代表數字的 vector<char> 改成 string。
‧08/11/07 部分函式內容改寫、更名。

2 回覆:

智涵 提到...

這種類別正名應該是BigInteger
我96年資訊科能力競賽也死在這題XD
我自己用List來實做BigInteger也只有做出+-*這三個算算子多載

你可以參考這個
有做出二進位的位移運算
http://www.codeproject.com/KB/cs/biginteger.aspx

小參 提到...

其實看起來兩種的使用都很廣泛
到底"正式"名稱是什麼我就不知道了@@"

位移運算的話其實是故意做十進位的
因為剛好就是vector的push跟pop動作XD

不過還是感謝你的資料
我會多加參考:)

張貼留言