首页 >Java >java教程 >如何通过按位运算快速判断一个大整数是否是完全平方数？

如何通过按位运算快速判断一个大整数是否是完全平方数？

DDD原创: 2025-01-01 07:23:10922浏览

How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

尽管算法速度比你给出的代码快35%左右，但不同CPU（x86）和编程语言（C/C ）的实际结果可能有所不同。本文的方法分为三个部分：

过滤明显答案：包括负数、检查最后4位（发现检查最后6位并无帮助）、回答0。（在阅读以下代码时，请注意我的输入是int64 x。）
```
if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
    return false;
if( x == 0 )
    return true;
```
检查是否为模255平方数：因为255是三个不同质数的乘积，所以模255的平方只有大约1/8的余数。然而，就我经验而言，使用模运算符（％）的代价高于收益，因此我使用了涉及255的位技巧来计算余数。（好坏参半，我没有使用从字中读取单个字节的技巧，只使用按位与和移位。）
```
int64 y = x;
y = (y & 4294967295LL) + (y >> 32); 
y = (y & 65535) + (y >> 16);
y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
// At this point, y is between 0 and 511.  More code can reduce it farther.
```
我用预先计算的表来实际检查余数是否为平方数。
```
if( bad255[y] )
    return false;
// However, I just use a table of size 512
```
使用类似于亨瑟尔引理的方法尝试计算平方根：在此之前，我使用二分搜索将所有2的次幂的余数除尽：
```
if((x & 4294967295LL) == 0)
    x >>= 32;
if((x & 65535) == 0)
    x >>= 16;
if((x & 255) == 0)
    x >>= 8;
if((x & 15) == 0)
    x >>= 4;
if((x & 3) == 0)
    x >>= 2;
```
在这一点上，我们的数要成为平方数，它的模必须是8的1。
```
if((x & 7) != 1)
    return false;
```
亨瑟尔引理的基本结构如下。（注意：未经测试的代码；如果不工作，请尝试t=2或8。）
```
int64 t = 4, r = 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
// Repeat until t is 2^33 or so.  Use a loop if you want.
```
思想是，在每次迭代中，你都将一位添加到r，“当前”的x平方根；每个平方根都模一个越来越大的2的次幂，即t/2。（注意，如果r是x的平方根，那么-r也是。这在模数的情况下也是成立的，但要注意，模某些数，事情甚至可以有超过2个平方根；特别是，这包括2的次幂。）因为我们的实际平方根小于2^32，所以在那一点上我们实际上可以检查r或t/2-r是否为x的实际平方根。在我的实际代码中，我使用了以下修改后的循环：
```
int64 r, t, z;
r = start[(x >> 3) & 1023];
do {
    z = x - r * r;
    if( z == 0 )
        return true;
    if( z < 0 )
        return false;
    t = z & (-z);
    r += (z & t) >> 1;
    if( r > (t >> 1) )
        r = t - r;
} while( t <= (1LL << 33) );
```
这里的速度提升可以通过三种方式获得：预先计算的起始值（相当于大约10次循环迭代）、更早地退出循环以及跳过一些t值。对于最后一部分，我观察z=r-x*x，并使用位技巧设置t为除以z的最大2的次幂。这允许我跳过那些无论如何都不会影响r值的t值。我的预先计算起始值在我的情况下选出了模8192的“最小正”平方根。

即使本代码不会更快地为您工作，我希望您也能享受其中的一些想法。完整测试代码如下，包括预计算表。

typedef signed long long int int64;

int start[1024] =
{1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,

以上是如何通过按位运算快速判断一个大整数是否是完全平方数？的详细内容。更多信息请关注PHP中文网其他相关文章！

Integer 运算符 if 循环 using 算法

声明：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：Instant vs. LocalDateTime in Java: When Should I Use Each?下一篇：How Can Selenium 4 Simplify Interaction with Shadow DOM Elements?

查看更多