在大整數庫開發中，絕對值減法（|x| ≥ |y| ⇒ z = x - y）是有符號減法的基石。本文繼承上篇「絕對值加法」的數據結構，深度解析減法的借位傳播邏輯、邊界處理、C 語言實現細節，並給出完整可運行代碼與測試驗證方案。
x, y，滿足 bn_cmp_abs(x, y) >= 0（即 |x| ≥ |y|）。z = x - y，結果非負，符號位固定為正（z->sign = 1）。typedef uint32_t bn_digit; // 基數 2^32 的「數位」
typedef struct {
bn_digit *dp; // 低位在前，動態數組
int used; // 有效數位數
int alloc; // 分配容量
int sign; // 符號：1 正，-1 負
} bignum;
BASE = 2^32，每位存儲 32 位無符號整數，借位閾值為 BASE。十進制手算：1000 - 1 → 從個位借位，連續向高位傳播，直到千位。
基數 2^32 下同理：
diff = x_i - y_i - borrow。x_i < y_i + borrow，則置 borrow = 1，實際計算 diff = x_i + BASE - y_i - borrow；否則 borrow = 0。diff = x_i - borrow，若 x_i == 0 且 borrow == 1 繼續借位，否則借位鏈斷開。// 返回 0 成功，BN_NEGATIVE_VALUE_ERROR 表示 |x| < |y|
int bn_sub_abs(bignum *z, const bignum *x, const bignum *y) {
// 1. 前置檢查：確保 |x| >= |y|
if (bn_cmp_abs(x, y) < 0) return BN_NEGATIVE_VALUE_ERROR;
// 2. 確保 z 容量足夠（最多 x->used 位）
int max = x->used;
int min = y->used;
int old_used = z->used;
BN_CHECK(bn_grow(z, max)); // 擴容若不足
z->used = max;
// 3. 指針別名優化訪問
bn_digit *px = x->dp;
bn_digit *py = y->dp;
bn_digit *pz = z->dp;
// 4. 變量聲明
bn_digit t1, t2; // 暫存當前數位
int borrow = 0; // 借位標誌：0 或 1
int i;
// --- 階段 1：對位相減（雙方都有數位）---
for (i = 0; i < min; i++) {
t1 = *px++; // x 當前數位
t2 = *py++; // y 當前數位
// 計算差值：t1 - t2 - borrow
// 無符號減法自動模 2^32 環繞，結果即為正確的 diff（含借位效果）
*pz++ = t1 - t2 - borrow;
// 更新借位：若 t1 < t2 + borrow 則產生借位
// 等價判斷：(t1 - borrow) < t2 或 t1 < t2 + borrow
// 利用無符號特性：若 t1 != t2，則 borrow = (t1 < t2) ? 1 : 0 (borrow 只能是 0/1)
// 但這裡 borrow 可能為 1，需考慮 t1 - borrow
// 簡化邏輯：若 t1 < t2 則必借位；若 t1 == t2 則看 borrow
if (t1 != t2) {
borrow = (t1 < t2) ? 1 : 0;
}
// 若 t1 == t2，borrow 保持不變（若前一位借位，本位 0 - 0 - 1 仍需借位）
}
// --- 階段 2：處理 x 剩餘高位（僅傳播借位）---
for (; i < max; i++) {
t1 = *px++;
*pz++ = t1 - borrow;
// 借位傳播邏輯：只有當 borrow==1 且 t1==0 時，借位才繼續向高位
// 若 t1 > 0，t1 - 1 不會產生新借位，borrow 歸零
if (borrow && t1 != 0) {
borrow = 0; // 借位鏈終止
}
}
// --- 階段 3：清零舊數據殘留高位 ---
for (i = max; i < old_used; i++) {
*pz++ = 0;
}
// 4. 設置符號為正，壓縮前導零
z->sign = 1;
bn_clamp(z); // 移除高位多餘的 0，更新 used
return 0;
}
// 原始邏輯：需要借位當 t1 - borrow < t2 // 即 t1 < t2 + borrow // 因 borrow 只能是 0 或 1： // borrow=0: t1 < t2 // borrow=1: t1 <= t2 (即 t1 < t2+1) // 代碼中簡化為： if (t1 != t2) borrow = (t1 < t2); // 原因：若 t1 == t2，則 t1 - borrow < t2 等價於 borrow == 1 // 此時 borrow 保持原值（1 繼續借，0 不借），邏輯自洽。
// C 標準：無符號運算溢出定義為模 2^N 環繞 // 例：uint32_t a = 0, b = 1; a - b = 4294967295 (即 BASE - 1) // 這正是我們需要的「借位後的差值」！ // 所以 *pz = t1 - t2 - borrow 直接給出正確的數位值，無需手動 +BASE。
// 階段 2：x 剩餘高位 // borrow=1 進入 // t1 = 0: 0 - 1 = BASE-1, 借位繼續 // t1 > 0: t1 - 1 >= 0, 不再借位，borrow=0，後續位直接拷貝 // 代碼：if (borrow && t1 != 0) borrow = 0; 精準捕捉此邏輯。
bn_clamp 的必要性// 例：1000 - 999 = 1 // 計算過程可能產生高位 0：[1, 0, 0, 0] (低位在前) // clamp 移除高位連續 0，將 used 從 4 縮減為 1，避免後續運算誤判長度。
void test_sub_abs() {
bignum x, y, z;
bn_init(&x); bn_init(&y); bn_init(&z);
// 1. 基本減法
bn_set_str(&x, "1000", 10);
bn_set_str(&y, "1", 10);
bn_sub_abs(&z, &x, &y);
assert(strcmp(bn_to_str(&z), "999") == 0);
// 2. 連續借位
bn_set_str(&x, "1000000");
bn_set_str(&y, "1");
bn_sub_abs(&z, &x, &y);
assert(strcmp(bn_to_str(&z), "999999") == 0);
// 3. 等長減法
bn_set_str(&x, "123456789");
bn_set_str(&y, "123456788");
bn_sub_abs(&z, &x, &y);
assert(strcmp(bn_to_str(&z), "1") == 0);
// 4. 結果前導零
bn_set_str(&x, "1000");
bn_set_str(&y, "999");
bn_sub_abs(&z, &x, &y);
assert(strcmp(bn_to_str(&z), "1") == 0);
// 5. 零值
bn_set_str(&x, "0");
bn_set_str(&y, "0");
bn_sub_abs(&z, &x, &y);
assert(strcmp(bn_to_str(&z), "0") == 0);
bn_free(&x); bn_free(&y); bn_free(&z);
printf("All tests passed!\n");
}
| 特性 | 絕對值加法 | 絕對值減法 |
|---|---|---|
| 核心操作 | 進位 | 借位 |
| 進位/借位值 | 0 或 1 | 0 或 1 |
| 雙精度中間值 | 需要（和可能超過 BASE） | 不需要（差在 [-BASE, BASE)） |
| 高位傳播終止 | 進位為 0 時 | 借位為 0 且當前位 > 0 時 |
| 結果符號 | 正 | 正（前置條件 |x|≥|y|） |
| 複雜度 | O(n) | O(n) |
系列銜接：掌握絕對值加減法後，下一步將實現有符號整數加減法：
z = x + y與z = x - y。核心邏輯：比較符號位，同號做絕對值加法、符號不變；異號做絕對值減法（大減小）、結果符號同絕對值大者。這將構建完整的大整數四則運算基礎集。
