题目描述

你是一名细菌爱好者。你希望在一个盒子里养一些细菌。

起初，盒子是空的。每天早晨，你可以往盒子里放入任意数量的细菌。每到夜晚，盒子里的每个细菌都会分裂成两个细菌。你希望在某个时刻，盒子里正好有 $x$ 个细菌。

你在这些天里总共最少需要往盒子里放入多少个细菌？

输入格式

一行包含一个整数 $x$（$1 \leq x \leq 10^{9}$）。

输出格式

一行包含一个整数，表示答案。

说明/提示

对于第一个样例，我们可以在第一天早上放入一个细菌，在第三天早上盒子里会有 $4$ 个细菌。现在我们再放入一个细菌，盒子里就有 $5$ 个细菌。整个过程中我们一共放入了 $2$ 个细菌，所以答案是 $2$。

对于第二个样例，我们可以在第一天早上放入一个细菌，在第四天早上，盒子里会有 $8$ 个细菌。所以答案是 $1$。

由 ChatGPT 5 翻译

样例

5

2

8

1