
问题
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘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种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4052。