LeetCode 231. 2的幂 && LeetCode 338. 比特位計數（2進制1的個數）

1. 題目資訊

給定一個整數，編寫一個函數來判斷它是否是 2 的幂次方。

示例 1:

輸入: 1
輸出: true
解釋: 20 = 1
示例 2:

輸入: 16
輸出: true
解釋: 24 = 16
示例 3:

輸入: 218
輸出: false           

複制

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/power-of-two

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 2的整數次幂的2進制數中隻有1個1
• n經過

  運算 n&(n-1)

  得到的數的二進制1的個數減少1個

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        return (n&(n-1)) == 0;//錯誤寫法 n&(n-1) == 0
    }
};           

複制

拓展：求一個數n的2進制有多少個1？

int count = 0, num = 8;
while(num)
{
    count++;
    num = num&(num-1);
}
std::cout << count << std::endl;           

複制

LeetCode 338

給定一個非負整數 num。對于 0 ≤ i ≤ num 範圍中的每個數字 i ，計算其二進制數中的 1 的數目并将它們作為數組傳回。

class Solution {
public:
    vector<int> countBits(int num) {
        int count, temp;
        vector<int> ans;
        for(int i = 0; i <= num; ++i)
        {
            count = 0;
            temp = i;
            while(temp)
            {
                temp &= (temp-1);
                ++count;
            }
            ans.push_back(count);
        }
        return ans;
    }
};           

複制

對338題還可以用動态規劃

• dp[0] = 0

奇數	偶數
1-‘01’-dp[1]=1	2-‘10’-dp[2]=1
3-‘11’-dp[3]=2	4-‘100’-dp[4]=1
5-‘101’-dp[5]=2	6-‘110’-dp[6]=2
7-‘111’-dp[7]=3	8-‘1000’-dp[8]=1

n 為 奇 數 ， d p [ n ] = d p [ n − 1 ] + 1 n為奇數，dp[n] = dp[n-1]+1 n為奇數，dp[n]=dp[n−1]+1，比前面的多1，好了解

n 為 偶 數 ， d p [ n ] = d p [ n / 2 ] n為偶數，dp[n]=dp[n/2] n為偶數，dp[n]=dp[n/2]，2的倍數，隻需要移動位數就可以，1個數不變

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans(num+1);
        ans[0] = 0;
        for(int i = 0; i <= num; ++i)
        {
            if(i % 2 == 1)
            {
                ans[i] = ans[i-1] + 1;
            }
            else
            {
                ans[i] = ans[i/2];
            }
        }
        return ans;
    }
};           

複制