191. Number of 1 Bits

题目描述和难度

  • 题目描述:

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 :

输入: 11
输出: 3
解释: 整数 11 的二进制表示为 00000000000000000000000000001011

 

示例 2:

输入: 128
输出: 1
解释: 整数 128 的二进制表示为 00000000000000000000000010000000

思路分析

求解关键:解法很多,这里主要列出 5 种,都不难理解。其中位运算的部分只要举出几个具体的例子就清楚了。

参考解答

参考解答1:简单粗暴转换为二进制的字符串表示,数 “1” 的个数,但我想应该不是这道题要考的。

public class Solution {

    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        char[] binaryArr = Integer.toBinaryString(n).toCharArray();
        int count = 0;
        for (char b : binaryArr) {
            if (b == '1') {
                count++;
            }
        }
        return count;
    }
}

参考解答2:直接使用 Java 的库函数去数,但我想应该也是这道题要考的。

public class Solution2 {

    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

参考解答3:一位一位去数,但是要注意,使用左移的时候,要注意符号位,或者你可以使用无符号左移(参考解答6)。

public class Solution3 {

    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        if (n < 0) {
            n = n & 0x7fffffff;
            count++;
        }
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n = n >> 1;
        }
        return count;
    }
}

参考解答4:与运算的这个性质是比较常见的了,应该记住。

public class Solution4 {

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

参考解答5:与参考解答 3 相反,我们让 n 不变,使用 mask 一位一位去“数”有多少个 1。

public class Solution5 {

    public int hammingWeight(int n) {
        int mask = 1;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                count++;
            }
            mask<<=1;
        }
        return count;
    }
}

参考解答6:无符号左移数出 “1” 的个数。

public class Solution6 {

    public int hammingWeight(int n) {
        int mask = 1;
        int count = 0;
        while (n != 0) {
            count += (n & mask);
            n >>>= 1;
        }
        return count;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0191-number-of-1-bits ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com