0191. 位1的個數 · ttttt

# 0191. 位1的個數 ## 題目地址(191. 位1的個數) <https://leetcode-cn.com/problems/number-of-1-bits/> ## 題目描述 ``` <pre class="calibre18">``` 編寫一個函數，輸入是一個無符號整數，返回其二進制表達式中數字位數為 ‘1’ 的個數（也被稱為漢明重量）。示例 1：輸入：00000000000000000000000000001011 輸出：3 解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。示例 2：輸入：00000000000000000000000010000000 輸出：1 解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。示例 3：輸入：11111111111111111111111111111101 輸出：31 解釋：輸入的二進制串 11111111111111111111111111111101 中，共有 31 位為 '1'。提示：請注意，在某些語言（如 Java）中，沒有無符號整數類型。在這種情況下，輸入和輸出都將被指定為有符號整數類型，并且不應影響您的實現，因為無論整數是有符號的還是無符號的，其內部的二進制表示形式都是相同的。在 Java 中，編譯器使用二進制補碼記法來表示有符號整數。因此，在上面的示例 3 中，輸入表示有符號整數 -3。進階: 如果多次調用這個函數，你將如何優化你的算法？ ``` ``` ## 前置知識 - [位運算](https://github.com/azl397985856/leetcode/blob/master/thinkings/bit.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - apple - microsoft ## 思路這個題目的大意是：給定一個無符號的整數，返回其用二進制表式的時候的1的個數。這里用一個trick，可以輕松求出。就是`n & (n - 1)` 可以`消除` n 最后的一個1的原理。 > 為什么能消除最后一個1，其實也比較簡單，大家自己想一下這樣我們可以不斷進行`n = n & (n - 1)`直到n === 0 ，說明沒有一個1了。這個時候`我們消除了多少1變成一個1都沒有了，就說明n有多少個1了`。 ## 關鍵點解析 1. `n & (n - 1)` 可以`消除` n 最后的一個1的原理簡化操作 2. bit 運算 ## 代碼語言支持：JS, C++，Python JavaScript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=191 lang=javascript * */ /** * @param {number} n - a positive integer * @return {number} */ var hammingWeight = function(n) { let count = 0; while (n !== 0) { n = n & (n - 1); count++; } return count; }; ``` ``` C++ code: ``` <pre class="calibre18">``` class Solution { public: int hammingWeight(uint32_t v) { auto count = 0; while (v != 0) { v &= (v - 1); ++count; } return count; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 while n: n &= n - 1 count += 1 return count ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(logN)O(logN) - 空間復雜度：O(N)O(N)O(N) ## 擴展可以使用位操作來達到目的。例如8位的整數21: ![](https://img.kancloud.cn/5d/a2/5da2347ede89ef9f157273a94a964dea_288x284.jpg) C++ Code： ``` <pre class="calibre18">``` const uint32_t ODD_BIT_MASK = 0xAAAAAAAA; const uint32_t EVEN_BIT_MASK = 0x55555555; const uint32_t ODD_2BIT_MASK = 0xCCCCCCCC; const uint32_t EVEN_2BIT_MASK = 0x33333333; const uint32_t ODD_4BIT_MASK = 0xF0F0F0F0; const uint32_t EVEN_4BIT_MASK = 0x0F0F0F0F; const uint32_t ODD_8BIT_MASK = 0xFF00FF00; const uint32_t EVEN_8BIT_MASK = 0x00FF00FF; const uint32_t ODD_16BIT_MASK = 0xFFFF0000; const uint32_t EVEN_16BIT_MASK = 0x0000FFFF; class Solution { public: int hammingWeight(uint32_t v) { v = (v & EVEN_BIT_MASK) + ((v & ODD_BIT_MASK) >> 1); v = (v & EVEN_2BIT_MASK) + ((v & ODD_2BIT_MASK) >> 2); v = (v & EVEN_4BIT_MASK) + ((v & ODD_4BIT_MASK) >> 4); v = (v & EVEN_8BIT_MASK) + ((v & ODD_8BIT_MASK) >> 8); return (v & EVEN_16BIT_MASK) + ((v & ODD_16BIT_MASK) >> 16); } }; ``` ``` 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經37K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)