面试题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;
}
#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;
}
#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;
}
#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;
}
补充：软件开发 , C++ ,
