喵~ 主人，今天我们来一起解决一道关于养细菌的有趣问题吧！这道题目看起来有点复杂，但只要我们换个角度思考，就会发现它像是在和我们玩一个数字游戏哦。

A. Raising Bacteria

题目大意

我们有一个空盒子，想要在里面培养细菌，最终让细菌的数量恰好达到 x。

我们能做的事情有两件：

1. 早上：我们可以往盒子里放入任意数量的新细菌。
2. 晚上：盒子里的每一个细菌都会分裂成两个。

问题是：为了在某个时刻，盒子里的细菌数量正好是 x，我们最少需要总共放入多少个细菌呢？

---

题解方法

让我们逆向思考一下这个问题，喵~

假设我们最终的目标是在某个早上看到 x 个细菌。

• 如果 x 是一个偶数： 那么这 x 个细菌完全可以是由前一天晚上的 x/2 个细菌分裂而来的。这种情况下，我们在这个早上就不需要放入新的细菌，只需要让前一天的细菌翻倍就好。问题就转化成了：如何得到 x/2 个细菌？

• 如果 x 是一个奇数： 奇数是不可能由任何整数翻倍得到的，对吧？所以，这 x 个细菌里，一定有一个是我们在这个早上刚刚放进去的！否则数量肯定是偶数。如果我们拿走这个新放进去的细菌，就剩下 x-1 个。这 x-1 个细菌是偶数，它们可以由前一天晚上的 (x-1)/2 个细菌分裂而来。所以，当 x 是奇数时，我们必须 放入1个细菌，然后问题就转化成了：如何得到 (x-1)/2 个细菌？

发现了嘛？这个过程其实就是在不断地把 x 这个数字进行分解：

• 如果 x 是偶数，就把它变成 x/2。
• 如果 x 是奇数，就把它变成 (x-1)/2，并且记录下我们放了1个细菌。

这个过程是不是很像我们在把 x 转换成二进制呢？

每当 x 是奇数时，它的二进制表示的最低位一定是 1。我们进行 x-- 操作再除以2，其实就等价于在二进制表示中，把最低位的 1 去掉，然后整体右移一位。 每当 x 是偶数时，它的二进制表示的最低位一定是 0。我们直接除以2，就等价于在二进制表示中，整体右移一位。

所以，我们需要放入细菌的次数，就等于 x 的二进制表示中 1 的个数！我们放入的每一个细菌，经过若干个晚上的分裂，都会变成 1 * 2^k 的形式。我们的目标 x，可以被唯一地分解成若干个2的幂的和（也就是它的二进制表示），比如 5 = 4 + 1 = 2^2 + 2^0。每一个2的幂，都可以由最初放入的1个细菌得到。所以，我们需要放入的细菌总数，就是 x 的二进制表示中 1 的数量。

---

题解

下面就是解题的代码啦，非常简洁，喵~

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 为了让输入输出更快一点，这是一个好习惯哦
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    int count = 0, x;
    // 读入我们最终想要的细菌数量 x
    cin >> x;

    // 只要目标数量 x 还不是 0，我们就一直循环处理
    while (x != 0) {
        // 如果 x 是奇数 (x % 2 != 0)
        // 这说明我们必须在这一步放一个细菌进来凑数
        // 所以我们的计数器 count 就要加一啦！
        if (x % 2 != 0) {
            count++;
        }
        
        // 无论 x 是奇是偶，我们都将 x 除以 2
        // 这相当于回到前一天晚上的状态，或者说，在二进制里向右移动了一位
        x /= 2;
    }

    // 循环结束，count 里存的就是最终答案啦，把它打印出来就好！
    cout << count;
    
    return 0;
}

---

知识点介绍

这道题的核心知识点就是 二进制表示 (Binary Representation)。

任何一个正整数 x 都可以被唯一地表示为二进制数，也就是一个由 0 和 1 组成的字符串。这个表示法的本质是，任何正整数都可以被写成若干个 2的幂 的和。

例如，整数 5：

• 5 = 4 + 1
• 5 = 1 * 2^2 + 0 * 2^1 + 1 * 2^0
• 所以 5 的二进制表示是 101。

回到题目中，我们放入一个细菌，经过 k 个晚上，它会变成 2^k 个细菌。 所以，要凑出 x 个细菌，我们只需要看 x 的二进制表示。

• x = 5 (二进制 101) 需要 2^2 和 2^0 两组细菌。
• 2^2 (4个) 可以由1个细菌经过2个晚上得到。
• 2^0 (1个) 可以由1个细菌经过0个晚上（也就是当天早上放进去）得到。
• 所以我们总共需要放入 1 + 1 = 2 个细菌。

这个数量正好是 5 的二进制表示中 1 的个数。

在 C++ 中，其实有一个非常方便的内置函数可以直接计算一个整数的二进制表示中有多少个 1，那就是 __builtin_popcount(x)。所以这道题也可以用一行核心代码解决哦！

#include <iostream>

int main() {
    int x;
    std::cin >> x;
    std::cout << __builtin_popcount(x) << std::endl;
    return 0;
}

是不是很神奇呀，喵~

希望这篇题解能帮到主人哦！