Raising Bacteria
صندوق فارغ في البداية. في كل صباح يمكنك أن تضع أي عدد من البكتيريا في الصندوق، وفي كل ليلة تنقسم كل بكتيريا في الصندوق إلى اثنتين. تريد أن ترى بالضبط \(x\) بكتيريا في الصندوق في لحظة ما.
أوجد أقل عدد من البكتيريا يجب أن تضعه في الصندوق إجمالًا.
القيود:
- \(1 \le x \le 10^9\)
الإدخال:
- عدد صحيح واحد \(x\).
المخرجات:
- عدد صحيح واحد — الجواب.
مثال:
الإدخال:
5المخرجات:
2(نضع بكتيريا واحدة في صباح اليوم الأول. في صباح اليوم الثالث يكون في الصندوق \(4\) بكتيريا، فنضع واحدة أخرى، فيصبح العدد \(5\).)
الحل
البكتيريا التي نضعها في الصندوق قبل \(d\) ليلة من لحظة النظر إلى الصندوق تصبح \(2^d\) بكتيريا. لذلك عدد البكتيريا في الصندوق هو مجموع قوى للعدد اثنين، قوة واحدة لكل بكتيريا وضعناها.
كل عدد \(x\) يُكتب مجموعًا لقوى مختلفة للعدد اثنين بطريقة واحدة فقط: تمثيله الثنائي. إذا ظهرت قوة للعدد اثنين مرتين في المجموع، يمكننا استبدال النسختين ببكتيريا واحدة نضعها قبل ليلة إضافية، وهذا يستخدم عددًا أقل من البكتيريا. لذلك الجواب هو عدد البتات 1 في التمثيل الثنائي للعدد \(x\).
مثلًا \(5 = 101_2 = 4 + 1\)، لذلك الجواب \(2\).
نعدّ البتات 1 بإزالة أدنى بت مضبوط باستخدام x & (x - 1) حتى يصبح \(x\) صفرًا.
#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";
}