【leetcode刷題】32.二進制中1的個數——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

面試陌陌時遇到的一道題

Question

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

難度：簡單

編寫一個函數，輸入是一個無符号整數（以二進制串的形式），傳回其二進制表達式中數字位數為 ‘1’ 的個數（也被稱為 漢明重量).）。

提示：

請注意，在某些語言（如 Java）中，沒有無符号整數類型。在這種情況下，輸入和輸出都将被指定為有符号整數類型，并且不應影響您的實作，因為無論整數是有符号的還是無符号的，其内部的二進制表示形式都是相同的。

在 Java 中，編譯器使用 二進制補碼 記法來表示有符号整數。是以，在上面的 示例 3 中，輸入表示有符号整數 -3。

示例 1：

輸入：n = 11 (控制台輸入 00000000000000000000000000001011)
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。      

示例2:

輸入：n = 128 (控制台輸入 00000000000000000000000010000000)
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。      

示例3:

輸入：n = 128 (控制台輸入 00000000000000000000000010000000)
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。      

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

Solution

又是一道可以巧妙的用位運算解決的問題。

(n−1) ： 二進制數字 nn 最右邊的 1 變成 0 ，此 1 右邊的 0 都變成 1 。

n & (n - 1)： 二進制數字 n 最右邊的 1 變成 00 ，其餘不變。

• 通過與運算不斷消去右邊的1
• 統計進行與運算的次數
• 當 n = 0 時結束

Code

所有

leetcode

代碼已同步至 github 歡迎

star

/**
 * @author yitiaoIT
 */
public class Solution {
    public int hammingWeight(int n) {
        int sum = 0;
        while(n != 0) {
            sum++;
            n &= n - 1;
        }
        return sum;
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第32/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

大家可以先自己找一下擷取方式，尋寶遊戲現在開始。

如果實在找不到可以評論區留言或私信我領取，不過一定要先關注哦！不然無法發私信！