考虑到一般的比特长度（尽管我在这里使用了特定的类型），我试图设计如下的简单算法。最初需要对0,1,2或<0进行简单而明显的检查。以下是简单的，因为它不试图使用任何现有的数学函数。大多数运算符可以用逐位运算符替换。我还没有用任何基准数据进行测试。我既不是数学专家，也不是计算机算法设计专家，我很乐意看到你们指出这个问题。我知道那里有很多改进的机会。

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}  

“我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法。”

答案令人印象深刻，但我没有看到一个简单的检查：

检查长右边的第一个数字是否为集合的成员（0,1,4,5,6,9）。如果不是，那么它不可能是一个“完美的正方形”。

eg.

4567-不能是完美的正方形。

如果你做了一个二进制斩试图找到“正确”的平方根，你可以很容易地检测到你得到的值是否足够接近：

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

因此，在计算了n^2之后，选项如下：

n ^2=目标：已完成，返回truen^2+2n+1>target>n^2:你很接近，但并不完美：return falsen^2-2n+1<目标<n^2：同上目标<n^2-2n+1：低位n上的二进制斩波目标>n^2+2n+1：较高n上的二进制斩波

（抱歉，这使用n作为您当前的猜测，并将其作为参数的目标。对此感到困惑深表歉意！）

我不知道这是否会更快，但值得一试。

编辑：二进制斩不必接受整个整数范围，或者（2^x）^2=2^（2x），所以一旦你在目标中找到了最高位（这可以用一个小技巧来完成；我完全忘记了怎么做），你就可以快速得到一系列可能的答案。请注意，一个简单的二进制斩仍然只需要31或32次迭代。

我喜欢对一些输入使用几乎正确的方法。这是一个“偏移”更高的版本。代码似乎有效，并通过了我的简单测试用例。

只需替换您的：

if(n < 410881L){...}

使用此代码：

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

我在想我在数值分析课程中度过的可怕时光。

然后我记得，在Quake源代码中，有一个函数围绕着“网络”旋转：

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

它基本上使用牛顿近似函数（记不清确切的名字）计算平方根。

它应该是可用的，甚至可能更快，它来自一个非凡的id软件的游戏！

它是用C++编写的，但一旦你有了这样的想法，在Java中重用同样的技术应该不会太难：

我最初在以下位置找到它：http://www.codemaestro.com/reviews/9

牛顿的方法在维基百科上解释：http://en.wikipedia.org/wiki/Newton%27s_method

您可以通过链接了解更多的工作原理，但如果您不太在意，那么这大概是我在阅读博客和参加数值分析课程时所记得的：

*（long*）&y基本上是一个快速转换为long的函数，因此整数运算可以应用于原始字节。0x5f3759df-（i>>1）；line是近似函数的预先计算的种子值。*（float*）-i将值转换回浮点。y=y*（three-half-（x2*y*y））行基本上再次迭代函数上的值。

在结果上迭代函数的次数越多，逼近函数给出的值就越精确。在Quake的案例中，一次迭代“足够好”，但如果不是为了你。。。然后您可以添加所需的迭代次数。

这应该更快，因为它减少了在简单平方根中执行的除法运算的数量（实际上是一个*0.5F乘法运算），并用一些固定数量的乘法运算代替。

我希望此功能与所有正64位有符号整数

Math.sqrt（）使用double作为输入参数，因此对于大于2^53的整数，不会得到准确的结果。