題目
#

leetcode 191 - Number of 1 Bits (題目說明請點連結)

題目簡述
#

計算一個 32 位無符號整數的二進制表示中 ‘1’ 的個數。

範例
#

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: 輸入的二進制數 00000000000000000000000000001011 中有三個 '1' 位。

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: 輸入的二進制數 00000000000000000000000010000000 中只有一個 '1' 位。

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: 輸入的二進制數 11111111111111111111111111111101 中有三十一個 '1' 位。

解題思路
#

這題要求我們計算一個 32 位無符號整數的二進制表示中 ‘1’ 的個數。我們需要逐位檢查每一位是否為 1，並統計總數。

解法
#

位運算計數法（Bit Manipulation Approach）

初始化計數器 cnt = 0
當 n > 0 時，繼續迴圈：
- 使用 n & 1 取出最右邊的位
- 如果該位為 1，計數器加 1
- 將 n 右移一位，準備檢查下一位
返回計數器的值

步驟
#

初始化：
- cnt = 0（計數器）
逐位檢查：
- 當 n > 0 時繼續迴圈
- cnt += n & 1：取出最右位並加到計數器
- n >>= 1：n 右移一位
返回結果：
- 返回 cnt

核心邏輯
#

while(n > 0) {
    cnt += n & 1;    // 取出最右位並計數
    n >>= 1;         // 右移一位
}

位運算符說明
#

&：按位與運算符，n & 1 可以取出 n 的最右邊一位
>>=：右移賦值運算符，將左邊的數右移指定位數
+=：加法賦值運算符，將右邊的值加到左邊的變數上

例子說明
#

n = 13（二進制：1101）

步驟	n（二進制）	n & 1	cnt	說明
初始化	1101	-	0	設定計數器為0
第1輪	1101	1	1	最右位為1，cnt += 1
第2輪	110	0	1	最右位為0，cnt += 0
第3輪	11	1	2	最右位為1，cnt += 1
第4輪	1	1	3	最右位為1，cnt += 1
第5輪	0	-	3	n = 0，迴圈結束
最終結果	-	-	3	總共有3個1位

完整程式碼
#

java

class Solution {
    public int hammingWeight(int n) {
        // 初始化計數器
        int cnt = 0;
        
        // 當n大於0時，繼續檢查每一位
        while(n > 0){
            // 取出n的最右一位，加到計數器上
            cnt += n & 1;
            // 將n右移一位，準備檢查下一位
            n >>= 1; 
        }

        // 返回1的個數
        return cnt;
    }
}