亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

如何檢查一個數字是否為2的冪

如何檢查一個數字是否為2的冪

慕碼人8056858 2019-06-25 15:56:13
如何檢查一個數字是否為2的冪今天,我需要一個簡單的算法來檢查一個數字是否是2的冪。算法需要:簡約對任何ulong價值。我想出了一個簡單的算法:private bool IsPowerOfTwo(ulong number){     if (number == 0)         return false;     for (ulong power = 1; power > 0; power = power << 1)     {         // This for loop used shifting for powers of 2, meaning         // that the value will become 0 after the last shift         // (from binary 1000...0000 to 0000...0000) then, the 'for'         // loop will break out.         if (power == number)             return true;         if (power > number)             return false;     }     return false;}但后來我想,檢查一下log2 x是正整數嗎?但當我檢查2^63+1時,Math.Log因為四舍五入返回了63。因此,我檢查了冪63的2是否等于原來的數字-是的,因為計算是在doubles而不是確切的數字:private bool IsPowerOfTwo_2(ulong number){     double log = Math.Log(number, 2);     double pow = Math.Pow(2, Math.Round(log));     return pow == number;}這個回來了true對于給定的錯誤值:9223372036854775809.有更好的算法嗎?
查看完整描述

3 回答

?
墨色風雨

TA貢獻1853條經驗 獲得超6個贊

要解決這個問題,有一個簡單的技巧:

bool IsPowerOfTwo(ulong x){
    return (x & (x - 1)) == 0;}

注意,此功能將報告true0,這不是2..如果您想排除這一點,下面是如何:

bool IsPowerOfTwo(ulong x){
    return (x != 0) && ((x & (x - 1)) == 0);}

解釋

首先也是最重要的,是MSDN定義中的按位二進制&操作符:

二進制&運算符是為積分類型和bool預定義的。對于整型,計算邏輯位數及其操作數。對于bool操作數,&計算邏輯和它的操作數;也就是說,結果是真的當且僅當它的兩個操作數都是真的。

現在讓我們來看看這一切是如何發生的:

函數返回布爾值(true/false),并接受一個輸入參數(在本例中為x)。為了簡單起見,讓我們假設有人傳遞了值4并調用了函數,如下所示:

bool b = IsPowerOfTwo(4)

現在,我們將x的每次出現替換為4:

return (4 != 0) && ((4 & (4-1)) == 0);

我們已經知道4!=0為真,到目前為止還不錯。但是關于:

((4 & (4-1)) == 0)

當然,這意味著:

((4 & 3) == 0)

但究竟什么是4&3?

4的二進制表示為100,3的二進制表示為011(記住&接受這些數字的二進制表示)。所以我們有:

100 = 4011 = 3

假設這些值被堆疊起來,就像基本加法一樣。這個&運算符表示,如果兩個值都等于1,則結果為1,否則為0。所以1 & 1 = 11 & 0 = 00 & 0 = 0,和0 & 1 = 0..所以我們計算一下:

100011----000

結果就是0。因此,我們回頭看看返回語句現在轉換為:

return (4 != 0) && ((4 & 3) == 0);

現在翻譯為:

return true && (0 == 0);
return true && true;

我們都知道true && true是簡單的true,這表明,在我們的例子中,4是2的冪。


查看完整回答
反對 回復 2019-06-25
  • 3 回答
  • 0 關注
  • 836 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號