[Leetcode] Number of 1 Bits 一的位數(shù)

msup 發(fā)布于2019-08-14 12:21 / 2264人閱讀

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

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.

移位法 復(fù)雜度

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

思路

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

注意

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

代碼

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;
    }
}

減一相與法 復(fù)雜度

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

思路

該方法又叫Brian Kernighan方法。當(dāng)原數(shù)不為0時，將原數(shù)與上原數(shù)減一的值賦給原數(shù)。因為每次減一再相與實際上是將最左邊的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;
    }
}