<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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">``` <span class="hljs-title">/* * @lc app=leetcode id=191 lang=javascript * */</span> <span class="hljs-title">/** * @param {number} n - a positive integer * @return {number} */</span> <span class="hljs-keyword">var</span> hammingWeight = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (n !== <span class="hljs-params">0</span>) { n = n & (n - <span class="hljs-params">1</span>); count++; } <span class="hljs-keyword">return</span> count; }; ``` ``` C++ code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">hammingWeight</span><span class="hljs-params">(uint32_t v)</span> </span>{ <span class="hljs-keyword">auto</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (v != <span class="hljs-params">0</span>) { v &= (v - <span class="hljs-params">1</span>); ++count; } <span class="hljs-keyword">return</span> count; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hammingWeight</span><span class="hljs-params">(self, n)</span>:</span> <span class="hljs-string">""" :type n: int :rtype: int """</span> count = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> n: n &= n - <span class="hljs-params">1</span> count += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> 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">``` <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> ODD_BIT_MASK = <span class="hljs-params">0xAAAAAAAA</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> EVEN_BIT_MASK = <span class="hljs-params">0x55555555</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> ODD_2BIT_MASK = <span class="hljs-params">0xCCCCCCCC</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> EVEN_2BIT_MASK = <span class="hljs-params">0x33333333</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> ODD_4BIT_MASK = <span class="hljs-params">0xF0F0F0F0</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> EVEN_4BIT_MASK = <span class="hljs-params">0x0F0F0F0F</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> ODD_8BIT_MASK = <span class="hljs-params">0xFF00FF00</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> EVEN_8BIT_MASK = <span class="hljs-params">0x00FF00FF</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> ODD_16BIT_MASK = <span class="hljs-params">0xFFFF0000</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">uint32_t</span> EVEN_16BIT_MASK = <span class="hljs-params">0x0000FFFF</span>; <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">hammingWeight</span><span class="hljs-params">(uint32_t v)</span> </span>{ v = (v & EVEN_BIT_MASK) + ((v & ODD_BIT_MASK) >> <span class="hljs-params">1</span>); v = (v & EVEN_2BIT_MASK) + ((v & ODD_2BIT_MASK) >> <span class="hljs-params">2</span>); v = (v & EVEN_4BIT_MASK) + ((v & ODD_4BIT_MASK) >> <span class="hljs-params">4</span>); v = (v & EVEN_8BIT_MASK) + ((v & ODD_8BIT_MASK) >> <span class="hljs-params">8</span>); <span class="hljs-keyword">return</span> (v & EVEN_16BIT_MASK) + ((v & ODD_16BIT_MASK) >> <span class="hljs-params">16</span>); } }; ``` ``` 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看