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种算法的时间复杂度均为：  。