LeetCode 231：2 的冪——位運算判斷整數是否為 2 的冂

題目描述

給定整數 n，判斷是否存在整數 k ≥ 0 使 n = 2^k。

位運算性質

2 的冂二進制表示有且僅有 1 個 1（最高位），其餘為 0。例如：8 = 1000₂。因此 n & (n-1) == 0（n-1 將最高位 1 變 0，低位全變 1）。

C++ 實現

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

替代寫法：計數 1 的個數

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    int cnt = 0;
    while (n) { cnt += n & 1; n >>= 1; }
    return cnt == 1;
}

複雜度

• 時間：O(1)（位運算）或 O(log n)（計數）。
• 空間：O(1)。

總結

n & (n-1) 是判斷 2 的冂、清除最低位 1 的經典技巧，同理可用於「判斷是否為 2 的冂減 1」（全 1）、「統計集合子集」等場景。