用sqrt函数加精度校验是最常用方法:先调用sqrt得浮点结果,再用llround取整并平方回检root*root==n,避免截断与浮点误差。

用 sqrt 函数加精度校验是最常用方法
直接调用 sqrt 算出浮点结果,再四舍五入取整、平方回检,是多数人第一反应。但要注意浮点误差:比如对大整数 9999999999999999,sqrt 返回值可能略小于真实根,round 后变小,导致误判。
实操建议:
- 用
llround(sqrt(n))(而非(long long)sqrt(n))避免截断误差 - 校验时用
root * root == n,而不是比较浮点差值 - 对
n 提前返回 <code>false,sqrt对负数返回NaN - 若
n是long long类型,需用sqrtl防止double精度不足(double仅精确表示约 2⁵³ 内整数)
整数二分法适合无浮点支持或超大整数场景
当不能用 sqrt(如嵌入式环境)、或 n 超出 double 表示范围(如 __int128),整数二分更可靠。时间复杂度 O(log n),但常数小,实际不慢。
关键细节:
- 左边界设为
0,右边界设为n或更优的min(n, (1LL (因平方根不会超过 <code>n的一半量级) - 判断条件用
mid 避免 <code>mid * mid溢出(尤其mid接近sqrt(LLONG_MAX)时) - 循环结束时检查
left * left == n即可,不用额外存mid
std::sqrt 在 float/double/long double 上的行为差异
类型选错会悄悄引入错误。例如对 uint64_t n = 18446744073709551615ULL(2⁶⁴−1):
-
sqrt((double)n)→ 返回4294967296.0(正确),但这是巧合;更大的数就会失真 -
sqrtf((float)n)→ 直接溢出为+inf,llround得到极大值,校验必败 -
sqrtl((long double)n)在 x86-64 GCC 下通常是 80-bit 扩展精度,能撑到约 2⁶⁴,但跨平台不可靠
结论:除非明确知道输入范围且足够小,否则别用 float;double 安全上限约 2⁵³;超此范围必须用整数方法。
位运算预筛选能快速排除 75% 的非完全平方数
完全平方数模 16 只能是 0,1,4,9;模 64 更精细(仅 12 个余数合法)。先做一次位运算取模,能立刻拒绝大部分数,再进主逻辑。
高效写法:
if ((n & 15) != 0 && (n & 15) != 1 && (n & 15) != 4 && (n & 15) != 9) return false;- 用
n & 63替代n % 64,编译器通常自动优化,但显式写更清晰 - 注意:负数要先处理,
n & 15对负的有符号整数是实现定义行为,应确保n >= 0 - 这个过滤对随机数据效果显著,但对已知接近平方数的输入(如测试边界值)几乎无效
真正难的是平衡可读性、跨平台性和边界覆盖——比如 sqrtl 在 Windows MSVC 上不支持 long double 精度提升,而整数二分又得小心除零和溢出。实际项目里,先用位筛 + sqrtl + 校验,跑不通再切二分,比一开始就写通用模板更省事。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











