不能直接用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 <= right) {
uint64_t mid = left + (right - left) / 2;
if (mid > 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++免费学习笔记（深入）”；
实操建议：
- 初始值取
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;
}
}查表 + 位移法（仅限 32 位）：极致速度，牺牲空间
对 uint32_t 输入，平方根最大为 65535，可预计算 64K 大小的表。但更常用的是“逐位构造”法——类似手算开方，每次确定结果的一位 bit，共 16 轮，每轮只用位移和加法，零分支、零除法、常数时间。
适用场景：
- 资源极度受限（如裸机 MCU），且输入确定为 32 位
- 需要硬实时响应（最坏 16 步，无数据依赖分支）
- 编译期常量开方（可用 constexpr 展开）
核心逻辑：从高位开始试 res 的每一位，维护余数 rem，每次左移两位补入新两位，再试减 (res （即 <code>(2*res + 1) * 2^i）。
细节陷阱：
- 输入为 0 时循环不执行，需单独返回 0
- 位操作中
rem和res必须用足够宽类型（如uint32_t rem、uint16_t res），否则移位溢出 - 循环次数固定为 16，不能提前 break —— 否则破坏常数时间特性
整数开方真正难的不是算法选择，而是边界处理和溢出防御。二分最稳，牛顿最快但要防初值，位移法看似炫技实则对 32 位最实用。别迷信“最优”，先看你的 n 范围、是否允许分支、有没有除法成本限制。
