square root for integer

isqrt.cpp

#include <concepts>
#include <bit>

template <std::unsigned_integral T>
constexpr auto isqrt(T x) noexcept {
    constexpr unsigned N = sizeof(T) * 8;
    
    // 1. 归一化：x | 1 确保 x=0 时求出的前导零也是安全的，& (N-2) 确保提取最大偶数
    const unsigned lz = std::countl_zero(static_cast<T>(x | 1)) & (N - 2);
    x <<= lz;
    
    // 2. 初始猜测值：奇偶位宽的初始逼近略有不同
    T y = 0;
    if constexpr (N == 16 || N == 64) {
        y = 2 + (x >> (N - 1));
    } else {
        y = 1 + (x >> (N - 2));
    }

    // 3. 动态分步牛顿迭代
    // 迭代次数规律：8位1次，16位2次，32位3次，64位4次 -> 公式: log2(N) - 2
    constexpr int iters = std::countr_zero(N) - 2;
    
    for (unsigned k = 1; k <= iters; ++k) {
        unsigned L = (1 << k) - 1;          // y 的左移量规律: 1, 3, 7, 15
        unsigned S = N - 3 * L - 2;         // x 的右移量规律: N - 3L - 2
        y = (y << L) + (x >> S) / y;
    }

    // 4. 误差校正与反归一化
    y -= x < y * y;
    return y >> (lz >> 1);
}