介紹

輸入一個(gè)值，計(jì)算出一個(gè)比它大的為2的冪的數(shù)。

思路

所有為2的冪的數(shù)，它的二進(jìn)制數(shù)表示永遠(yuǎn)只有一位為1，其它都是為0

• 2o：00000001
• 21：00000010
• 22：00000100
• 23：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的位開(kāi)始到最低位的所有位全都變成1，最后加1進(jìn)位，以達(dá)到目的。

注：如果n本身已經(jīng)是2的冪，只運(yùn)行移位就會(huì)得到n * 2，所以先減1。如果n是0，減1就是-1，對(duì)應(yīng)的無(wú)符號(hào)數(shù)為位數(shù)全為1的數(shù)，加1結(jié)果是0。

附 - 判斷一個(gè)數(shù)是否為2的冪

算法1

所有為2的冪的數(shù)，它的二進(jìn)制數(shù)表示永遠(yuǎn)只有一位為1，其它都是為0，將這個(gè)數(shù)減去1后，僅有的那個(gè)1會(huì)變?yōu)?code>0，而原來(lái)的那n個(gè)0會(huì)變?yōu)?code>1。如原來(lái)的數(shù)'n'為00100000，'n-1'為00011111。因此，將原來(lái)的數(shù)與減去1后的數(shù)字進(jìn)行與運(yùn)算后為零。

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

算法2

所有為2的冪的數(shù)，它的二進(jìn)制數(shù)表示永遠(yuǎn)只有一位為1，其它都是為0，這個(gè)數(shù)的補(bǔ)碼是1位位置前面的位全部變?yōu)?code>1，1位位置后面的位全部變?yōu)?code>0。如原來(lái)的數(shù)'n'為00100000，'-n'為11100000。因此，將原來(lái)的數(shù)與原來(lái)的數(shù)的補(bǔ)碼進(jìn)行與運(yùn)算后為原來(lái)的數(shù)不變。

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