判断整数是否为完全平方数的几种方法

1. 概述

✅ 完全平方数（Perfect Square）是指一个整数可以表示为另一个整数与自身相乘的结果。

本文将介绍在 Java 中判断一个整数是否为完全平方数的多种方法，并分析每种方法的优缺点，帮助你选择最合适的实现方式。

2. 判断整数是否为完全平方数

Java 提供了两种基本整数类型：int（32位）和 long（64位）。由于我们要处理的整数可能非常大，因此我们使用 long 类型来处理最坏情况。

Java 中 long 的取值范围是：

-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807

由于我们只关心正整数（负数不可能是完全平方数），所以只需要考虑正整数范围。又因为最大值约为 2^63，所以平方根小于 2^31.5 的整数大约有 2^31.5 个。如果为这些数建立查找表，显然不现实。

2.1. 使用 `Math.sqrt()` 方法

✅ 最简单直接的方式就是使用 Math.sqrt() 方法。

该方法返回一个 double 类型值，我们需要将其转换为整数并验证其平方是否等于原数：

public static boolean isPerfectSquareByUsingSqrt(long n) {
    if (n <= 0) {
        return false;
    }
    double squareRoot = Math.sqrt(n);
    long tst = (long)(squareRoot + 0.5);
    return tst * tst == n;
}

⚠️ 注意：由于浮点数精度问题，有时需要加 0.5 再进行强制类型转换，以避免因精度误差导致判断错误。

例如：3 被表示为 3.00000001 或 2.99999999，通过 +0.5 后再转为 long 可以更准确地还原整数部分。

虽然单次调用很快，但如果需要频繁调用，这种微优化也能带来一定性能提升。

2.2. 使用二分查找法

✅ 我们也可以不依赖 Math.sqrt()，使用二分查找手动寻找平方根。

由于 long 类型的取值范围大约在 1 到 2^31.5 之间，所以最多只需要约 16 次二分查找即可找到平方根：

public boolean isPerfectSquareByUsingBinarySearch(long low, long high, long number) {
    long check = (low + high) / 2L;
    if (high < low) {
        return false;
    }
    if (number == check * check) {
        return true;
    } else if (number < check * check) {
        high = check - 1L;
        return isPerfectSquareByUsingBinarySearch(low, high, number);
    } else {
        low = check + 1L;
        return isPerfectSquareByUsingBinarySearch(low, high, number);
    }
}

2.3. 优化的二分查找

我们可以进一步优化二分查找的搜索范围。根据原数的位数，我们可以预估平方根的范围。

例如：

一位数（如 9）的平方根范围为 1~4
两位数（如 99）的平方根范围为 4~10

✅ 我们可以通过构建一个查找表，根据原数的位数快速定位平方根的大致范围，从而减少二分查找的迭代次数：

public class BinarySearchRange {
    private long low;
    private long high;

    // standard constructor and getters
}

private void initiateOptimizedBinarySearchLookupTable() {
    lookupTable.add(new BinarySearchRange());
    lookupTable.add(new BinarySearchRange(1L, 4L));
    lookupTable.add(new BinarySearchRange(3L, 10L));
    for (int i = 3; i < 20; i++) {
        lookupTable.add(
          new BinarySearchRange(
            lookupTable.get(i - 2).low * 10,
            lookupTable.get(i - 2).high * 10));
    }
}

public boolean isPerfectSquareByUsingOptimizedBinarySearch(long number) {
    int numberOfDigits = Long.toString(number).length();
    return isPerfectSquareByUsingBinarySearch(
      lookupTable.get(numberOfDigits).low,
      lookupTable.get(numberOfDigits).high,
      number);
}

2.4. 使用牛顿法（整数运算）

✅ 牛顿法（Newton's Method）是一种通用的数值逼近方法，也可用于求平方根。

其基本思想是：假设 X 是 N 的平方根，通过不断迭代逼近真实值。

我们可以稍作修改，使其适用于判断一个整数是否为完全平方数：

public static boolean isPerfectSquareByUsingNewtonMethod(long n) {
    long x1 = n;
    long x2 = 1L;
    while (x1 > x2) {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }
    return x1 == x2 && n % x1 == 0L;
}

⚠️ 注意：此方法通过整数除法避免浮点运算，效率较高。

3. 完全平方数判断算法的优化技巧

在实际应用中，我们可以通过一些“预判”技巧来优化算法性能。

✅ 一个重要的事实是：在十六进制中，完全平方数的末位只能是 0、1、4 或 9。

我们可以利用这一特性，先判断数字的末位是否符合要求，再决定是否继续计算平方根：

public static boolean isPerfectSquareWithOptimization(long n) {
    if (n < 0) {
        return false;
    }
    switch((int)(n & 0xF)) {
        case 0: case 1: case 4: case 9:
            long tst = (long)Math.sqrt(n);
            return tst * tst == n;
        default:
            return false;
    }
}

✅ 这种方式可以快速排除大量不可能为完全平方数的情况，从而提高整体性能。

4. 总结

本文介绍了几种判断整数是否为完全平方数的方法：

使用 Math.sqrt()：简单直接，适合一般场景
二分查找：不依赖浮点运算，适合需要精确控制的场景
牛顿法：高效逼近，适合性能敏感场景
预判优化：通过末位判断快速排除，适合批量处理

✅ 总体来看，合理使用预判技巧可以大幅提升算法效率，避免不必要的计算。

📌 本文代码可在 GitHub 获取。

Persistence

REST

Security