Linux 核心整數平方根算法 (int_sqrt) 移植與解析

背景

Linux 核心提供了 int_sqrt 函數，用於在無浮點運算環境下快速計算無號長整數的整數平方根（向下取整）。其原理基於「位運算試商法」，類似手算開平方的二進制版本。

算法原理

設輸入為 x，從最高位開始嘗試構建結果 res。變數 one 初始為最高位的 2 的冂次方（對應 64 位系統為 1<<62，32 位為 1<<30）。每輪迭代中，若 op >= res + one，則減去並更新 res；隨後 res 右移 1 位，one 右移 2 位，直到 one 為 0。

移植代碼 (標準 C)

#include <stdio.h>
#include <stdint.h>

#if defined(__LP64__) || defined(_WIN64)
#define BITS_PER_LONG 64
#else
#define BITS_PER_LONG 32
#endif

unsigned long int_sqrt(unsigned long x) {
    unsigned long op = x, res = 0;
    unsigned long one = 1UL << (BITS_PER_LONG - 2);

    while (one > op) one >>= 2;

    while (one != 0) {
        if (op >= res + one) {
            op -= res + one;
            res += 2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

int main(void) {
    printf("%lu\n", int_sqrt(16));   // 4
    printf("%lu\n", int_sqrt(100));  // 10
    printf("%lu\n", int_sqrt(123456789)); // 11111
    return 0;
}

執行結果

輸出：4

適用場景

• 嵌入式系統、核心模組、無 FPU 環境。
• 需整數平方根且不想引入 math.h 時。