A_Johnny_and_Ancient_Computer.cpp

#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#define nl '\n'
#define sp ' '
#define pi 2 * acos(0.0)

// Types of declarations /////////////////////////////////
#define ui unsigned int
#define us unsigned short
#define ull unsigned long long
#define ll long long
#define ld long double
#define vstr vector<string>
#define vll vector<ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define pii pair<int, int>

// Odd Even /////////////////////////////////////////////
bool odd(ll num) { return ((num & 1) == 1); }
bool even(ll num) { return ((num & 1) == 0); }

//////////////////////////////////////////////////////// Prime

bool isPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

///////////////////////////////////////////////////////// LCM GCD
long long gcd(long long a, long long b)
{
    while (b != 0)
    {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
long long lcm(long long a, long long b)
{
    return (a / gcd(a, b)) * b;
}
////////////////////////////////////////////////////////// SQR ROOT

long long sqrt(long long x)
{
    long long s = 0, e = 2e9, res = s;
    while (s <= e)
    {
        long long m = (s + e) / 2;
        if (m * m <= x)
            res = m, s = m + 1;
        else
            e = m - 1;
    }
    return res;
}

/*
check all edge cases
check for integer overflow
check for corner cases
check for constraints
check for time complexity
check for array bounds
check for negative values
*/

/*----------------------------------------------------------------------------*/
void solve()
{
    ll ans = 0;
    ll a, b;
    cin >> a >> b;

    if (a == b)
    {
        cout << "0" << "\n";
    }
    else
    {
        if (a < b)
            swap(a, b);

        ans = 0;
        while (a > b)
        {
            if (a / 8 >= b && a % 8 == 0)
            {
                ans = ans + 1;
                a = a / 8;
            }
            else if (a / 4 >= b && a % 4 == 0)
            {
                ans += 1;
                a = a / 4;
            }
            else if (a / 2 >= b && a % 2 == 0)
            {
                ans += 1;
                a = a / 2;
            }
            else
            {
                break;
            }
        }

        if (a == b)
        {
            cout << ans << "\n";
        }
        else
        {
            cout << "-1" << "\n";
        }
    }
}

/*
Johnny has recently found an ancient, broken computer. The machine has only one register, which allows one to put in there one variable. Then in one operation, you can shift its bits left or right by at most three positions. The right shift is forbidden if it cuts off some ones. So, in fact, in one operation, you can multiply or divide your number by 2
, 4
 or 8
, and division is only allowed if the number is divisible by the chosen divisor.

Formally, if the register contains a positive integer x
, in one operation it can be replaced by one of the following:

x⋅2
x⋅4
x⋅8
x/2
, if x
 is divisible by 2
x/4
, if x
 is divisible by 4
x/8
, if x
 is divisible by 8
For example, if x=6
, in one operation it can be replaced by 12
, 24
, 48
 or 3
. Value 6
 isn't divisible by 4
 or 8
, so there're only four variants of replacement.

Now Johnny wonders how many operations he needs to perform if he puts a
 in the register and wants to get b
 at the end.

Input
The input consists of multiple test cases. The first line contains an integer t
 (1≤t≤1000
) — the number of test cases. The following t
 lines contain a description of test cases.

The first and only line in each test case contains integers a
 and b
 (1≤a,b≤1018
) — the initial and target value of the variable, respectively.

Output
Output t
 lines, each line should contain one integer denoting the minimum number of operations Johnny needs to perform. If Johnny cannot get b
 at the end, then write −1
.

Example
InputCopy
10
10 5
11 44
17 21
1 1
96 3
2 128
1001 1100611139403776
1000000000000000000 1000000000000000000
7 1
10 8
OutputCopy
1
1
-1
0
2
2
14
0
-1
-1
Note
In the first test case, Johnny can reach 5
 from 10
 by using the shift to the right by one (i.e. divide by 2
).

In the second test case, Johnny can reach 44
 from 11
 by using the shift to the left by two (i.e. multiply by 4
).

In the third test case, it is impossible for Johnny to reach 21
 from 17
.

In the fourth test case, initial and target values are equal, so Johnny has to do 0
 operations.

In the fifth test case, Johnny can reach 3
 from 96
 by using two shifts to the right: one by 2
, and another by 3
 (i.e. divide by 4
 and by 8
).
 */

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
        solve();
}