快速判断一个数是否是2的幂次方

发表于 分类于 阅读次数：

如何利用位运算判断一个数是否是2的幂次方，如果是，是2的多少次方

将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0； 因此问题可以转化为判断1后面是否跟了n个0就可以了。

如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现为零。

最快速的方法： (number & number - 1) == 0

原因：因为2的N次方换算是二进制为10……0这样的形式(0除外)。与上自己-1的位数，这们得到结果为0。例如。8的二进制为1000；8-1=7，7的二进制为111。两者相与的结果为0。计算如下：

1
2
3
4
  1000
& 0111
 -------
  0000

递归实现的代码与非递归实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class IsTwoPower {
    public static void main(String[] args) {
        int n = 1024;
        if((n & (n - 1) )== 0){
            System.out.println("是2的" + log2(n) + "次方");
        }else {
            System.out.println("不是2的n次方");
        }
    }

    // 递归实现
    // 注意跳出递归条件，n == 1返回0效果一样但是多加了一层栈
    public static int log2_recursion(int n) {
        if(n == 2) {
            return 1;
        }else{
            return log2_recursion(n >> 1) + 1;
        }
    }

    // 非递归实现
    // 注意跳出循环条件，不要多加
    public static int log2(int n) {
        int count = 0;
        while (n != 1) {
            n = n >> 1;
            count ++;
        }
        return count;
    }
}

扩展1：求一个数n的二进制中的1的个数

了解了(number & number - 1) == 0这个特性以后，我们可以发现利用它可以移除一个数最右边的1，循环移除就可以得到1的个数

1
2
3
4
5
6
7
8
public static int fun3(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

扩展2：数A与数B的二进制位中有多少个数不相同

由于异或的特性，可知只有不同的数异或才为1，那么1的个数就是不相同的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int fun3(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

public static int difference(int i, int j) {
    int c = i ^ j;
    return fun3(c);
}