java - 在没有数学函数或对数函数的情况下查找数字是否是 2 的幂

Question

我想查看用户输入的数字是否为 2 的幂。

我的代码不起作用。

public class power_of_two
{  
    public static void main(String args[])  
    {  

        Scanner in=new Scanner(System.in);
        System.out.println("Enter the number : ");
        int num = in.nextInt();

        int other = 1;  
        if(((~num) & 1) == 1)  
        {  
            System.out.println("The number is a power of two");  
        }  
        else  
        {
            System.out.println("The number is a  NOT A power of two");  
        }
    }  
} 

告诉我如何求两个数的幂。
例如 8 是 2 的幂。
22 不是 2 的幂等。

Answer 1

您可以测试一个正整数 n 是否是 2 的幂，例如

(n & (n - 1)) == 0

如果 n 可以是非正数(即负数或零)，您应该使用

(n > 0) && ((n & (n - 1)) == 0)

---

如果 n 真的是 2 的幂，那么在二进制中它看起来像:

10000000...

所以 n - 1 看起来像

01111111...

当我们 bitwise-AND他们:

  10000000...
& 01111111...
  -----------
  00000000...

现在，如果 n 不是 2 的幂，那么它的二进制表示除了前面的 1 之外还有一些其他的 1，这意味着两个 n 和 n - 1 将具有相同的前导 1 位(因为如果二进制表示中某处还有另一个 1，则减 1 不可能关闭该位)。因此，如果 n 不是 2 的幂，则 & 操作不能产生 0，因为 & 将两个前导n 和 n - 1 的位将产生 1 本身。这当然假设 n 是正数。

这在 "Fast algorithm to check if a positive number is a power of two" 中也有解释。在维基百科上。

---

快速健全性检查:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1248163264