首页 > 代码库 > 【剑指offer】二进制中1的个数

【剑指offer】二进制中1的个数

题目描述:


       请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。


分析描述:

     

       1、对一个整数的二进制形式,要想知道其中1的个数,首先想到的应该就是遍历整个二进制数,用到的方法当然就是移动了(包含左移或右移)。例如,用1来跟给定的整数做与运算。如果结果为1,则证明整数的二进制形式中,最右边的一位是1,如果结果是0,则证明整数的二进制形式中,最右边的一位是0。

int NumberOf1(int n)
{
       int count = 0;
       while(n){
               if(n & 1)
                         count++;
               n = n >> 1;
       }
}


          这种方法有一个bug,当n是负数时,右移一位的时候,不能简单地把最高位1移到第二位,因为如果移位前是个负数,仍然要保证移位后是个负数,因此移位后的最高位会设为1。如果一直做右移运算,最终整数会变成0xFFFFFFFF而陷入死循环。


         2、针对上面分析的bug,可以不对n移到,而是对1移动,每次与整数n做完与操作后,就左移一位1……反复左移,每次都能判断整数的某一位是否为1。

int NumberOf1(int n)
{
	int count = 0;
	unsigned int flag = 1;
	while(flag){
		if(n & flag)	
			count++;

		flag = flag << 1;
	}

	return count;
}

         3、还有一种更加巧妙的办法:当把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

int NumberOf1(int n)
{
	int count = 0;

	while(n)
	{
		++count;
		n = (n - 1) & n;	
	}

	return count;
}

         技巧:把一个整数减去1之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。