2252: Pick Balls

2252: Pick Balls

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	3s	8192K	373	158	Standard

Sherry is an excellent student of Jilin University. Today her teacher gives her a bag which is filled with M balls. She wants to pick all of them out. To make it interesting, she makes a rule as following:

Assume that the number of balls she picks last time is N,then she can only pick N, N/2 or N*2 balls this time. She can pick only one ball at the beginning. Of course, when N is equal to 1, she can not pick 0 ball this time.

Certainly she can always do that successfully no matter what value M is.But, to make it more difficult, she wants to use the fewest times to finish the task.

Could you help her? Thank you.:)

Input

There are T (T < 50000)lines in the input file.Each line there is a positive integer M (1 <= M <= 2 31-1) which indicates the total number of balls.

The end of the input will be indicated by an integer value of zero.

Output

For each integer in the input, you should print a integer in a single line which is the minimum times Sherry needs to pick these exactly M balls out.

Sample Input

2
3
8
0
      

Sample Output

2
2
4
      

hints:

2: 1 1
3: 1 2
8: 1 1 2 4      

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int cnt=0,temp=1,sum=0;
        while(sum<n)
        {
            cnt++;
            sum+=temp;
            temp*=2;
        }
        temp/=2;
        sum-=temp;
        sum=n-sum;
        cnt--;
        while(sum)
        {
            cnt+=sum/temp;
            sum%=temp;
            temp/=2;
        }
        cout<<cnt<<endl;
    }
    return 0;
}