CODEWITHSUNDEEP
bit-manipulation
Ovi Poddar
Ovi Poddar

Reputation: 9

why number of set bits is needed?

i found a problem in codeforces 579/A:

You are a lover of bacteria. You want to raise some bacteria in a box.

Initially, the box is empty. Each morning, you can put any number of bacteria into the box. And each night, every bacterium in the box will split into two bacteria. You hope to see exactly x bacteria in the box at some moment.

What is the minimum number of bacteria you need to put into the box across those days?

Input The only line containing one integer x (1 ≤ x ≤ 109).

Output The only line containing one integer: the answer.

input : 5 output: 2 Note: For the first sample, we can add one bacterium in the box in the first day morning and at the third morning there will be 4 bacteria in the box. Now we put one more resulting 5 in the box. We added 2 bacteria in the process so the answer is 2.

My ques is, why number of set bit is used here to solve this?

Upvotes: 0

Views: 300

Answers (2)

Déjà vu
Déjà vu

Reputation: 28850

Each time you inject 1 bacteria, the number of germs will be 2n after n days. In order to reach a number N, you have to see its powers of 2.

5 is 22 + 20 or 4 + 1.

that is, in binary, 5 is 101, which is your injection planning!

To reach 5,

  • (1) add 1 bacteria
  • (0) after a day add 0 bacteria and
  • (1) after another day add 1 bacteria

The maximum acceptable number is 109 or 1101101 in binary. To reach 109, add 1 , then 1 after a day, then 0, then 1...

From the left,

  • the first 1 will give 26 after 6 days (64)
  • the second 1 will give 25 after 5 days (32)
  • the third 1 will give 23 after 3 days (8)
  • then... the 5 (4+1)

Finally, to know how many bacteria you'll have to inject, just count the number of 1 in the target binary number. That is, the number of bits set.

You may wonder why not injecting more than 1 at some day? Because the problem has no limitation on the number of days, so you'll "use" less bacteria by letting them multiply. That's the power of exponentiation!

Upvotes: 2

Alex Guteniev
Alex Guteniev

Reputation: 13689

Any bacteria put on given day would become one, two, four, eight and so on bacterias. It will not become three, for example. It is always a power of two. So, if desired number is not power of two, you need to make it as a sum of powers of two. Minimum amount of addends in such sum is such that no power of two is repeated, each power is used 0 or 1 times. Representation of number as such sum of powers of two is basically converting it to binary representation, and counting used powers of two is counting binary digits set to one.

Upvotes: 1

Related Questions