题目描述

你是细菌的爱好者。你想在一个盒子里培养一些细菌。

最初，盒子是空的。每天早上，您可以将任意数量的细菌放入盒子中。而且到第二天早上，盒子里的每个细菌都会分裂成两个细菌。

您希望在某个早上准确地看到盒子中有 \(x\) 个细菌。（当然你也可以在最后的早上，放入一些细菌，使其正好等于 \(x\)）

请你计算出最少需要放入的细菌数量。

格式

输入格式

只有一个正整数 \(x（1≤x≤10^9）\)。

输出格式

一个正整数表示最少需要放入的细菌数量。

样例1

输入样例1

5

输出样例1

2

样例解释

可以在第 \(1\) 天早上放入 \(1\) 个细菌，到第 \(3\) 天早上盒子中会有 \(4\) 个细菌，我们可以再添加 \(1\) 个细菌，使其正好为 \(5\) 个细菌。总共放入 \(2\) 个细菌。

限制

时间：\(1s\) 空间：\(64M\)

共有 \(10\) 个测试点：

第 \(1\) 个测试点：\(1≤x≤10\)；

第 \(2\) 个测试点：\(1≤x≤10^2\)；

第 \(3\) 个测试点：\(1≤x≤10^3\)；

第 \(4\) 个测试点：\(1≤x≤10^4\)；

第 \(5\) 个测试点：\(1≤x≤10^5\)；

第 \(6\) 个测试点：\(1≤x≤10^6\)；

第 \(7\) 个测试点：\(1≤x≤10^7\)；

第 \(8\) 个测试点：\(1≤x≤10^8\)；

第 \(9,10\) 个测试点：\(1≤x≤10^9\)。

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T1\)