原始题目

A. Raising Bacteria

• time limit per test1 second
• memory limit per test256 megabytes
• inputstandard input
• outputstandard output

You are a lover of bacteria. You want to raise some bacteria in a box.

Initially, the box is empty. Each morning, you can put any number of bacteria into the box. And each night, every bacterium in the box will split into two bacteria. You hope to see exactly x bacteria in the box at some moment.

What is the minimum number of bacteria you need to put into the box across those days? ### Input The only line containing one integer x (1 ≤ x ≤ \(10^9\)).

Output

The only line containing one integer: the answer.

Examples

input

5

output

2

input

8

output

1

Note

For the first sample, we can add one bacterium in the box in the first day morning and at the third morning there will be 4 bacteria in the box. Now we put one more resulting 5 in the box. We added 2 bacteria in the process so the answer is 2.

For the second sample, we can put one in the first morning and in the 4-th morning there will be 8 in the box. So the answer is 1.

题目大意

初始盒子是空的，每天早晨你可以放任意个细菌到盒子盒子中去，每个细菌在盒子中每天分裂成两个。现在给出x，问最少需要放多少个细菌可以使 一定天数后盒子中细菌数量恰好为x。

解题思路

• 在不限制天数的情况下，恰巧达到x就让每个放入的细菌尽可能繁殖
• 将x用二进制表示，有多少个1即为答案。

解题代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
#define mp make_pair
#define np next_permutation
#define pb push_back
#define fi first
#define se second
#define eps 1e-8
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int maxn=1e5+5;
const int maxl=26;
ll n;
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n){
		ll ans=0;
		while(n){
			if(n&1) ans++;
			n>>=1;
		}
		cout<<ans<<endl;
	}
	
}

收获与反思

• 思维