# Leetcode [No. 191] Number of 1 Bits(EASY)

## 題目

https://leetcode.com/problems/number-of-1-bits/description/?envType=daily-question&envId=2023-12-12

去計算一個數字裡面有多少個1。

## 思路
+ 原版: 先去判斷第0個bit是否為1，如果是的話cnt就++，我們可以透過n&1的回傳來得到結果

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n > 0)
        {
            if(n & 1) cnt++;
            n = n >> 1;
        }
        return cnt;
    }
};

### 解法分析
+ time complexity:$O(klgn), 多了if要判斷$

### 執行結果

---
+ 改善後的版本，不用去做if的判斷。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n > 0)
        {
            cnt += n & 1; // faster than **if(n & 1) cnt++**
            n = n >> 1;
        }
        return cnt;
    }
};

### 解法分析
+ time complexity: O(lgn)

### 執行結果


## 2nd visited on 2025/05/24

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while (n > 0) {
            cnt += n % 2;
            n = n >> 1;
        }
        return cnt;
    }
};