Full Binary Tree

#### Description

In computer science,a binary tree is a tree data structure in which each node has at most two children.
Consider an infinite full binary tree(each node has two children except the leaf nodes) defined as follows.
For a node labelled v,it‘s left children will be labelled 2v and it‘s right child will be labelled 2v+1.The
root is labelled 1. #### Input

First line contains n(1?≤?n?≤?10^5), the number of queries. Each query consists of two space separated integers i and j(1?≤?i,?j?≤?10^9) in one line.

#### Output

For each query, print the required answer in one line. #### AC代码

``````#include<bits/stdc++.h>
using namespace std;

long long Path(long long x,long long y);
int main(){
int n;
long long a,b;
cin >> n;
for(int t=0;t<n;t++){
scanf("%lld%lld",&a,&b);
//cin >> i >> j;
long long ans = Path(a,b);
cout << ans << endl;
}
return 0;
}

long long Path(long long x,long long y){

int step = 0;
while(x!=y){
if( x > y){
x = x/2;
step++;
}else if(x < y){
y = y/2;
step++;
}

}
return step;
}
``````

#### 错误集锦

``````long long Path(long long x,long long y){

int step = 0;
while(x!=y){
if(x % y == 0){
x /= 2;
step++;
continue;
}

if(y % x == 0){
y /= 2;
step++;
continue;
}
//cout << ":" << x << " " << y << " step = " << step << endl;
x = x/2;
y = y/2;
//cout << " x = " << x << " y = " << y << " step = " << step <<endl;
step += 2;

}
return step;
}
``````

Full Binary Tree