CSU - 1530 Gold Rush —— 二进制

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1530

对于一块2^n质量的gold。需要把它分成a质量和b质量（a+b=2^n），且每次分时是平分。问至少要平分多少次？

其实只需要知道最小分块的质量，就能知道它分了多少次。

比如当a=5， b=3，n=3时：

2^3: 1000

5    :  0101（3的情况也一样）

可知最小分块的质量为1。一块石头，它由8个质量分到1个质量，需要经过三次平分。

所以答案就是(2^n)的二进制的最高位1的位置减去a二进制中最低位1的位置。即：ans = （n+1） -  （a二进制从右数起0的个数+1） =  n -  a二进制从右数起0的个数

代码如下：

题解：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <sstream>

#include <algorithm>

using namespace std;

#define pb push_back

#define mp make_pair

#define ms(a, b)  memset((a), (b), sizeof(a))

#define eps 0.0000001

typedef long long LL;

const int INF = 2e9;

const LL LNF = 9e18;

const int maxn = 2000000+10;

const int mod = 1e9+7;

void solve()

{

    LL a,b,n;

    scanf("%lld%lld%lld",&n,&a,&b);

    LL t = 0;

    while(!(a&1))//只需找到最小的分块，就能知道分了多少次

    {

        t++;

        a >>= 1;

    }

    printf("%lld\n",n-t);

}

int main()

{

#ifdef LOCAL

    freopen("input.txt", "r", stdin);

//      freopen("output.txt", "w", stdout);

#endif // LOCAL

    int t;

    scanf("%d", &t);

    while(t--){

        solve();

    }

    return 0;

}