1000ms

Difficulty: 3

所属公司 : 阿里

时间 :2025年4月17日-阿里云(算法岗)

算法与标签>递归

会员或题库专享

请先，开通会员或购买题库阿里系机考题库，可解锁完整内容。

购买阿里系机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

解题思路

题目定义了一个能量计算过程：初始能量 $E=1$ ，反复执行：
- 若当前 $x$ 为奇数，则 $E \gets E \times 2$ ；
- $x \gets \lfloor x/2 \rfloor$ 。直到 $x=0$ 时停止，最终的能量值记为 $E(x)$ 。
观察上述操作本质：
- 每次判断 $x$ 是否为奇数，等价于检查 $x$ 二进制表示的最低位是否为 $1$ ；

题目内容

小蓝发现了一个有趣的数字游戏。给定一个非负整数 $x$ ，初始能量值为 $1$ 。随后反复执行以下操作：

若 $x$ 为奇数，则将当前能量值乘以 $2$ ；
将 $x$ 替换为 $\lfloor x/2 \rfloor$ （即向下取整的一半）。当 $x$ 变为 $0$ 时停止操作，此时得到的能量值记为 $E(x)$ 。

现有 $q$ 次询问，每次给定一个整数 $x$ ，请你计算并输出 $E(x)$ 的值。

约束条件：询问次数 $q$ 满足 $1 \le q \le 10^5$ ，每次询问的整数 $x$ 满足 $0 \le x \le 10^9$ 。