上周有个朋友来问我说面试时遇到一道题“判断一个整数是不是完全平方数但不准用 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^2O(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 超过 46340mid*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 longn / mid 一定不会溢出mid n / mid 就等价于 mid*mid n但不会产生乘法溢出。这是所有需要手写二分平方根的 C/C 代码里我最推荐的一种写法。2.3 边界条件与整数溢出这里最容易阴沟翻船边界条件这块我整理了一份速查表面试前最好默写一遍输入结果原因n 0True0 0^2n 1True1 1^2n 0False负数没有实数平方根n 2False2 介于 1^2 和 2^2 之间n 2147483647FalseINT_MAXsqrt 约 46340不是完全平方数n 2147395600True46340^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_{k1} 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 为例x017x1(17 1)/29x2(9 17/9)/2≈5.444x3≈4.318x4≈4.128x5≈4.1231056256到这里其实已经非常接近 sqrt(17)≈4.12310562561766 了。也就是说从初值 n 出发通常五六次迭代就能达到 double 的精度。3.2 整数场景下终止条件怎么定才稳如果直接写浮点牛顿跳出条件一般是 |x_k^2 - n| eps但 eps 选多少很麻烦选大了可能把非完全平方数误判成完全平方数选小了又可能因为浮点误差永远不满足条件而死循环。所以我的建议是不要依赖浮点 eps改用整数版本。整数牛顿的精髓是把迭代公式里的浮点除法全部换成整数除法x_{k1} (x_k n // x_k) // 2这个序列在非负整数域里单调下降最终会落在 floor(sqrt(n)) 上。终止条件不是“误差小于多少”而是当 x_{k1} 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^21 3 4 2^21 3 5 9 3^2…… 所以判断 n 是不是完全平方数可以不断从 n 中减去 1、3、5、7……如果最后余数刚好为 0说明 n 是某个数的平方减法执行了几次平方根就是几。举个例子来演算。n 99 - 1 88 - 3 55 - 5 0一共减了 3 次所以 9 是 3^2。再看 n 1010 - 1 99 - 3 66 - 5 11 - 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 17bit_length 是 5bit 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 怎么办”。这个问题没有任何算法难度纯粹考察边界意识。负数直接 false0 和 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 过一遍n0、n1、n2、nINT_MAX、n46340^2这几个值全部手算一遍再开始写代码。这个习惯帮我省过无数次调试时间也让我在面试里从来没被边界条件卡住过。我个人实际操作中还有一个感触这类“不用内置函数”的题目真的值得反复练习。它逼着我把一行 API 拆成最底层的运算去理解后面真正发生的数学过程。我最大的收获不是记住了多少种解法而是养成了几个小习惯写循环之前先想清楚上界、下界和退出条件遇到乘法先想溢出遇到浮点先想精度。这几个习惯比多背一种算法值钱得多。如果你也被面试官追着问过溢出问题欢迎在评论区聊聊你是怎么答的——我当年就是没答好溢出回家之后把二分法的各种写法整整练了一周。