学步园

// Find1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream"

using namespace std;

int Count(int x);
int Count2(int x);

int _tmain(int argc, _TCHAR* argv[])
{
	int x;
	cin>>x;
	cout<<endl;
	cout<<"number of 1:"<<Count(x)<<endl;
	cout<<"number of 1:"<<Count2(x)<<endl;

	system("pause");
	return 0;
}

// 通过移位计算1的个数
// 算法负责度为O(sizeof(x))
int Count(int x)
{
	int sum = 0;
	while(x)
	{
		//int t = x & 0x0001;
		sum += x & 0x0001;
		// sum = sum + x & 0x0001; // 计算会出错，奇怪，可能是运算符优先级的问题
		x = x >> 1;
	}
	return sum;
}

// 通过直接统计1的个数
// 负责度 O(M)，M为1的个数
int Count2(int x)
{
	int num = 0;
	while(x)
	{
		x = x & (x - 1);
		num++;
	}
	return num;
}