【LeetCode】Number of 1 Bits解題報告

Number of 1 Bits
[LeetCode]
https://leetcode.com/problems/number-of-1-bits/
Total Accepted: 88721 Total Submissions: 236174 Difficulty: Easy
Question
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.
Ways
方法1
実はどんどん右に移動します.最後の人が全部で何回現れたかを判断する.
最初にACがなかったのはjavaが符号無し整数であったため,intの最高位が1であれば負数と考えられるため,通常右シフトしてn=0がタイムアウトと判断し,n>0と判断するとそのまま運転しなかったためである.
Javaはシンボルビットを保持しない>>>を提供しています.

>>           。

左に移動する方法ではそんなに考えなくてもいいようです.
本来はn%2=1で最下位が1かどうかを判断したいのですが、効率が悪すぎて、n&1で最下位計算時のレートを速めることができます.

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

AC:2ms
方法2
LeetCodeが与えたもう一つの巧みな解法.
n&(n-1)!=0の場合、nには少なくとも1つが含む.
最後の1つをn=n&(n−1)の方法で消去することができる.
We can make the previous algorithm simpler and a little faster. Instead of checking every bit of the number, we repeatedly flip the least-significant 11-bit of the number to 00, and add 11 to the sum. As soon as the number becomes 00, we know that it does not have any more 11-bits, and we return the sum.
The key idea here is to realize that for any number nn, doing a bit-wise AND of nn and n - 1n−1 flips the least-significant 11-bit in nn to 00. Why? Consider the binary representations of nn and n - 1n−1.

public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

Date
2016/5/1 14:31:33