腾讯笔试2020.4.26

腾讯笔试2020.4.26：第k层祖先

给你一棵无限深度的满二叉树，节点的编号按层次依次编号，即第-层节点编号为1，第二层节点编号为2,3,
第三层节点编号为4,5, 6...以此类推。
接下来有Q次询问，每-一次询问让你找一 个编号为x的结点在深度为k的祖先节点的编号是多少?
输入描述:
输入第一行一个整数Q,代表有Q次询问
接下来Q行，每一行输入两个数x和k。
1<Q≤10^4
1<x<10^{18}
1<k<60
输出描述:
对于每一组测试数据，如果深度为K的祖先存在，输出
结点编号，不存在输出-1

输入示例

4
10 1
10 2
10 3
10 4

输出示例

1
2
5
-1

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int Q = sc.nextInt();
    for (int i = 0; i < Q; i++) {
        long x = sc.nextLong();
        int k = sc.nextInt();
        System.out.println(getFather(x,k));
    }
    sc.close();
}
//找父节点
public static long getFather(long x,int k){
    int nowDeep = getDeep(x);
    if (k >= nowDeep) {
        return -1;
    }
    //一层层往上找父节点，总共需要计算nowDeep - k次
    for (int i = 0; i < nowDeep - k; i++) {
        if (x % 2 == 0) {
            x = x >> 1;
        }else {
            x = (x - 1) >> 1;
        }
    }
    return x;
}
//计算当前节点x的所在层数
public static int getDeep(long x){
    int deep = 0;
    long i = 1;
    while(i <= x){
        i <<= 1;
        deep++;
    }
    return deep;
}