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

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) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4052

发表评论

登录后才能评论