二进制中1的个数

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

代码：

[cpp]
#include "stdafx.h"
#include
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;
}

#include "stdafx.h"
#include
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，以此类推。

代码：

[cpp]
#include "stdafx.h"
#include
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;
}

#include "stdafx.h"
#include
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，就可进行多少次这样的操作。显然可以减少循环次数。

代码：

[cpp]
#include "stdafx.h"
#include
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;
}

#include "stdafx.h"
#include
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;
}