C#LeetCode刷题之#191-位1的个数（Number of 1 Bits）

问题

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

输入: 11

输出: 3

解释: 整数 11 的二进制表示为 00000000000000000000000000001011

输入: 128

输出: 1

解释: 整数 128 的二进制表示为 00000000000000000000000010000000

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

Input: 11

Output: 3

Explanation: Integer 11 has binary representation 00000000000000000000000000001011

Input: 128

Output: 1

Explanation: Integer 128 has binary representation 00000000000000000000000010000000

示例

public class Program {

    public static void Main(string[] args) {

        var n = 11U;

        var res = HammingWeight(n);

        Console.WriteLine(res);

        n = 128U;

        res = HammingWeight2(n);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    public static int HammingWeight(uint n) {

        //10进制转2进制，除2取余法

        var count = 0;

        while(n != 0) {

            if(n % 2 != 0) count++;

            n /= 2;

        }

        return count;

    }

    public static int HammingWeight2(uint n) {

        //基本思路同 HammingWeight

        var count = 0;

        while(n != 0) {

            //10进制的1，2，3，4，5对应于2进制的1，10，11，100，101

            //由于2进制的特点，末位数在1，0之间循环

            //用 n 和 1 做“与运算”若值为1，必为奇数

            //即除2余1

            if((n & 1) == 1) count++;

            //2进制右移1位即10进制除2

            n >>= 1;

        }

        return count;

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

3

1

分析：

显而易见，以上2种算法的时间复杂度均为： $O(logn)$ 。

巴特西

C#LeetCode刷题之#191-位1的个数（Number of 1 Bits）

最新文章

热门文章