不使用数学函数或对数函数，如何判断一个数字是否为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的幂次方。

- sam

---

你的代码检查的是2的倍数，而不是2的幂次方。 - Daniel

我认为这个问题被错误地关闭了。链接的“重复问题”涉及到两种不同的语言（分别是C#和PHP）。当然，语义是相同的，但这是一个特定的 Java 问题。有关参考，请参阅http://meta.stackexchange.com/questions/189850/how-should-duplicates-of-language-independent-questions-be-handled. - arshajii

Answer 1

您可以使用类似以下代码来测试正整数 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不可能关闭此位）。因此，如果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);
}

1
2
4
8
16
32
64

- arshajii

---

( n & (n - 1) == 0 ) && n > 0 可以翻译为：当且仅当 n 大于 0 并且 n 与 (n - 1) 的按位与结果等于 0 时，该条件成立。 - Ahmed KRAIEM

@lining -16 不是2的幂。 - arshajii

我最近发现了这个替代方法，它基于相同的原理，并且更加模块化: Integer.bitCount(n) == 1。 - Andres Stadelmann

Answer 2

您可以使用位运算 AND (&) 运算符：

bitwise AND (&) operator

return (num & -num) == num

为什么这行得通？

考虑数字8，在二进制下表示为什么（假设是32位）？

0000 0000 0000 0000 0000 0000 0000 1000

现在让我们看看如何表示-8？ ¹

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，它不是二的幂。

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 为零时会发生什么... 我将把解决方案留给你 :)

¹ 一个好的记忆计算方法：从最右边的位开始，对于每个 0，不要改变它，当你看到 1 时，请保留它并继续进行，但从现在开始，反转所有位。我在这里尝试更详细地解释了一下（链接）。

- Maroun

---

可能不太明显为什么这是-8。也许了解这个概念的来源（http://en.wikipedia.org/wiki/Two's_complement）会有所帮助。 - Cruncher

我认为你需要在那里加上 num != 0 && ...（如果 num 可以是 0 的话）。否则 +1。 - arshajii

如果 num < 0，例如 -8，则会失败。我猜你需要检查它是否为 num 的绝对值，但无论如何都要加1。 - Harrison

为什么要使用 if (cond) { return true; } 而不是 return cond;？ - TemplateRex

@TemplateRex 会返回 true，即使 0 不是 2 的幂。 - Maroun

Answer 3

double input = 22;

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

return input == 2;

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

- Jeroen Vannevel

---

我同意。如果 OP 寻求可读性，那么这是他应该采取的方法，但从性能上来看，其他算法要好得多。 - Troubleshoot

不是最快的解决方案，但需要较少的二进制补码和位操作知识。就像冒泡排序一样，它是一个糟糕的解决方案，但易于理解。 - AlexWien

不仅阅读性差，而且问题的标题说“不使用数学函数”，我会认为这意味着不使用除法运算符。 - Eterm

@Eterm：我理解这个问题的方式是他不能使用“Math”函数，否则他会指定使用位运算。 - Jeroen Vannevel

@JeroenVannevel 1是2的幂，它是2^0。 - Eterm

Answer 4

直截了当的解决方案：

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)

- crazy2be

Answer 5

   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;
        }

- Kranti123

Answer 6

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

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")

- Pankaj Goyal

---

在这种情况下，您不能使用 n++，表达式必须为 n >= 2。 - karlphillip