62

我想知道用户输入的数字是否是 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 的幂，等等。

4

6 回答 6

203

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

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

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

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

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

10000000...

所以n - 1看起来像

01111111...

当我们按位与它们时：

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

现在，如果n 不是2 的幂，那么它的二进制表示除了前导 1 之外还有一些其他的 1，这意味着两者n和n - 1都将具有相同的前导 1 位（因为减 1 不可能关闭该位，如果在某处的二进制表示中还有另一个 1）。因此，该&操作不能产生0ifn不是 2 的幂，因为ing和&的两个前导位将在其自身中产生。这当然假设这是积极的。nn - 11n

这也在Wikipedia 上的“检查正数是否为 2 的幂的快速算法”中进行了解释。

快速健全性检查：

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

1
2
4
8
16
32
64
于 2013-10-15T14:04:46.457 回答
96

您可以使用bitwise AND (&) operator：

return (num & -num) == num

为什么这行得通？

考虑数字 8，它是什么二进制（假设是 32 位）？ 

0000 0000 0000 0000 0000 0000 0000 1000

现在让我们看看 -8 是如何表示的？1

1111 1111 1111 1111 1111 1111 1111 1000

最后..让我们计算一下8 & -8：

0000 0000 0000 0000 0000 0000 0000 1000   8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &
1111 1111 1111 1111 1111 1111 1111 1000  -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000   8    ¯\_(ツ)_/¯

7现在让我们再举一个例子，假设不是2 的幂。

0000 0000 0000 0000 0000 0000 0000 0111   7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &                       
1111 1111 1111 1111 1111 1111 1111 1001  -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  != 7  ¯\_(ة_ة)_/¯

正如@arshajii 所提到的，想想如果num为零会发生什么......我会为你留下解决方案:)

1记住如何计算的好方法：从最右边的位开始，对于你看到的每个 0，不要更改它，当你看到 1 时，离开它并继续，但从现在开始，反转所有位。我试图在这里更多地解释这一点。

于 2013-10-15T14:05:31.600 回答
7 
double input = 22;

while(((input != 2) && input % 2 == 0) || input == 1) {
 input = input /2;
}

return input == 2;

继续将它除以 2，直到达到 1 或奇数。如果它达到 1，它是 2 的幂，否则它不是。

于 2013-10-15T14:06:06.000 回答
5

直接的解决方案：

bool isPowerOfTwo(int n) {
    // All values < 1 cannot be (positive, at least) powers of two.
    if (n < 1) return false;

    // Keep shifting bits.
    while (n > 1) {
        // Since n > 1, the low bit set means at least two bits must
        // be set, making n no longer a power of two.
        if (n & 0x1) return false;
        // Throw away the bottom (zero) bit.
        n >>= 1;
    }
    // Only one bit was set, therefore, n is a power of two.
    return true;
}

当然，这并不像其他一些技巧解决方案（确实非常聪明）那样最佳，但很容易看出它是如何工作的，并在你的脑海中验证它是否有效。

对于输入4，我们得到：

n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true

对于无效输入，例如5，我们得到：

n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)
于 2013-10-15T19:20:49.790 回答
0 
   public boolean isPowerOfTwo(int n){

            boolean isPower=false;
            int temp=n;

            while(temp>=2){
                if(temp%2==0){
                    isPower=true;

                }else{
                    isPower=false;
                    break;
                }
                temp=temp/2;
            }

            if(isPower){
                System.out.println("power of 2");
            }else{
                System.out.println("not power of 2");
            }

            return isPower;
        }
于 2014-07-06T18:51:07.243 回答
-3

一个非常简单的解决方案。

int n = 8; // any integer and you can take it from user also
for(;n>0;n++){
    if(n%2 != 0) {
        System.out.println("not a power of two")
        return;
    } // if ends here
    n = n/2;
}// for ends here
System.out.println("power of two")
于 2013-12-11T08:33:24.250 回答