传统题 1000ms 256MiB

小胖寻路

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

现在有一颗标准完全二叉树(若父结点编号为 $x$ ,则它的两个子结点的编号分别为 $2x$  、$2x+1$)。现在小胖在 $1$ 号节点,如果她想去 $x$ 号节点,最少需要几步 ?

完全二叉树:若设二叉树的深度为 $k$ ,除第 $k$ 层外,其它各层 ($1$ ~ $k-1$ ) 的结点数都达到最大个数,第 $k$ 层所有的结点都连续集中在最左边。

例如(图为一棵标准的完全二叉树):

二叉树1.png

输入格式

第一行输入一个整数 $T$,表示输入的数据组数。

接下来的 $T$ 行,输入一个整数 $x$ ,表示小胖想去 $x$ 号节点。

$1 \le T \le 10^3$ ,$1 \le x  \le 10^3$

输出格式

对于每组数据,请在独立的行中输出一个整数 $num$ ,表示小胖从 $1$ 号节点走到 $x$ 号节点最少需要几步。

样例

4
1
2
4
666
0
1
2
9

福建师范大学第24届低年级程序设计竞赛(重现赛)

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2023-3-8 0:00
结束于
2023-12-24 15:00
持续时间
6999 小时
主持人
参赛人数
18