使用位移查找整數平方根的最快方法是什麼？

Question

我正在尋找最快的方法來計算一個數字（整數）的平方根（整數）。

short isqrt(short num) { 
    short res = 0; 
    short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long 
    // "bit" starts at the highest power of four <= the argument. 
    while (bit > num) 
     bit >>= 2; 
    while (bit != 0) { 
     if (num >= res + bit) { 
      num -= res + bit; 
      res = (res >> 1) + bit; 
     } 
     else 
      res >>= 1; 
     bit >>= 2; 
    } 
    return res; 
} 

：我碰到這個解決方案在維基百科指找到一個數的平方根（如果它是一個完美的正方形），或者其最接近的較低完全平方的平方根（如果給定的數字是不是一個完美的方形來我試了很多測試運行來跟蹤算法，但我似乎並不瞭解while(bit!=0)內部的部分。有人可以向我解釋這部分嗎？

Answer 1

我也列出了一些小例子，我想我知道了按照我的理解，該算法一次構建一個二進制數字的答案，從最高位到最低位。

設「num_init」爲函數開頭處的num值。假設在某個迭代中，我們有那個位= 4^x，並且這個num等於某個值「num_curr」（快速瀏覽顯示，直到位爲0時，它總是4的冪）。然後res的形式爲y * 2 ^（x + 1），其中y^2 + num_curr = num_init，並且y小於實際答案，但是在2^x之內。

num，res和bit的這個不變量將是關鍵。這是在代碼實現的方式是，

while (bit != 0) { 
    .... 
} 

是移動左至右我們想象的指針，並在每個步驟中，我們確定該位是0或1

將第一if語句，假設我們想象的「內建」整數等於y，我們正在查看2^x位。那麼，如果num的原始值至少爲（y + 2^x）^ 2 = y^2 + y * 2 ^（x + 1）+ 4^x，則該位爲1。換句話說，如果該點處的num值至少是y * 2 ^（x + 1）+ 4^x（因爲我們有num的值已經下降y^2的不變量），那麼該位是1。 。方便地，res = y * 2 ^（x + 1）和位= 4^x。然後，我們明白了背後

if (num >= res + bit) { 
    num -= res + bit; 
    res = (res >> 1) + bit; 
} 
else 
    res >>= 1; 

這在我們的假想點增加了1位，如果有必要，則更新資源和num保持不變。最後

bit >>= 2; 

更新位並將所有內容一步一步移動。