[Leetcode] Number of 1 Bits 一的位數

msup 發布于2019-08-14 12:21 / 2259人閱讀

摘要：重復此步驟直到原數歸零。注意右移運算符是算術右移，如果符號位是的話最高位將補，符號位是的話最高位補。當原數不為時，將原數與上原數減一的值賦給原數。因為每次減一再相與實際上是將最左邊的給消去了，所以消去幾次就有幾個。

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(1) 空間 O(1)

思路

通過與運算符判斷最低位/最高位是否是1，然后再右移/左移。重復此步驟直到原數歸零。

注意

右移運算符是算術右移，如果符號位是1的話最高位將補1，符號位是0的話最高位補0。在C/C++中可以先將原數轉換成無符號整數再處理，而在Java中可以使用無符號右移算術符>>>。當然，左移的解法就沒有這個問題了。

代碼

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

減一相與法 復雜度

時間 O(1) 空間 O(1)

思路

該方法又叫Brian Kernighan方法。當原數不為0時，將原數與上原數減一的值賦給原數。因為每次減一再相與實際上是將最左邊的1給消去了，所以消去幾次就有幾個1。比如110，減去1得101，相與得100，消去了最左邊的1。

代碼

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

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

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

LeetCode[191] Number of 1 Bits

摘要：依次移位復雜度思路依次移動位數進行計算。代碼利用性質復雜度，思路代碼 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). Fo...

Scliang 2019-08-14 15:00 評論0 收藏0
[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 PHP題解--D57 762. Prime Number of Set Bits

摘要：題目鏈接題目分析對給定范圍內的每個整數，返回其二進制形式下，數字出現的次數為質數的次數。思路由于題目固定了范圍為，次方為千萬。即最多只會出現次。存在則符合題目要求的數字，否則不計入該數字。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 D57 762. Prime Number of Set Bits in Binary Representation 題目鏈接 762. Prime ...

Cobub 2019-07-01 12:45 評論0 收藏0
leetcode7:漢明距離

摘要：題目漢明距離是兩個字符串對應位置的不同字符的個數，這里指二進制的不同位置例子我的解法先將，進行異位或運算再轉化成二進制然后把去掉算出長度其他方法先算出不同位數，然后用右移運算符算出能右移幾次來獲取距離 1題目 The Hamming distance between two integers is the number of positions at which the corresp...

xeblog 2019-08-23 16:46 評論0 收藏0
leetcode190 Reverse Bits

摘要：思路一比特位移動將比特位逆轉過來也就是將十進制數轉化為二進制數，再從右往左獲得每一位上的值，再將這個值添加至結果值中。根據分治思想，逆轉個比特位等價于分別將每個比特位進行逆轉。題目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...

趙連江 2019-08-16 10:59 評論0 收藏0