LeetCode[191] Number of 1 Bits

Scliang 發布于2019-08-14 15:00 / 3426人閱讀

摘要：依次移位復雜度思路依次移動位數進行計算。代碼利用性質復雜度，思路代碼

LeetCode[191] Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1" bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11" has binary representation 00000000000000000000000000001011, so the function should return 3.

依次移位

復雜度
O(N), O(1), N = number of bits in the interger

思路
依次移動位數進行計算。
The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
So when the first bit is 1, if use >>, 1 will always be there, then the loop will never end.

代碼

public int hammingWeight(int n) {
    int cnt = 0;
    while(n != 0) {
        if((n & 1) == 1) {
            cnt ++;
        }
        // must use unsigned operation
        n = n >>> 1;
    }
    return cnt;
}

利用性質 n & (n - 1)

復雜度
O(N), O(1)， N = number of 1 bits in the number

思路
consider n & (n - 1) always eliminates the least significant 1.

代碼

public int hammingWeight(int n) {
    int cnt = 0;
    // loop times = number of 1"s in the n
    while(n != 0) {
        n = n & (n - 1);
        cnt ++;
    }
    return cnt;
}

云服務器 GPU云服務器 Bits jquery191 cdn-191磁力 LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65226.html

[LeetCode] 191. Number of 1 Bits

Problem Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Example For example, the 32-bit integer 11 has bina...

gitmilk 2019-08-16 12:31 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
[Leetcode] Number of 1 Bits 一的位數

摘要：重復此步驟直到原數歸零。注意右移運算符是算術右移，如果符號位是的話最高位將補，符號位是的話最高位補。當原數不為時，將原數與上原數減一的值賦給原數。因為每次減一再相與實際上是將最左邊的給消去了，所以消去幾次就有幾個。 Number of 1 Bits Write a function that takes an unsigned integer and returns the numbe...

msup 2019-08-14 12:21 評論0 收藏0