算法：计算一个数的下个为2的幂的数

介绍

输入一个值，计算出一个比它大的为2的幂的数。

思路

所有为2的幂的数，它的二进制数表示永远只有一位为1，其它都是为0

• 2º：00000001
• 2¹：00000010
• 2²：00000100
• 2³：00001000
• …

代码

int nextPowerOf2(int n) {
    n -= 1;
    n |= n >>> 16;
    n |= n >>> 8;
    n |= n >>> 4;
    n |= n >>> 2;
    n |= n >>> 1;
    return n + 1;
}

目的是把n - 1从最高位为1的位开始到最低位的所有位全都变成1，最后加1进位，以达到目的。

注：如果n本身已经是2的幂，只运行移位就会得到n * 2，所以先减1。如果n是0，减1就是-1，对应的无符号数为位数全为1的数，加1结果是0。

附 - 判断一个数是否为2的幂

算法1

所有为2的幂的数，它的二进制数表示永远只有一位为1，其它都是为0，将这个数减去1后，仅有的那个1会变为0，而原来的那n个0会变为1。如原来的数'n'为00100000，'n-1'为00011111。因此，将原来的数与减去1后的数字进行与运算后为零。

public static boolean isPowerOf2(int n) {
    return (n & n - 1) == 0;
}

算法2

所有为2的幂的数，它的二进制数表示永远只有一位为1，其它都是为0，这个数的补码是1位位置前面的位全部变为1，1位位置后面的位全部变为0。如原来的数'n'为00100000，'-n'为11100000。因此，将原来的数与原来的数的补码进行与运算后为原来的数不变。

public static boolean isPowerOf2(int n) {
    return (n & -n) == n;
}