/*
*计算一个数的二进制中1的个数
*/
#include
int numberOf1InBinary(const unsigned int a);
int numberOf1InBinary_Mask(const unsigned int a);
int main(int argv , char** argc)
{
int a = 8 ;
printf("the number of 1 in %d of binary is %d\n",a,numberOf1InBinary(a));
return 0 ;
}
/*
*非常高效率的算法：时间复杂度为O(m)，其中m为1的个数
* 类似求补的方法，将右边的1不断清零，直至整个数为0。
*
*/
int numberOf1InBinary(const unsigned int a)
{
int number = a ;
int counter = 0 ;
while( number )
{
number = number && (number-1) ;
counter++ ;
}
return counter ;
}
/*
*普遍的：计算一个数的二进制中1的个数的方法
*算法思想：通过构造掩码，对原数或掩码不断移位来计算
时间复杂度为O(n),其中n为数的长度
*/
int numberOf1InBinary_Mask(const unsigned int a)
{
int number = a ;
int counter = 0 ;
int mask = 1 ;
while( number )
{
if( number&mask )
counter++ ;
number = number >> 1 ;
}
return counter ;
}
