std::sqrt转double再取整不严谨，牛顿迭代法（防溢出用long long、整数终止条件）和位移搜索法（纯整数、O(log n)）才是整数平方根的可靠实现。
直接用 std::sqrt 转成 double 再取整，对大多数场景够用；但若输入是 long long、要求严格向下取整、或运行在无浮点硬件的嵌入式环境，就必须自己实现——牛顿迭代法和位移搜索（bit shift search）是两种真正高效且可控的选择。
牛顿迭代法求整数平方根：为什么比二分快，又怎么防溢出
牛顿法收敛极快（二次收敛），通常 5–7 次迭代就能覆盖 int 全范围；但它默认输出浮点近似值，直接转 int 会因舍入误差错判边界。
- 必须用
long long做中间计算：比如res = (res + x / res) / 2中，若res是int，x / res可能截断，且res + x / res易溢出 - 停止条件别用
res != last：浮点下可能死循环；改用整数判断——迭代后检查(res * res x) - 初始值设为
x或x >> 1都可，但x == 0 || x == 1必须特判，否则除零或无效迭代
示例核心逻辑：
long long r = x;
while (r * r > x) {
r = (r + x / r) >> 1;
}
return static_cast<int>(r);位移搜索法（bit shift search）：纯整数、零浮点、确定性 O(log n)
本质是手动模拟二进制长除法开方，从最高有效位开始逐位试探，每步只做位运算和加法，完全规避乘除与浮点。适合裸机、DSP、或对时序有硬要求的场合。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 起始位设为
1 （对 <code>int）或1LL （对 <code>long long），然后右移试探 - 每轮计算
candidate = root | bit，再判断candidate * candidate ；注意 <code>candidate * candidate仍需用long long防溢出 - 不依赖初始猜测，最坏也是 32/64 步，性能恒定，无分支预测失败风险
关键片段：
long long root = 0;
long long bit = 1LL << 31; // for 32-bit input, adjust for 64-bit
while (bit > x) bit >>= 2;
while (bit) {
long long candidate = root | bit;
if (candidate <= x / candidate) { // avoid overflow: use division instead of candidate*candidate
root = candidate;
x -= candidate * candidate;
}
bit >>= 2;
}
std::sqrt 在整数场景下的三个隐藏陷阱
很多人以为 static_cast<int>(std::sqrt(x))</int> 安全，实际在边界上极易翻车：
-
x = 2147395600（即46340²）：某些平台std::sqrt返回略小于46340.0的值，static_cast<int></int>得到46339，再验证46339 * 46339 < x就暴露了 -
x是long long且大于2^53：double无法精确表示所有整数，sqrt输入已失真 - 未检查
isnan：若误传负数，std::sqrt返回NaN，后续static_cast行为未定义（通常得 0，但不可靠）
真正需要“整数平方根”的时候，别把问题交给浮点单元去猜——位移搜索给你确定性，牛顿迭代给你速度，而 std::sqrt 只是方便，不是答案。
