【Java】位运算判断2的N次幂

思考

如何判断一个数是不是2的N次幂？ 难道要一直除下去？一直乘过去？还是打表？ 我们就不能简单一些处理这个问题吗？ 那就有了这篇博客的内容——位运算判断一个数是不是2的N次幂……

核心算法

其实就是：(num & num-1) == 0

&表示按位取且，运算规律是（在二进制的情况下）：

• 1 & 1 = 1
• 1 & 0 = 0
• 0 & 1 = 0
• 0 & 0 = 0

Java编程实现

private static boolean isPowOfTwo(int num) {
    return (num & num-1) == 0;
}

算法正确性

我们把一个十进制的数当成二进制来看。

Q：2的N次幂的二进制有什么特点？

先枚举一些例子： 1 → 00000001 2 → 00000010 4 → 00000100 8 → 00001000 ……

A：二进制表示的情况下只有一位（非最高位）是1。

我们不加以形式化地证明一下：

假设不是2的N次幂，这个数起码就要比2大（我们只考虑正整数），至少也是00000011（8位二进制表示），那么非0的就不止1个，至少2位非0。 那么对于num-1，一定不会去到最高位非0位去“借位”，所以最高非0位一定不変，还是1。 既然我们按位取且，所以num & num-1（注意位运算的优先级弱于加减，可以这么写而不加括号）至少会在num原先的最高非0位保持1,（因为1&1=1），这样的结果就不可能是0（因为0是00000000）。

所以我们就能发现，只有在num是2n(0≤n, n∈N+)的情况下，(num & num-1) == 0为真。

完整代码

import java.util.Scanner;

public class JudgePowOfTwo {

    private static boolean isPowOfTwo(int num) {
        return (num & num-1) == 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        System.out.println(isPowOfTwo(num));
    }
    
}

2021.3.24更新 如果是考虑到0的话，应该这么写： ( ( n u m ! = 0 ) & & ( n u m & n u m − 1 ) ) = = 0 ((num!=0)\&\&(num\&num-1))==0 ((num!=0)&&(num&num−1))==0