位掩碼：如何確定是否只有一個位被設置

如果我有一個基本的掩碼...位掩碼：如何確定是否只有一個位被設置

cat = 0x1; 
dog = 0x2; 
chicken = 0x4; 
cow = 0x8; 

// OMD has a chicken and a cow 
onTheFarm = 0x12;

...我怎麼能檢查，如果只有一個動物（即一個比特）被設置？

的onTheFarm的值必須是2 ^Ñ，但如何檢查編程（優選在Javascript）？

來源

2013-04-11 Tim

看看[這個問題]（http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer）。不是特定於JavaScript的，而是有趣的。 – 2013-04-11 14:46:21

感謝羅布，剛發現這個（它看起來更直截了當）http://stackoverflow.com/questions/1053582/how-does-this-bitwise-operation-check-for-a-power-of-2 – Tim 2013-04-11 14:53:21

僅供參考，'OMD' = ['Old MacDonald']（https://en.wikipedia.org/wiki/Old_MacDonald_Had_a_Farm）。 – rvighne 2014-05-18 23:14:43

你可以指望那些在一個非負整數，此代碼（從this answer適應的JavaScript）設置的位數：

function countSetBits(i) 
{ 
    i = i - ((i >> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 
}

它應該比單獨檢查每一位更高效。但是，如果符號位在i中設置，則不起作用。

EDIT（所有功勞都尖尖的評論）：

function isPowerOfTwo(i) { 
    return i > 0 && (i & (i-1)) === 0; 
}

來源

2013-04-11 14:53:24

哇，這很不錯。展望這一點，我發現[這個參考]（http://aggregate.org/MAGIC/#Is%20Power%20of%202）這個特定的問題，它看起來更好！ – Pointy 2013-04-11 15:05:37

你必須位校驗位，具有功能或多或少是這樣的：

function p2(n) { 
    if (n === 0) return false; 
    while (n) { 
    if (n & 1 && n !== 1) return false; 
    n >>= 1; 
    } 

    return true; 
}

一些CPU指令集都包含一個「設置位計數」操作（古代CDC網絡系列是一個）。這對於實現位集合的一些數據結構很有用。如果你有一個實現爲一個整數字符串的集合，其位置與設置的數據類型的元素相對應，那麼獲得基數就涉及計數位。

編輯哇尋找到泰德·霍普的答案，我碰到這個偶然發現：

function p2(n) { 
    return n !== 0 && (n & (n - 1)) === 0; 
}

從this awesome collection of "tricks"的。像這樣的問題的東西都是好的理由來學習數論:-)

來源

2013-04-11 14:49:08 Pointy

如果你想看看如果只有一個位被設置，你可以採取的logarithms優勢，如下：

var singleAnimal = (Math.log(onTheFarm)/Math.log(2)) % 1 == 0;

Math.log(y)/Math.log(2)找到x在2^x = y和x % 1告訴我們，如果x是一個整數。如果設置了一個位，x將只是一個整數，因此只有一個動物被選中。

來源

2013-04-11 14:57:59 cmptrgeekken

如果忽略浮點四捨五入，你會得出結論：（1 << 29）將會有多個位的設置：'console.log（（Math.log（1 << 29）/ Math.log（2））％1 ）'在我的機器上打印3.552713678800501e-15。 – 2013-04-11 15:05:02

有趣。總的來說，我認爲使用'log'的效率要遠遠低於其他方法的效率。知道處理浮點舍入錯誤的方法嗎？ – cmptrgeekken 2013-04-11 18:52:29

不適用於此問題。您可以閱讀[本文]（http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html）中有關問題的完整概述。技術上相當重要，但如果您想要深入瞭解浮點下的內容，則值得努力。 TL; DR版本是：每個浮點操作（即使簡單地表示一個數字）都有錯誤;相應地設計你的代碼。 – 2013-04-11 21:25:30

位掩碼：如何確定是否只有一個位被設置

回答

相關問題