LeetCode 191. Number of 1 Bits

[Woodyiiiiiii]

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

---

这道题求的是数值的二进制中1的个数，考察的当然是位运算。我的方法是32次循环，每次对数进行>>1操作右移1位，用&1(与1)运算求得每位是1的个数。& ^ ~等位运算会将数值自动进行二进制转换。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; ++i) {
            count += (n & 1);
            n >>= 1;
        }
        return count;
    }
}

第二种方法可以使用库函数。将数值用Integer.toBinaryString(n)方法转换成它的二进制字符串，然后遍历字符串后求字符1的个数。(下面的代码转换成了字符串数组，但其实可以不用)

public class Solution {
    public int hammingWeight(int n) {
        String s=Integer.toBinaryString(n); 
        String[] split=s.split(""); 
        int a=0; 
        for(int i = 0; i < split.length; i++) { 
            if (split[i].equals("1")) 
           { a++; }
        } 
        return a;  
    }
}

第三种方法是利用n & (n - 1)的性质——将二进制最右边的1位转换位0。所以只要计算能进行多少次这种运算就可以了。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; ++i) {
            count += (n & 1);
            n >>= 1;
        }
        return count;
    }
}

---

参考资料：

• https://leetcode.com/problems/number-of-1-bits/
• 小夕学算法——作业帮面试题