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

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

1. 过滤明显答案：包括负数、检查最后4位（发现检查最后6位并无帮助）、回答0。（在阅读以下代码时，请注意我的输入是int64 x。）

   if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if( x == 0 )
       return true;

2. 检查是否为模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

3. 使用类似于亨瑟尔引理的方法尝试计算平方根：在此之前，我使用二分搜索将所有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中文网其他相关文章！