查找数字是否为2的幂，没有数学函数或日志函数 [英] Find if a number is a power of two without math function or log function

问题描述

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

I want to find if a user entered number is a power of two or not.

我的代码不起作用。

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的幂等等。

Let me know how can I find the power of two number.
For example 8 is a power of 2.
22 is not a power of 2, etc..

推荐答案

您可以测试正整数 n 是否为2的幂类似

You can test if a positive integer n is a power of 2 with something like

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

如果 n 可以是非正数（即负数或零），你应该使用

If n can be non-positive (i.e. negative or zero) you should use

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

---

如果 n 确实是2的幂，那么在二进制中它将看起来像：

---

If n is truly a power of 2, then in binary it will look like:

10000000...

所以 n - 1 看起来像

01111111...

当我们按位-EN 时他们：

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

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

Now, if n isn't a power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both n and n - 1 will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the & operation cannot produce 0 if n is not a power of 2, since &ing the two leading bits of n and n - 1 will produce 1 in and of itself. This of course assumes that n is positive.

这也在快速算法检查正数是否是2的幂。

This is also explained in "Fast algorithm to check if a positive number is a power of two" on Wikipedia.

快速健全性检查：

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

1
2
4
8
16
32
64

这篇关于查找数字是否为2的幂，没有数学函数或日志函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！