为了表现，你经常不得不做一些宣传。其他人表达了不同的方法，然而，你注意到卡马克的黑客在达到N的某些值时更快。然后，你应该检查“N”，如果它小于N，请使用卡马克的方法，否则使用此处答案中描述的其他方法。

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

(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次迭代。

我不确定它是否会更快，甚至更准确，但你可以使用约翰·卡马克的神奇平方根算法来更快地解平方根。您可能很容易对所有可能的32位整数进行测试，并验证您实际上得到了正确的结果，因为这只是一个近似值。然而，现在我想起来，使用双打也是近似的，所以我不确定这会如何发挥作用。

这是旧的Marchant计算器算法（抱歉，我没有参考）从十进制到二进制的修改，在Ruby中，专门针对这个问题进行了修改：

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

这里有一个类似的处理方法（可能有编码风格/气味或笨拙的O/O——重要的是算法，C++不是我的母语）。在这种情况下，我们要查找残数==0：

#include <iostream>  

using namespace std;  
typedef unsigned long long int llint;

class ISqrt {           // Integer Square Root
    llint value;        // Integer whose square root is required
    llint root;         // Result: floor(sqrt(value))
    llint residue;      // Result: value-root*root
    llint onebit, x;    // Working bit, working value

public:

    ISqrt(llint v = 2) {    // Constructor
        Root(v);            // Take the root 
    };

    llint Root(llint r) {   // Resets and calculates new square root
        value = r;          // Store input
        residue = value;    // Initialise for subtracting down
        root = 0;           // Clear root accumulator
        
        onebit = 1;                 // Calculate start value of counter
        onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
        while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value
        
        while (onebit > 0) {
            x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
            if (residue >= x) {         // Room to subtract?
                residue -= x;           // Yes - deduct from residue
                root = x + onebit;      // and step root
            };
            root >>= 1;
            onebit >>= 2;
        };
        return root;                    
    };
    llint Residue() {           // Returns residue from last calculation
        return residue;                 
    };
};

int main() {
    llint big, i, q, r, v, delta;
    big = 0; big = (big-1);         // Kludge for "big number"
    ISqrt b;                            // Make q sqrt generator
    for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
        q = b.Root(i);                  // Get the square root
        r = b.Residue();                // Get the residue
        v = q*q+r;                      // Recalc original value
        delta = v-i;                    // And diff, hopefully 0
        cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
    };
    return 0;
};

maartinus解决方案的以下简化似乎使运行时减少了几个百分点，但我在基准测试方面做得不够好，无法产生我可以信任的基准：

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

值得检查的是，如何省略第一次测试，

if (goodMask << x >= 0) return false;

会影响性能。

一个数字的平方根，假设该数字是一个完全平方。

复杂性为log（n）

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}