我們如何有效地確定一個數字是否是2的力量？

判斷一個數是否為2的冪

問題描述

判斷給定數字是否為2的冪需要一個既簡單又準確的算法。作者提出了兩種算法，但在使用對數計算時遇到了舍入問題。

第一種算法

第一種算法IsPowerOfTwo 使用簡單的循環，通過位移來檢查2的冪：

<code class="language-c#">private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}</code>

此方法簡單易懂，對於任何ulong值都能完美運行。

第二種算法

第二種算法IsPowerOfTwo_2 依賴於對數計算：

<code class="language-c#">private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}</code>

然而，由於舍入問題，此算法無法正確處理值9223372036854775809。

改進後的算法

<code class="language-c#">bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}</code>

算法解釋

這種改進後的算法巧妙地利用了位運算：

• 位運算符& 檢查對應位置的兩個位是否都為1。
• 從數字中減去1會將所有1翻轉為0，將所有0翻轉為1。
• 如果數字是2的冪，則其二進製表示只會有一個1位。
• 當數字與(x - 1)進行位與運算時，除了最右邊的1位之外的所有位都將為0。
• 因此，如果結果為0，則該數字是2的冪。

排除零

<code class="language-c#">bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}</code>

為了排除零（零不被認為是2的冪），添加了附加條件(x != 0)。

以上是我們如何有效地確定一個數字是否是2的力量？的詳細內容。更多資訊請關注PHP中文網其他相關文章！