如何检查一个数的平方根是否为整数：Java中的5种方法

引言：一个让Stack Overflow爆炸的问题

想象一下：你正在编写每秒处理数千个数字的代码。你需要筛选出那些平方根为整数的数字（1, 4, 9, 16…）。看起来很简单？用Math.sqrt()检查余数就行了。但事情没那么简单。

Stack Overflow上的问题「判断一个整数的平方根是否为整数的最快方法」已经获得了超过10万次浏览。为什么？因为Math.sqrt()是一个浮点运算，速度慢且容易受到舍入误差的影响。对于大数字（例如2^50），double可能会「撒谎」。

在本文中，我们将探讨Java中的5种方法：从最朴素的方法到使用位运算和整数算术的快速算法。您将了解哪种方法实际上更快，哪种更安全。开始吧！

问题陈述

我们需要编写一个方法boolean isPerfectSquare(long n)，如果n是完全平方数，则返回true。示例：

\n
• isPerfectSquare(25) → true (5*5)
\n
• isPerfectSquare(26) → false
\n
• isPerfectSquare(0) → true (0*0)
\n
• isPerfectSquare(1) → true
\n

我们将使用long进行测试，因为int只是一个特例，而long提供了更大的出错空间。

方法1：朴素方法——Math.sqrt + 余数检查

新手最容易想到的最简单方法：

public static boolean isPerfectSquareSqrt(long n) {\n    if (n < 0) return false;\n    double sqrt = Math.sqrt(n);\n    long floorSqrt = (long) sqrt;\n    return floorSqrt * floorSqrt == n;\n}\n

问题1：精度。对于大于约2^53（9 007 199 254 740 991）的数字，double无法精确表示整数。例如：n = 999999999999999999L——Math.sqrt会返回错误结果。

问题2：速度。Math.sqrt是一条CPU指令（FSQRT），但仍然比简单的算术运算慢。

何时使用：仅适用于int或较小的long（< 10^12），且对速度要求不高的情况。

方法2：通过牛顿-拉夫逊法计算整数平方根

牛顿-拉夫逊法（Newton-Raphson）是一种无需浮点数的经典平方根计算方法。通过迭代逐步逼近：

public static boolean isPerfectSquareNewton(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long x = n;\n    long y = (x + 1) / 2;\n    while (y < x) {\n        x = y;\n        y = (y + n / y) / 2;\n    }\n    return x * x == n;\n}\n

该算法收敛速度非常快——只需O(log log n)次迭代。对于Long.MAX_VALUE以内的数字，仅需6-8次迭代。

优点：对所有long（最大2^63-1）绝对精确。不使用double。

缺点：除法是一种昂贵的操作。对于非常小的数字（n < 4），可以在开头添加检查。

方法3：二分查找平方根

另一种经典算法——在区间[0, n]上通过二分查找寻找平方根。对于long，平方根的最大值为3 037 000 499（sqrt(Long.MAX_VALUE)）。

public static boolean isPerfectSquareBinary(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long low = 1;\n    long high = 3037000499L; // sqrt(Long.MAX_VALUE)\n    while (low <= high) {\n        long mid = (low + high) >>> 1;\n        long square = mid * mid;\n        if (square == n) return true;\n        else if (square < n) low = mid + 1;\n        e