面试题10：二进制中1的个数

方法一：判断整数二进制表示中最右边一位是否为1，接着把整数右移一位判断倒数第二位是否为1，以此类推，直到整数变成0为止。

代码：

#include "stdafx.h"
#include <iostream>
using namespace std;

 int CountOf1(int n)
 {
 	int nCount = 0;
 
 	while (n)
 	{
 		if (n & 1)
 		{
 			nCount++;
 		}
 
 		n = n >> 1;
 	}
 
 	return nCount;
 }

int _tmain(int argc, _TCHAR* argv[])
{
	cout << CountOf1(7) << endl;
    system("pause");
	return 0;
}

缺点：如果输入的数为负数，若一直做右移运算，最终将陷入死循环。

方法二：为避免陷入死循环，可以不右移输入的数字，先将输入数字和1做与运算，判断最低位是否为1，接着将1左移一位，判断倒数第二位是否为1，以此类推。

代码：

#include "stdafx.h"
#include <iostream>
using namespace std;

 int CountOf1(int n)
 {
 	int nCount = 0;
 	unsigned int flag = 1;
 	while (flag)
 	{
 		if (n & flag)
 		{
 			nCount++;
 		}
 
 		flag = flag << 1;
 	}
 
 	return nCount;
 }

int _tmain(int argc, _TCHAR* argv[])
{
	cout << CountOf1(7) << endl;
    system("pause");
	return 0;
}

缺点：循环次数等于整数二进制的位数，32为的整数需要循环32次。

方法三：把整数减去1，在和原整数做与运算，会把整数最右边的一个1变成0，那么一个整数的二进制表示中有多少个1，就可进行多少次这样的操作。显然可以减少循环次数。

代码：

#include "stdafx.h"
#include <iostream>
using namespace std;

int CountOf1(int n)
{
	int nCount = 0;

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

	return nCount;
}


int _tmain(int argc, _TCHAR* argv[])
{
	cout << CountOf1(7) << endl;
    system("pause");
	return 0;
}

面试题10：二进制中1的个数

相关推荐