x_to_y_2

[编程题]x_to_y_2

热度指数：193 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个整数 $x,y$ ，你每次可以做如下两种操作之一：

令 $x= \lfloor\frac{x}{2}\rfloor$ 。
选择任意一个整数 $z$ ，令 $x= x \ |\ z$ 。

请问最少操作几次才可以让 $x$ 变成 $y$ 。

$\rule{4cm}{0.1pt}$

$^{\text{∗}}$ $|$ ：表示按位或，例如 $1\ |\ 2=3$ 。

输入描述:

本题有多组测试数据

第一行输入一个整数 ，表示数据组数。

对于每组测试数据：

每行输入两个整数 。

输出描述:

对于每组测试数据，输出把  变成  的最小操作次数。

示例1

输入

输出

说明

对于第一组测试数据，一种操作次数最少的方式是：先用操作 2，选 ，令 ，然后用操作 1，令 ，共 2 次操作。

算法知识视频讲解

C++

计应3254沈楚涵程

using ll = long long;
int main() {
    int t;
    cin >> t;
    while(t --) {
        ll x, y;
        cin >> x >> y;
        ll len = 0;
        while(x && (x & y) != x) {
            x >>= 1;
            len ++;
        }
        if(x == y) cout << len;
        else cout << len + 1;
        cout << endl;
    }
}

发表于 2025-12-19 20:42:02 回复(0)