劍指 Offer 15 – 二進制中1 的個數

題目：

請實作一個函數，輸入一個整數（以二進制串形式），輸出該數二進制表示中 1 的個數。例如，把 9 表示成二進制是 1001，有 2 位是 1。是以，如果輸入 9，則該函數輸出 2。

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。
           

示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。
           

示例 3：

輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進制串 11111111111111111111111111111101 中，共有 31 位為 '1'。
           

提示：

輸入必須是長度為 32 的 二進制串 。
           

分析：

• n & 1 = 0 則 n 二進制最右邊一位為 0；
• n & 1 = 1 則 n 二進制最右邊一位為1；

代碼：

package com.xujinshan.offer.offer15;

/**
 * @Author: [email protected]
 * 劍指 Offer 15 -- 二進制中1 的個數
 * 劍指 Offer 15. 二進制中1的個數
 * <p>
 * 請實作一個函數，輸入一個整數（以二進制串形式），輸出該數二進制表示中 1 的個數。
 * 例如，把 9 表示成二進制是 1001，有 2 位是 1。是以，如果輸入 9，則該函數輸出 2。
 * <p>
 * 示例 1：
 * <p>
 * 輸入：00000000000000000000000000001011
 * 輸出：3
 * 解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。
 * <p>
 * 示例 2：
 * <p>
 * 輸入：00000000000000000000000010000000
 * 輸出：1
 * 解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。
 * <p>
 * 示例 3：
 * <p>
 * 輸入：11111111111111111111111111111101
 * 輸出：31
 * 解釋：輸入的二進制串 11111111111111111111111111111101 中，共有 31 位為 '1'。
 * <p>
 * 提示：
 * <p>
 * 輸入必須是長度為 32 的 二進制串 。
 */

/**
 * 分析：
 * n & 1 = 0 則 n 二進制最右邊一位為 0；
 * n & 1 = 1 則 n 二進制最右邊一位為1；
 * 根據以上特點，考慮以下循環判斷：
 * 1.判斷n最後一位是否是1，根據結果計數
 * 2.将n 右移動一位(本題要求把數字 n 看作無符号數，是以使用無符号右移操)
 */
class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                result++;
            }
            // >>：帶符号右移。正數右移高位補0，負數右移高位補1
            // >>>：無符号右移。無論是正數還是負數，高位通通補0
            n = n >>> 1;
        }
        return result;
    }
}

public class Offer15 {
    public static void main(String[] args) {
        System.out.println(new Solution().hammingWeight(00000000000000000000000010000000));
    }
}
           

結果：