5

这个问题是这里帖子的后续:Fastest way to determine if an integer's square root is an integerWhat's a good algorithm to determine if an input is a perfect square? .

那里的一个帖子有这个解决方案来查找给定的数字是否为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;
        }
    } 

这是一个简洁的解决方案,并且工作得非常好。但没有解释它是如何工作的,更重要的是,没有详细解释这个解决方案是如何得出的。我想知道这个解决方案是如何得出的。

4

2 回答 2

3

虽然这个问题与直接编程无关,但它仍然与选择的解决方法有关。这就是为什么我会发布正确的解释。显然,这x & 0xF相当于x % 16- 即从除法到 16 的模(因为它会留下相应的位。但是,这个技巧只适用于 2 的幂)。

这种方法基于关于完美正方形的非常重要的事情:

如果整数除以模数(so )K的任何整数,则 K 2和 r 2除以将得到相同的模数。brK%b = rb

为什么?实际上,我们有: K 2 -r 2 = (Kr)(K+r) 并且K-r将被除以b整数结果(因为除以r是模数)Kb

这就是为什么b=16

rr^2 (r^2)%16
0 ----> 0 ---> 0
1 ----> 1 ---> 1
2 ----> 4 ---> 4
3 ----> 9 ---> 9
4 ---> 16 ---> 0
5 ---> 25 ---> 9
6 ---> 36 ---> 4
7 ---> 49 ---> 1
8 ---> 64 ---> 0
9 ---> 81 ---> 1
10 --> 100 ---> 4
11 --> 121 ---> 9
12 --> 144 ---> 0
13 --> 169 ---> 9
14 --> 196 ---> 4
15 --> 225 ---> 1

因此,如您所见,如果r是从完全平方除法导出的,则模必须与模相同r^2%16- 因此,它只能 0, 1,49

更重要的一件事:这是完全平方的必要条件,但条件不够(所以点是“如果模不是 0,1,4 或 9,那么数字不是完全平方”,但它仍然不等于“如果模IS 0,1,4 或 9 然后数字是完美平方”简单示例是1717%16 = 1但 17 不是完美平方)这就是为什么即使满足模条件,方法仍然使用

返回 tst*tst == n;

n- 即通过计算平方根来测试完美平方。所以这个方法大约会快 4 倍——因为从r12 的 16 个可能的模数中,我们总是可以返回false

于 2014-02-25T08:16:56.507 回答
2

n & 0xF只选择 n 的最后 4 位,因为0xF它是1111二进制的。实际上,它相当于得到 n 除以 16 时的余数。

该算法利用了这样一个事实,即对于一个完美的正方形mm % 16它只能是0、或1中的一个。可以证明如下:49

任何自然数n都可以表示为4k4k+14k+24k+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+416k^2+24k+9

如果n^216k^2n^2 % 16显然是 0。

如果n^216k^2+8k+1, n^2 % 16 = (8k+1) % 16 = (8k % 16) + 1 = 0 or 9, 取决于k是偶数还是奇数。

如果n^216k^2+16k+4, n^2 % 16 = 4.

如果n^216k^2+24k+9n^2 % 16 = (24k+9) % 16 = (16k+8k+9) % 16 = 1 or 9取决于 k 是奇数还是偶数。

因此,n^2 % 16只能是0,1, 4 or 9

于 2014-02-25T08:11:35.003 回答