求完全二叉树某结点的子树结点数

题目描述：

完全二叉树的子树问题描述对一棵完全二叉树，采用自上而下、自左往右的方式从1开始编号，我们已知这个二叉树的最后一个结点是n，现在的问题是结点m所在的子树一共包括多少个结点？输入格式 输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。0 0表示输入结束。输出格式 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

样例输入：

3 12
0 0

样例输出：

4

案例代码

题目要求计算完全二叉树中某个节点所在子树的节点数量。我们可以利用完全二叉树的性质来解决这个问题。

完全二叉树的性质：

1. 对于完全二叉树的第 i 个节点（1-based），其左子节点为 2i，右子节点为 2i+1。
2. 完全二叉树的最后一个节点 n 的父节点为 n/2（取整）。

根据以上性质，我们可以从给定的节点 m 开始，向上遍历到根节点，同时计算每一层的节点数量，直到遍历到节点 1。最终得到的节点数量即为所求。

下面是使用 C 语言实现的解答：

#include <stdio.h>

int countNodes(int m, int n) {
    int count = 0;
    while (m <= n) {
        count += n - m + 1;  // 当前层的节点数量
        m *= 2;             // 左子节点
        n = n * 2 + 1;      // 右子节点
    }
    return count;
}

int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) == 2) {
        if (m == 0 && n == 0) {
            break;
        }
        int result = countNodes(m, n);
        printf("%d\n", result);
    }
    return 0;
}