Linux內核整數平方根算法：位運算迭代逼近實現

Linux 內核中沒有浮點支持，但提供了高效的整數平方根實現 int_sqrt，基于「二進制試商法」通過位運算迭代逼近，無需除法、浮點或數學庫。本文詳細解析算法邏輯、代碼實現與測試驗證。

算法原理：二進制試商法

求 √x 的整數部分，本質是找最大的 y 使 y² ≤ x。利用二進制特性，從最高位向最低位逐位確定 y 的每一位：

1. 初始化 one = 1 << (位寬-2)，即最高可能的平方位（如 32 位系統 1<<30）。
2. 將 one 右移直到 ≤ x，對齊最高有效位。
3. 迭代：嘗試在當前結果 res 基礎上加上 one，若 (res+one)² ≤ x（通過 op >= res+one 判斷），則確定該位為 1，更新 op 和 res。
4. one 每次除 4（右移 2 位），res 除 2（右移 1 位），處理下一位。

核心代碼（源自 Linux 內核）

#include 

#ifdef CONFIG_64BIT
#define BITS_PER_LONG 64
#else
#define BITS_PER_LONG 32
#endif

unsigned long int_sqrt(unsigned long x) {
    unsigned long op = x;      // 被開方數（會被修改）
    unsigned long res = 0;     // 結果累積
    unsigned long one = 1UL << (BITS_PER_LONG - 2);  // 最高可能的平方位

    // 對齊 one 到 x 的最高有效位附近
    while (one > op) one >>= 2;

    while (one != 0) {
        if (op >= res + one) {      // 試探：若 (res+one)^2 <= x
            op -= res + one;        // 減去試探值對應的平方增量
            res += 2 * one;         // 結果該位置 1（res 實際存儲 2*真實結果）
        }
        res >>= 1;                  // 準備下一位
        one >>= 2;                  // 下一位權重
    }
    return res;
}

關鍵變量含義

測試驗證

int main() {
    unsigned long test_vals[] = {0, 1, 2, 3, 4, 15, 16, 17, 100, 1000, 65535, 65536};
    int n = sizeof(test_vals)/sizeof(test_vals[0]);

    for (int i = 0; i < n; i++) {
        unsigned long v = test_vals[i];
        unsigned long r = int_sqrt(v);
        printf("int_sqrt(%lu) = %lu  (check: %lu^2=%lu, %lu^2=%lu)\n",
               v, r, r, r*r, r+1, (r+1)*(r+1));
    }
    return 0;
}

運行結果

int_sqrt(0) = 0   (check: 0^2=0, 1^2=1)
int_sqrt(1) = 1   (check: 1^2=1, 2^2=4)
int_sqrt(2) = 1   (check: 1^2=1, 2^2=4)
int_sqrt(3) = 1   (check: 1^2=1, 2^2=4)
int_sqrt(4) = 2   (check: 2^2=4, 3^2=9)
int_sqrt(15) = 3  (check: 3^2=9, 4^2=16)
int_sqrt(16) = 4  (check: 4^2=16, 5^2=25)
int_sqrt(17) = 4  (check: 4^2=16, 5^2=25)
int_sqrt(100) = 10  (check: 10^2=100, 11^2=121)
int_sqrt(1000) = 31  (check: 31^2=961, 32^2=1024)
int_sqrt(65535) = 255  (check: 255^2=65025, 256^2=65536)
int_sqrt(65536) = 256  (check: 256^2=65536, 257^2=66049)

所有結果均正確：返回最大的 y 使 y² ≤ x。

算法特性

總結

Linux 內核 int_sqrt 是位運算精妙應用的教科書級範例：

1. 將平方根求解轉化為逐位試探，利用 (a+b)² = a² + 2ab + b² 的遞推關係。
2. 變量 res 存儲 2a，one 存儲 b²，op 存儲 x - a²，完美避開乘法。
3. 代碼短小、無分支預測失敗風險、確定性執行時間，極適合內核與實時場景。

掌握此算法，不僅能在無浮點環境求平方根，更能領悟「用位運算重構數學運算」的系統級優化智慧。