上周有个朋友来问我，说面试时遇到一道题：“判断一个整数是不是完全平方数，但不准用 Math.sqrt。”他第一反应是这不简单吗，开个方再乘回来比一下就行。但真让他写的时候，他卡住了——离开现成的开方函数，脑子里的“整数开方”居然是一片空白。
这不怪他。日常写业务代码，遇到这种需求，一行Math.sqrt(num)就搞定了，谁还会去想底层怎么算？但面试官要的就是你把这一行函数拆开，用最基本的运算去实现它。这不是一道刁难人的题，反而是非常经典的一类“造轮子”题目：判断完全平方数、求平方根、求最大公约数……本质上都是在考察你对数学性质和算法边界的理解。这篇就把我整理过的几种解法一次讲清楚：二分查找、牛顿迭代、奇数求和、按位构造。每种都给出原理、代码、复杂度，还会重点说说我在面试和实际项目中反复踩过的坑，尤其是整数溢出和浮点精度这两个地方。
1. 题目拆解与思路总览
1.1 这道题到底在考什么
严格来说，完全平方数的定义很朴素：一个整数 n 是另一个整数 x 的平方，即存在整数 x 使得 x*x == n。题目要求“不用 Math.sqrt”，真正的含义不是“故意刁难”，而是要求你在整数域内解决问题，不要依赖标准库里封装好的浮点开方逻辑。
为什么面试官偏爱这类题？因为它能一次性考察四个维度。第一，数学性质，比如平方函数的单调性、完全平方数末位数字的规律、相邻平方数之间的差值关系。第二，算法设计，你能不能把一个看起来“必须开方”的问题，转化成搜索、迭代、计数或者逐位构造的问题。第三，边界条件，0、1、负数、超大整数这些 case 有没有考虑清楚。第四，误差控制，一旦涉及浮点数，舍入误差会不会导致误判。
很多人在面试时只盯着“怎么不用 sqrt”，上来就写了一个 for 循环从 1 试到 n，这当然也能得到正确答案，但暴露出来的是对复杂度和边界思考的缺失。所以这篇文章我不打算只给一个解法，而是把这四条路线全部过一遍，这样你面试时无论被追问到哪一层，手里都有牌可以打。
1.2 四条解决路径先看图
我把常见的解法归纳成四条路径，各有各的适用场景，没有银弹：
| 解决路径 | 核心思想 | 时间复杂度 | 是否依赖浮点 | 典型场景 |
|---|---|---|---|---|
| 二分查找 | 利用平方函数单调性搜索 | O(log n) | 否 | 通用，面试首选 |
| 牛顿迭代 | 切线法逼近方程 x^2 - n = 0 的根 | 对数级收敛 | 可避免 | 数值计算，追求收敛速度 |
| 奇数求和 | 利用前 k 个奇数之和等于 k^2 | O(sqrt n) | 否 | n 较小，实现最简单 |
| 按位构造 | 从高位到低位逐位试商，类似手工开方 | O(log n) | 否 | 大整数，嵌入式环境 |
先记住这张表，后面每一节详细展开。需要提醒的是，不要急着写代码，先想清楚题目的约束条件到底是什么：输入 n 是否保证非负？n 的最大范围是多少？运行环境是否支持大整数类型？这些约束直接决定了你选哪条路，也决定了你写的代码会不会在边界上翻车。
2. 二分查找：最稳妥的通用方案
2.1 凭什么二分能找到答案
如果 n 是非负整数，那么方程 x*x == n 的候选解一定落在闭区间 [0, n] 内。当 n 大于 1 时，上界甚至可以收紧到 n/2，因为 (n/2)^2 在 n 大于等于 2 时一定大于 n，但实际上多收紧这几步意义不大，二分搜索多一两次迭代几乎无感，代码上我用 n//2 纯粹是心理上觉得“范围小了一点”。
关键在于平方函数 f(x) = x*x 在 x >= 0 时严格单调递增。单调性保证了根只有一个，而且左边都比根小，右边都比根大。所以可以像查字典一样逐步缩小区间：如果 mid*mid 小于 n，说明根在右边，把左边界挪到 mid + 1；如果 mid*mid 大于 n，说明根在左边，把右边界挪到 mid - 1。最终 left 会指向第一个满足 left*left >= n 的整数，此时只需要判断 left*left 是否等于 n。
我习惯用闭区间 [left, right] 配合 while (left <= right) 的写法，因为退出条件最直观，不熟练的人建议也先从这个版本开始。等你写熟了，再尝试左闭右开或者其他变体。
2.2 代码实现：Python / JavaScript / C 三个版本
先放 Python 版本。为什么先放 Python？因为它在算法题里最接近伪码，逻辑最清晰，而且整数是任意精度的，不需要在一开始就操心溢出问题。
def is_perfect_square(n: int) -> bool: if n < 0: return False if n < 2: return True left, right = 2, n // 2 while left <= right: mid = left + (right - left) // 2 square = mid * mid if square == n: return True elif square < n: left = mid + 1 else: right = mid - 1 return False这里有两个细节我想多说一句。第一，mid = left + (right - left) // 2，不要写成(left + right) // 2。虽然在这道题里 left 和 right 都不大，但一旦 n 接近 32 位有符号整数的上限，left + right 可能直接溢出成负数，这个坑我早年真的踩过。第二，n < 2直接返回 True，因为 0 和 1 都是完全平方数，这也避免了下面对 2 和 1 做无用功。
然后是 JavaScript 版本。JS 里唯一要注意的是，不要把 mid 的计算写成位运算，因为 JS 的位运算会先把 Number 转成 32 位有符号整数，一旦 n 超过 2^31，右移和按位或的结果就完全不对了。
function isPerfectSquare(n) { if (n < 0) return false; if (n < 2) return true; let left = 2; let right = Math.floor(n / 2); while (left <= right) { const mid = left + Math.floor((right - left) / 2); const square = mid * mid; if (square === n) return true; else if (square < n) left = mid + 1; else right = mid - 1; } return false; }再放一个 C 语言版本。C 里最大的坑是类型溢出，我特意用unsigned long long并配合除法判断来规避。这里要说清楚：在 32 位有符号 int 下，INT_MAX 约等于 21.47 亿，而 sqrt(INT_MAX) 约等于 46340，所以一旦 mid 超过 46340，mid*mid 就溢出成负数或者被截断，整个判断就全乱了。解决方案有两个，要么把中间乘法转成 long long，要么干脆避免乘法，用除法比较。
bool isPerfectSquare(unsigned long long n) { if (n < 2) return true; unsigned long long left = 2, right = n / 2; while (left <= right) { unsigned long long mid = left + (right - left) / 2; // 避免 mid * mid 溢出的除法比较 if (mid <= n / mid) { if (mid * mid == n) return true; left = mid + 1; } else { right = mid - 1; } } return false; }因为 n 是unsigned long long，n / mid 一定不会溢出，mid <= n / mid 就等价于 mid*mid <= n，但不会产生乘法溢出。这是所有需要手写二分平方根的 C/C++ 代码里我最推荐的一种写法。
2.3 边界条件与整数溢出：这里最容易阴沟翻船
边界条件这块，我整理了一份速查表，面试前最好默写一遍：
| 输入 | 结果 | 原因 |
|---|---|---|
| n = 0 | True | 0 = 0^2 |
| n = 1 | True | 1 = 1^2 |
| n < 0 | False | 负数没有实数平方根 |
| n = 2 | False | 2 介于 1^2 和 2^2 之间 |
| n = 2147483647 | False | INT_MAX，sqrt 约 46340，不是完全平方数 |
| n = 2147395600 | True | 46340^2，正好等于 2147395600，完美避开乘法溢出陷阱 |
关于溢出，我还想专门多说一点。很多人以为用了无符号整数就安全了，其实无符号整数只是“溢出方向”不同，该溢出还是溢出。只有两种办法是真正稳妥的：把平方换成除法比较；或者把乘法放到足够大的类型里做。在 C 里如果编译器支持__int128，用__int128 square = (__int128)mid * mid也是可以的，但可移植性不如除法版本。
另一个细节是：如果你用有符号整数，n / mid在 n 为负数时结果是向零取整还是向下取整，不同语言差异很大。所以我在写任何版本的第一步，永远是先把 n < 0 过滤掉。这不是啰嗦，是把语义锁死在非负整数域内，后面所有位运算、除法、取模都才安全。
3. 牛顿迭代：数值派的优雅解法
3.1 从切线逼近说起
牛顿迭代法本来是求方程根的数值方法，套用到开平方上非常漂亮。我们要求的是 x^2 - n = 0 的根，设 f(x) = x^2 - n，那么 f'(x) = 2x。从某个初始值 x_k 出发，沿着 f 的切线方向找零点，得到下一个近似值：
x_{k+1} = x_k - f(x_k) / f'(x_k) = x_k - (x_k^2 - n) / (2*x_k) = (x_k + n / x_k) / 2
这个公式有一个非常直观的解释：如果 x_k 比真正的平方根大，那么 n / x_k 就会比真正的平方根小，这时候取两者的平均值，就会比原来的 x_k 更接近真值；反过来也是一样。所以无论初始值从哪边出发，序列都会像两边夹击一样快速逼近 sqrt(n)。
在实际迭代中，这个收敛速度是二次的，意思是每迭代一轮，有效数字的位数大约翻一倍。以 n = 17 为例，x0=17，x1=(17 + 1)/2=9，x2=(9 + 17/9)/2≈5.444，x3≈4.318，x4≈4.128，x5≈4.1231056256，到这里其实已经非常接近 sqrt(17)≈4.12310562561766 了。也就是说，从初值 n 出发，通常五六次迭代就能达到 double 的精度。
3.2 整数场景下，终止条件怎么定才稳
如果直接写浮点牛顿，跳出条件一般是 |x_k^2 - n| < eps，但 eps 选多少很麻烦，选大了可能把非完全平方数误判成完全平方数，选小了又可能因为浮点误差永远不满足条件而死循环。所以我的建议是：不要依赖浮点 eps，改用整数版本。
整数牛顿的精髓是把迭代公式里的浮点除法全部换成整数除法：
x_{k+1} = (x_k + n // x_k) // 2
这个序列在非负整数域里单调下降，最终会落在 floor(sqrt(n)) 上。终止条件不是“误差小于多少”，而是当 x_{k+1} >= x_k 时停止，因为这个时候序列已经跌不动了，说明 x_k 就是整数平方根。然后只需要检查 x_k*x_k == n 就能判断是不是完全平方数。
def is_perfect_square(n: int) -> bool: if n < 0: return False if n < 2: return True x = n while True: y = (x + n // x) // 2 if y >= x: break x = y return x * x == n这段代码极其简洁，而且完全不碰浮点。很多人第一次看到会疑惑：为什么 y >= x 就停？原因是整数除法只会让序列越迭代越小，一旦下一轮不再变小，说明已经到达不动点，这个不动点就是不超过 sqrt(n) 的最大整数。我再强调一次，最后一定要用x * x == n判断，因为 x 是整数平方根，如果 n 本身不是完全平方数，x^2 一定小于 n，而不会等于 n。
3.3 浮点精度的坑：大整数场景下别指望 double
写到这里必须泼一盆冷水：浮点牛顿的大整数场景是个雷区。double 只有约 53 位二进制有效数字，换算成十进制大约是 15 到 16 位。当 n 大到 10^16 这个量级时，很多整数根本没有办法在 double 里精确表示，更不用说对这样的数开方再做乘法回来比对。
以 Python 为例，Python 的 int 是任意精度的，可以处理几百位的整数，但 Python 的 float 底层还是 C 的 double，精度跟 int 完全不是一个量级。所以如果你写：
import math x = math.sqrt(n) # n 是超大整数这里 n 会先被转成浮点数，精度直接丢失，后面再判断int(x) * int(x) == n就可能把本来是完全平方数的数误判成非完全平方数。
Julia 语言里虽然有 BigFloat、BigInt 这些高精度类型，处理原则也是一样的：要么用 BigInt 做整数牛顿，要么用 BigFloat 并且显式设置足够高的精度，否则照样踩精度坑。JS 里同样，Number 超过 Number.MAX_SAFE_INTEGER 之后，整数精度都开始丢失，更别提开方了。这种情况下我建议直接上 BigInt，配合整数二分或者整数牛顿都是安全的。
C++ 版本我也顺手贴一个，用unsigned long long时注意加法溢出问题：
bool isPerfectSquare(unsigned long long n) { if (n < 2) return true; unsigned long long x = n; while (true) { unsigned long long y = (x / 2) + (n / x) / 2; if (y >= x) break; x = y; } return x * x == n; }这里我把(x + n / x) / 2改成了(x / 2) + (n / x) / 2，目的是避免 x + n/x 在 n 接近 ULLONG_MAX 时溢出。当然这样会引入整除时的精度损失，但对收敛过程影响极小，换来的是更稳妥的范围。如果要硬刚最大值的无符号 64 位整数，更保险的做法是限制 n 小于 2^62，或者在编译器支持的前提下使用__int128做中间运算。
4. 数学性质派：奇数求和与快速排除
4.1 平方数相邻差值构成奇数等差数列
这是一个我私心非常喜欢的数学事实：第 k 个正奇数等于 2k - 1，而前 k 个正奇数之和正好等于 k^2。用数学归纳法很容易证明：1 = 1^2，1 + 3 = 4 = 2^2，1 + 3 + 5 = 9 = 3^2…… 所以判断 n 是不是完全平方数，可以不断从 n 中减去 1、3、5、7……，如果最后余数刚好为 0，说明 n 是某个数的平方，减法执行了几次，平方根就是几。
举个例子来演算。n = 9：9 - 1 = 8，8 - 3 = 5，5 - 5 = 0，一共减了 3 次，所以 9 是 3^2。再看 n = 10：10 - 1 = 9，9 - 3 = 6，6 - 5 = 1，1 - 7 = -6，减到第 4 次的时候不够减了，说明 10 落在 3^2 和 4^2 之间，不是完全平方数。
代码异常简单：
def is_perfect_square(n: int) -> bool: if n < 0: return False odd = 1 while n > 0: n -= odd odd += 2 return n == 0注意循环结束之后判断的是n == 0，不是n <= 0。因为当 n 不是完全平方数时，最后一次减法会让 n 变成负数，所以n == 0才能准确区分两种情况。
4.2 复杂度分析：看起来 O(sqrt n)，但 32 位范围内真不慢
很多资料直接说这个方法是 O(sqrt n)，然后就把它贬得一文不值。但我觉得应该给出一个更精确的量级判断：循环次数等于 floor(sqrt(n)) 加 1。在最坏情况下，n 接近 32 位有符号整数最大值 2147483647 时，循环约 46340 次。四万多次循环在现代 CPU 上就是一瞬间的事，毫秒级都算不上。所以在算法面试里，如果你写出这个版本，面试官其实不会直接否定，而是会继续问“如果 n 是 10^18 呢”。
10^18 的平方根是 10^9，循环十亿次，这就明显不可接受了。所以这个方法的适用边界非常清晰：n 不超过 32 位甚至 16 位整数范围时，它简单、直观、不容易写错；一旦 n 的量级上来，必须换二分或者整数牛顿。我个人的建议是，这个方法可以当作“热身答案”，但不要把它当成最终方案展示，除非题目明确限制了 n 的范围。
4.3 末位数字快速排除：能被立刻打发的直接打发
在所有方案之前加一个“快速排除”的步骤，往往能省下大量计算。十进制下，完全平方数的末位数字只可能是 0、1、4、5、6、9。换句话说，如果 n 的末位是 2、3、7、8，那么它一定不是完全平方数，可以直接返回 false。这个判断成本极低，却可以过滤掉大约四成的随机整数。
更进一步的优化是取模 16，因为一个完全平方数对 16 取模，只可能是 0、1、4、9。在二进制下，n & 15 就等价于 n % 16（只对非负整数成立），配合查表可以非常高效地排除约六成的候选数。
if n & 15 in (2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15): return False这里特别提醒一点：C 语言里如果有符号整数做 n & 15，因为只取低 4 位，结果和 n % 16 对有符号数可能不同。表达式 n % 16 在 C 里负数结果是负的，而位与的结果一定是非负的。所以这段代码最好只作用在已经确保 n >= 0 的前提下。无符号整数做这种位运算倒是没有语义问题，这也是为什么很多底层代码库偏爱无符号类型写位运算。但注意，这个快速排除只能用来否定，不能用来肯定——末位是 0、1、4、5、6、9 只是必要条件，不充分，比如 21 末位是 1，但它不是完全平方数。
5. 进阶：按位构造开方法
5.1 手工竖式开方的思路变成算法
小学学过的竖式开方，本质上就是“逐位试商”：把被开方数从右向左每两位分一组，每一组对应结果的一位，试商时靠当前余数来估算下一位。把这个过程搬到二进制里，就变成了从高到低逐位确定平方根的二进制位。
逐位构造的核心思想是贪心：假设当前已经确定的结果为 res，下一个要尝试的位是 bit，那么候选值是 res + bit。只需要检查 (res + bit)^2 是否小于等于 n，如果成立，就把这个 bit 累加进 res；无论成立与否，bit 都要右移一位，继续尝试更低的位。
初始 bit 怎么选？我一般取1 << ((n.bit_length() - 1) // 2)，这个式子保证 bit 是从高到低第一个可能对结果产生贡献的二进制位，而且不会超过 sqrt(n)。比如 n = 17，bit_length 是 5，bit = 1 << 2 = 4，直接尝试 (0 + 4)^2 = 16 <= 17，所以 res 至少是 4；接着 bit 变成 2、1，分别尝试 6^2 和 5^2，最后停在 res = 4。
def is_perfect_square(n: int) -> bool: if n < 0: return False if n < 2: return True res = 0 bit = 1 << ((n.bit_length() - 1) // 2) while bit: if (res + bit) * (res + bit) <= n: res += bit bit >>= 1 return res * res == n这个版本在 Python 里运行，因为 int 没有溢出，直接算平方也没问题。但在 C 语言里，同样建议把(res + bit) * (res + bit) <= n改写成除法比较：(res + bit) <= n / (res + bit)，避免乘法溢出。这里有符号无符号都能用，只是要保证 n 不为负。
5.2 为什么逐位构造比二分更优雅
二分查找维护的是一个连续的搜索区间，每次把区间折半，最后得到的是“第一个满足 x^2 >= n 的位置”。逐位构造则更像是在“组装”答案本身：直接确定平方根的每一位是 0 还是 1，跳过了对明显不可能的高位的试探。
两者的时间复杂度都是 O(log n)，都需要大约 log n 次迭代，但逐位构造有几个独特的优势：状态少，不需要维护 left 和 right 两个指针；思路直观，和手工开方的直觉完全一致；天然适合大整数，因为每一轮只做一次平方和除法判断，不会产生任何中间大数溢出的问题。缺点是，对没接触过的人来说，第一次看这个代码会觉得“为什么这样就能算出平方根”，需要一点时间去理解逐位试探的本质。
另外值得指出的是，按位构造本质上也是一种“二进制化的二分”，只是它的搜索空间被固定成了二进制的位权，而不是连续区间。理解了这一点，面试时你就可以很自然地从二分讲到逐位构造，显示出你对两种方法内在联系的理解深度。
5.3 大整数场景实测印象
我之前在 Python 里跑过一个 10^100 量级的大整数，用逐位构造法做完全平方数判断，耗时还是毫秒级。因为 10^100 的二进制长度大约是 333 位，逐位构造只需要大约 166 次循环就能收敛。换成奇数求和法，哪怕宇宙毁灭也算不完；换成浮点牛顿，double 精度连这个数本身都表示不出来，更不用提开方了。
所以在“超大整数”这个场景下，真正可靠的选择就是二分查找、整数牛顿、按位构造这三者。如果你是做密码学、大数运算相关开发的，这几个方法应该成为条件反射级别的技能。
6. 方法对比与实战避坑指南
6.1 五种方案横向对比
我整理了一张对比表，面试前建议反复看几遍：
| 方案 | 时间复杂度 | 空间 | 浮点依赖 | 溢出风险 | 大整数表现 | 实现复杂度 |
|---|---|---|---|---|---|---|
| 二分查找 | O(log n) | O(1) | 无 | 可用除法规避 | 优秀 | 低 |
| 浮点牛顿 | 对数级收敛 | O(1) | 有 | 有风险 | 差，精度不足 | 低 |
| 整数牛顿 | 对数级收敛 | O(1) | 无 | 可控制 | 优秀 | 中 |
| 奇数求和 | O(sqrt n) | O(1) | 无 | 无 | 差 | 极低 |
| 按位构造 | O(log n) | O(1) | 无 | 可用除法规避 | 优秀 | 中 |
如果让我给一句总结，那就是：面试首选二分，因为它最通用、最容易讲清楚、边界也最好控制；如果面试官追问数值解法，就把整数牛顿抛出来；如果希望展示知识面，把奇数求和和按位构造的数学原理讲透会非常加分。
6.2 面试官常问的三个后续问题
面试官不会只满足于你写出代码，一定会追加几个问题来区分你是背答案还是真懂。我遇到频率最高的几个：
第一个是“Math.sqrt 本身有什么不好”。这个问题千万不能只答“面试不让用”，而要主动指出浮点开方的精度问题。Math.sqrt返回的是浮点数，当 n 是超大整数时，开方结果本身就可能带有微小的舍入误差。经典的错误场景是：某些语言里 sqrt(25) 的结果可能是 4.9999999999 而不是 5，如果直接取整 int(x)，就会得到 4，导致4*4 == 25判断为 false，把一个完全平方数误判成非完全平方数。所以即使用 Math.sqrt，也应该Math.round之后再判断，而不是直接Math.floor或Math.trunc。
第二个是“输入是负数、0、1 怎么办”。这个问题没有任何算法难度，纯粹考察边界意识。负数直接 false，0 和 1 直接 true。如果一个人的代码连 n < 0 都不处理，说明他平时写代码边界意识比较薄弱，这在面试里是很减分的。
第三个是“n 如果特别大，比如 10^18 甚至更大，怎么办”。这是把问题从“能不能算”提升到“能不能在大范围算”。需要立刻反应出：奇数求和会退化到十亿次循环，浮点牛顿精度不足，而二分、整数牛顿、按位构造可以继续工作。如果环境是 JS，还要主动提出用 BigInt；如果是 C/C++，要讨论 __int128 或者输入范围限制。
6.3 实际项目里我选型的真实经验
说实话，业务开发里“完全平方数判断”真的不常用。真用到的时候，我的决策路径是这样的：如果 n 在 64 位整数范围内，团队水平参差，我直接写二分查找，因为它最好维护，任何懂二分的人都能一眼看懂。如果 n 可能是大整数，比如密码学或算法竞赛场景，我用整数牛顿或按位构造，这两者对我来说更像是“在整数域里自己实现一个 isqrt 函数”。如果只是偶尔在脚本里判断几个 int 数字，我甚至不介意用 Math.sqrt 配合 Math.round，因为在 64 位 int 范围内浮点误差几乎不会翻车，没必要为了纯粹而纯粹。
另外，在 C 语言里处理无符号和有符号混合比较时，要特别小心隐式转换。举个例子：int 类型的 -1 和无符号整数直接比较，-1 会被转换成巨大的无符号数，导致比较结果完全错误。所以无论用哪种方法，第一步把负数独立出来处理掉，永远是性价比最高的防御性编程。
最后分享一个我自己的习惯：写二分之前，先在心里把所有边界 case 过一遍，n=0、n=1、n=2、n=INT_MAX、n=46340^2，这几个值全部手算一遍，再开始写代码。这个习惯帮我省过无数次调试时间，也让我在面试里从来没被边界条件卡住过。
我个人实际操作中还有一个感触：这类“不用内置函数”的题目，真的值得反复练习。它逼着我把一行 API 拆成最底层的运算，去理解后面真正发生的数学过程。我最大的收获不是记住了多少种解法，而是养成了几个小习惯：写循环之前先想清楚上界、下界和退出条件；遇到乘法先想溢出；遇到浮点先想精度。这几个习惯，比多背一种算法值钱得多。如果你也被面试官追着问过溢出问题，欢迎在评论区聊聊你是怎么答的——我当年就是没答好溢出，回家之后把二分法的各种写法整整练了一周。
