您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 處理超長整數的兩種經典實現 (字元陣列與流式讀取)

編輯：Java 相關知識

當整數位數超過 `long` (19 位) 或 `BigInteger` 建構子字串長度限制時，需自行實現超長整數讀取與儲存。本文介紹兩種經典方案：**字元陣列全量載入** 與 **流式逐字元處理**，並分析適用場景與擴展方向。

方案一：字元陣列全量載入 (適合中等長度、需隨機存取)


public static void readFullArray() throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String line = reader.readLine(); // 一次性讀入整行
    if (line == null) return;
    
    int[] digits = new int[line.length()];
    for (int i = 0; i < line.length(); i++) {
        char c = line.charAt(i);
        if (c < '0' || c > '9') throw new NumberFormatException("非數字字元: " + c);
        digits[i] = c - '0'; // ASCII 轉數值
    }
    
    // 輸出驗證
    for (int d : digits) System.out.print(d);
    System.out.println();
    
    // 後續可實現大數加減乘除...
}

優點： 實現簡單、支援隨機存取、易於實現大數運算 (模擬豎式算式)。
缺點： 記憶體佔用 O(N)、超大輸入 (GB 級) 會 OOM。

方案二：流式逐字元處理 (適合極長輸入、串流管道)


public static void readStreaming() throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int[] buffer = new int[1000]; // 固定緩衝區，或用 ArrayList 動態擴容
    int count = 0;
    int ch;
    
    while ((ch = reader.read()) != -1 && ch != '\n' && ch != '\r') {
        if (ch < '0' || ch > '9') throw new NumberFormatException("非數字字元: " + (char)ch);
        if (count == buffer.length) {
            buffer = Arrays.copyOf(buffer, buffer.length * 2); // 動態擴容
        }
        buffer[count++] = ch - '0';
        System.out.print(ch - '0'); // 即時回顯
    }
    System.out.println();
    
    // 輸出緩衝區內容
    for (int i = 0; i < count; i++) System.out.print(buffer[i]);
    System.out.println();
}

優點： 記憶體恆定/線性增長、支援管道輸入 (`cat huge_num.txt | java App`)、無單行長度限制。
缺點： 無法隨機存取、需自行管理緩衝區擴容。

核心技術細節對比

維度	字元陣列法	流式法
記憶體模型	一次性分配 N int (4N bytes)	分塊分配，峰值 ~2N bytes
最大處理長度	受限於堆記憶體 (~2億位數)	理論無上限 (磁碟/網路流)
隨機存取	O(1)	需全量載入或重讀
適用場景	競程、中等大數運算、教學演示	日誌分析、流式計算、超大數據管道
錯誤處理	統一驗證整行	即時發現非法字元

生產級擴展：大數運算雛形

讀取只是第一步，實際應用需實現運算。以加法為例：


public static int[] add(int[] a, int[] b) {
    int maxLen = Math.max(a.length, b.length);
    int[] result = new int[maxLen + 1]; // 可能進位
    int carry = 0;
    
    for (int i = 0; i < maxLen; i++) {
        int ai = i < a.length ? a[a.length - 1 - i] : 0;
        int bi = i < b.length ? b[b.length - 1 - i] : 0;
        int sum = ai + bi + carry;
        result[result.length - 1 - i] = sum % 10;
        carry = sum / 10;
    }
    result[0] = carry;
    return result[0] == 0 ? Arrays.copyOfRange(result, 1, result.length) : result;
}

現代替代方案：直接使用 BigInteger

Java 內建 `java.math.BigInteger` 已高度優化 (基於 `int[]` + 原生方法)，支援任意精度：


// 讀取超長整數
BigInteger huge = new BigInteger(new BufferedReader(new InputStreamReader(System.in)).readLine());
// 或流式 (需自行拼接字串)
BigInteger huge = new BigInteger(streamChars.collect(StringBuilder::new, StringBuilder::append, StringBuilder::append).toString());

// 運算
BigInteger sum = a.add(b);
BigInteger product = a.multiply(b);
BigInteger modPow = a.modPow(exp, mod); // 模冪，密碼學核心

建議： 除非教學、極特殊環境 (無標準庫)、或需自定義進制/編碼，**生產代碼直接用 `BigInteger`**。