这个问题是这里帖子的后续：确定整数是否为'；s的平方根是一个整数，What'；这是一个很好的算法来确定一个输入是否是一个完美的正方形？。
其中一个帖子有这样的解决方案，可以确定给定的数字是否是perfect square：
public final static boolean isPerfectSquare(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;
}
}
这是一个巧妙的解决方案，效果非常好。但没有详细解释它是如何工作的，更重要的是，没有解释这个解决方案是如何导出的。我想知道这个解决方案是如何得出的。
虽然这个问题不是直接关于编程的，但它仍然与所选的解决方法有关。这就是为什么我会发布正确的解释。显然，x & 0xF与x % 16等价，即从除法到16取模(因为它会留下相应的位。然而，这个技巧只适用于2的幂)。
这种方法是基于关于完美平方的非常重要的东西：
如果整数K除以任何具有模r的整数b(因此K%b = r)，则K2和r<2>除以b将得到相同的模
为什么？事实上，我们有：K2-r2=(K-r)(K+r)和K-r将被划分为b，结果为整数(因为r是K划分为b的模)
这就是为什么b=16:
r^2(r^2)%160---->0---->01---->1--->12---->4---->43---->9---->94---->16---->05-->25-->96---->36---->47-->49--->18-->64-->09--->81--->110-->100--->411-->121--->912-->144--->013-->169--->914-->196--->415-->225--->1
所以，正如你所看到的，如果r是由完美平方的除法导出的，那么模必须与r^2%16的模相同-因此，它只能是0、1、4和9
更重要的一点是：这是完美平方的必要条件，而不是足够的条件(所以点是"如果模不是0,1,4或9，则数字不是完美平方">，但它仍然不等于"如果模是0,1,4，则数字是完美平方">简单的例子是17:17%16 = 1，但17不是完美平方)这就是为什么在满足模条件的情况下，该方法仍然使用
返回tst*tst==n；
即通过计算n的平方根来测试它是完美平方。因此，这种方法大约快4倍，因为从16个可能的模r到12，我们总是可以返回false。
n & 0xF只选取n的最后4位，因为0xF是二进制的1111。实际上，这相当于当n除以16时得到余数。
该算法利用了对于完全正方形m，m % 16只能是0、1、4或9中的一个的事实。可以证明如下：
任何自然数n都可以表示为4k、4k+1、4k+2或4k+3(对于某些自然数k)。
那么，n^2可以是(4k)^2、(4k+1)^2、(4k+2)^2或(4k+3)^2。=>n^2可以是16k^2、16k^2+8k+1、16k^2+16k+4或16k^2+24k+9。
如果n^2是16k^2，则n^2 % 16显然是0。
如果n^2是16k^2+8k+1，则n^2 % 16 = (8k+1) % 16 = (8k % 16) + 1 = 0 or 9，这取决于k是偶数还是奇数。
如果n^2是16k^2+16k+4、n^2 % 16 = 4。
如果n^2是16k^2+24k+9，则n^2 % 16 = (24k+9) % 16 = (16k+8k+9) % 16 = 1 or 9取决于k是奇数还是偶数。
因此，n^2 % 16只能是0,1, 4 or 9。