algorithm - 一个数能否表示为2的n次方？这个逻辑如何运作？

Question

众所周知，要检查一个数字是否可以表示为 2 的幂。为了解决这个问题，我们使用位操作来加快速度。

if( n && !(n&(n-1)))
print("yes number can be express 2 to power");
print("No number can not be express 2 to power");

我的问题是它是如何工作的。为什么是 n&(n-1)？为什么不是 n&(n-2) 或其他任何东西。

任何想法将不胜感激。

提前致谢。

Answer 1

与n的位模式相比，在n-1中，包括最后一个1在内的所有位都将被翻转。左边的位不变。例如

n   01001000
n-1 01000111

因此，如果 n 的位模式中有多个 1，则表达式 n&(n-1) 将是非 -零。

一个特例是值 0，它不是 2 的幂，但表达式给出 0。所以它在这种情况下不起作用。