首頁 >Java >java教程 >如何透過位元運算快速判斷一個大整數是否為完全平方數？

如何透過位元運算快速判斷一個大整數是否為完全平方數？

DDD原創: 2025-01-01 07:23:10908瀏覽

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的次方。在我的實際程式碼中，我使用了以下修改後的循環：
```
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

上一篇：Java 中的 Instant 與 LocalDateTime：什麼時候應該使用它們？下一篇：Java 中的 Instant 與 LocalDateTime：什麼時候應該使用它們？

看更多