#二叉树子树节点判断#北京大学机试#acwing

思路：本题给出总节点数n和子树根节点m，先使用位运算计算出每组数据对应的根节点层数和树的总层数，此时用两个变量分别逐层记录该子树某层最左和最右节点的编号，直到最底层。此时：

若总结点数落在左和右之中，则子树节点为完全n-1层＋多余节点，其他情况较为简单

接下来分别打印treenum即可

/*如上所示，由正整数 1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是 n。现在的问题是，结点 m所在的子树中一共包括多少个结点。
比如，n=12,m=3那么上图中的结点 13,14,15以及后面的结点都是不存在的，结点 m所在子树中包括的结点有 3,6,7,12，因此结点 m的所在子树中共有 4个结点。
输入格式：输入数据包括多行，每行给出一组测试数据，包括两个整数 m,n。最后一行 0 0 表示输入结束。
输出格式：对于每一组测试数据，输出一行，该行包含一个整数，给出结点 m所在子树中包括的结点的数目。
数据范围：1≤m≤n≤109,最多包含 20组数据。
输入样例：
3 12
0 0
输出样例：
4 */
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int n = 12, m = 3;
    while (1){
        scanf("%d%d", &m, &n);//输入数据
    if (m == 0 && n == 0) { break; }

    int i = 1;//从一层开始获取层数
    int begin_level = 0;//存储子树的根在第几层
    int final_level = 0;//存储树的总层数
    while (1) {
        if (m >= 1 << (i - 1) && m < 1 << i) {
            begin_level = i;
        }
        if (n >= 1 << (i - 1) && n < 1 << i) {
            final_level = i;
            break;
        }
        ++i;
    }

    int left_side = m;
    int right_side = m;
    for (i = begin_level; i < final_level; i++) {
        left_side = left_side * 2;
        right_side = right_side * 2 + 1;
    }
    int treenum = 0;
    if (left_side > n) { //说明m叶节点都在倒数第二层
        treenum = (1 << (final_level - begin_level)) - 1;
    } else if (right_side >= n) {//说明m子树有一部分叶节点在最后一层
        treenum = (1 << (final_level - begin_level)) + n - left_side;
    } else {
        treenum = (1 << (final_level - begin_level + 1)) - 1;//说明子树叶节点全在最后一层
    }
    printf("%d\n", treenum);
}
    return 0;
}