C++如何实现高效的整数开平方根（不使用sqrt函数）-C++-PHP中文网

不能直接用sqrt因嵌入式/竞赛/安全场景禁用浮点函数，易致精度误差、异常或硬件不支持；整数开方需用二分或位运算法确保整除、无溢出、常数时间。

c++如何实现高效的整数开平方根（不使用sqrt函数）

为什么不能直接用 `sqrt`？常见场景和约束

很多嵌入式、竞赛或安全敏感场景禁止调用标准库浮点函数——sqrt 依赖 double 运算，可能引入精度误差、不可预测的浮点异常，或触发硬件不支持的指令。整数开方只要求返回满足 res * res ≤ n 的最大整数 <code>res，完全可纯整数运算解决。

二分查找法：稳定、易懂、无溢出风险

对非负整数 n，平方根一定落在 [0, n] 区间（n ≥ 1 时其实只需到 n/2 + 1，但为简化逻辑直接取 n 更安全）。二分查找每次比较 mid * mid 与 n，避免浮点，且时间复杂度 O(log n)，对 uint64_t 最多 64 次迭代。

关键注意点：

mid * mid 可能溢出，尤其当 n 接近 UINT64_MAX 时 —— 改用 mid > n / mid 判断（整除向下取整，等价于 mid * mid > n，且无溢出）
边界初始化必须是 left = 0, right = n；若设 right = n / 2 + 1，需单独处理 n == 0 和 n == 1
循环条件用 left ，退出后 <code>right 即为所求结果（因为始终维护 res ≤ right）

uint64_t isqrt_binary(uint64_t n) {
    if (n == 0) return 0;
    uint64_t left = 1, right = n;
    while (left  n / mid) {  // 避免 mid*mid 溢出
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

牛顿迭代法：更快但需小心初始值和收敛性

公式为 x_{k+1} = (x_k + n / x_k) / 2，对整数开方，用整数除法并保证单调收敛即可。它通常比二分快（O(log log n)），但初始值选差了可能多迭代几次，甚至在 n == 0 或 n == 1 时除零。

实操建议：

C++14 标准参考

C++14 标准最终草案参考资料，适合旧项目兼容、语言特性对照、标准库行为核对和现代 C++ 迁移学习。

下载

初始值取 max(1UL, n) 安全，但更优的是 n ? (1ULL （用位长估算，一次到位）
迭代终止条件不是「前后两次相等」，而是 next >= curr —— 因为整数除法导致序列非严格递减，一旦开始不下降就已收敛
必须加 if (curr == 0) break; 防止 n / curr 除零（n == 0 时初始 curr 可能为 0）

uint64_t isqrt_newton(uint64_t n) {
    if (n == 0) return 0;
    uint64_t curr = n;
    for (;;) {
        uint64_t next = (curr + n / curr) / 2;
        if (next >= curr) return curr;
        curr = next;
    }
}