Raising Bacteria
A box is initially empty. Each morning you can put any number of bacteria into the box, and each night every bacterium in the box splits into two. You want to see exactly \(x\) bacteria in the box at some moment.
Find the minimum number of bacteria you need to put into the box in total.
Constraints:
- \(1 \le x \le 10^9\)
Input:
- One integer \(x\).
Output:
- One integer — the answer.
Example:
Input:
5
Output:
2
(Put one bacterium in on the first morning. On the third morning there are \(4\) bacteria, and we put one more in, which gives \(5\).)
Solution
A bacterium that we put into the box \(d\) nights before the moment we look at the box becomes \(2^d\) bacteria. So the number of bacteria in the box is a sum of powers of two, one for each bacterium we put in.
Every number \(x\) is a sum of distinct powers of two in exactly one way: its binary representation. If a power of two appears twice in a sum, we can replace the two copies with one bacterium put in one night earlier, which uses fewer bacteria. So the answer is the number of 1 bits in the binary representation of \(x\).
For example, \(5 = 101_2 = 4 + 1\), so the answer is \(2\).
We count the 1 bits by removing the lowest set bit with x & (x - 1) until \(x\) becomes \(0\).
#include <iostream>
using namespace std;
int main() {
int x;
cin >> x;
int answer = 0;
while (x > 0) {
x = x & (x - 1); // remove the lowest set bit
answer++;
}
cout << answer << "\n";
}