[LeetCode] 191. Number of 1 Bits* 解題思路 (Easy)

這題需要判斷二進制數字總共有幾個1。

LeetCode 題目連結

 

https://leetcode.com/problems/number-of-1-bits/

 

題目

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).




Example 1:Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.


Example 2:Input: 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.


Example 3:Input: 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Accept 作法

這題時間複雜度為 O(1)，利用比自己小1的數字做 & 可消除掉 1，一直到沒有 1 為止。


Runtime: 1 ms
Memory: 38.6 MB

Java 程式碼

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            n &= (n-1);
            count++;
        }
        return count;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

 

 

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題