javascript - 求 2 次方的算法

Question

我找到了一个小算法来确定一个数是否是 2 的幂，但没有解释它是如何工作的，到底发生了什么？

var potence = n =>  n && !(n & (n - 1));


for(var i = 2; i <= 16; ++i) {
   if(potence(i)) console.log(i + " is potence of 2");
}

Answer 1

我将解释它如何适用于非负 n。 n && !(n & (n - 1)) 中的第一个条件只是检查 n 不为零。如果 n 不为零，则它在某个位置 p 有一些最低有效的 1 位。现在，如果从 n 中减去 1，位置 p 之前的所有位都将变为 1，并且该位在 p 将翻转到 0。

像这样:

n:       1010100010100111110010101000000
n-1:     1010100010100111110010100111111
                                 ^ position p

现在，如果你 & 这两个位模式，位置 p 之后的所有内容保持不变，之前的所有内容(包括 p) 被清零:

after &: 1010100010100111110010100000000
                                 ^ position p

如果取&后的结果恰好为零，则说明位置p后没有任何东西，因此这个数一定是2^p，看起来像这样:

n:       0000000000000000000000001000000
n - 1:   0000000000000000000000000111111
n&(n-1): 0000000000000000000000000000000
                                 ^ position p

因此 n 是 2 的幂。如果 & 的结果不为零(如第一个示例中所示)，则意味着在第 p 位置之后的较高有效位中存在一些垃圾，因此 n 不是 2 的幂。

对于负数的 2 补码表示，我懒得玩这个了。