NYOJ 46-最少乘法次数(数论)

题目地址：

思路：能够化成二进制来求解。结果是最高位的位数-1+最高位后面1的个数。比如：对于3。它的二进制代码为11，就是用这个最高位(2-1)加上后面的1的个数(1个)。

用最高位1的目的是他能代表了转化的次数，由于2+2=4，4+4=8 8+8=16........

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-6;

const int maxn=21010;

char str[110];

int main()

{

    int T,n,i,j;

    int cnt;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        memset(str,0,sizeof(str));

        i=0;

        while(n/2!=0){

            str[i++]='0'+n%2;

            n=n/2;

        }

        str[i]='1';

        cnt=0;

        for(j=0;j<i;j++){

            if(str[j]=='1')

               cnt++;

        }

        printf("%d\n",strlen(str)-1+cnt);

    }

    return 0;

}