找到2的幂的算法 [英] Algorithm to find the power of 2

问题描述

我找到了一个小算法来确定一个数字是2的幂，但不能解释它是如何工作的，究竟发生了什么？

I have found a small algorithm to determine if a number is power of 2, but not an explanation for how it works, what really happens?

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


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

推荐答案

我将解释它如何适用于非负 n 。 n&&中的第一个条件！（n&（n - 1））只检查 n 是否为零。如果 n 不为零，那么它在某个位置有一些最不重要的 1 -bit p 。现在，如果从 n 中减去 1 ，则位置 p 将更改为 1 ， p 位将转换为 0 。

I'll explain how it works for non-negative n. The first condition in n && !(n & (n - 1)) simply checks that n is not zero. If n is not zero, then it has some least significant 1-bit at some position p. Now, if you subtract 1 from n, all bits before position p will change to 1, and the bit at p will flip to 0.

这样的事情：

n:       1010100010100111110010101000000
n-1:     1010100010100111110010100111111
                                 ^ position p

现在，如果你& 这两个位模式，位置 p 之后的所有东西都保持不变，以及之前的所有内容（并包括 p ）归零：

Now, if you & these two bit-patterns, all the stuff after the position p remains unchanged, and everything before (and including p) is zeroed out:

after &: 1010100010100111110010100000000
                                 ^ position p

如果取得& <后的结果/ code>恰好为零，那么这意味着在 p 之后没有任何内容，因此该数字必须是
2 ^ p ，看起来像这样：

If the result after taking & happens to be zero, then it means that there was nothing after position p, thus the number must have been 2^p, which looked like this:

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

因此 n 是 2的幂。如果& 的结果不为零（如第一个示例中所示），则表示在 p -th position，因此 n 不是 2 的幂。

thus n is a power of 2. If the result of & is not zero (as in the first example), then it means that there was some junk in the more significant bits after the p-th position, and therefore n is not a power of 2.

对于负数的2补码表示，我太懒了。

I'm too lazy to play this through for the 2-complement representation of negative numbers.

这篇关于找到2的幂的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！