解题思路

我们把“兑换”过程视为一棵二叉树：每次把一张面额为 x>1 的钞票拆成 ⌊x/2⌋、x mod 2、⌊x/2⌋，其中当且仅当 x 为偶数时会产生一张 0。因此，问题等价于：整棵树里一共分裂了多少次“偶数面额”的节点。

设答案为 f(n)。直接递推可得

• f(0)=f(1)=0

• n>1 时：

  • 若 n 为偶数：f(n) = 2*f(n/2) + 1（本次分裂产生 1 个 0，两张 n/2 继续分裂）

题目内容

小明手头有一个面额为 $n$ 的钞票，他试图钱生钱，魔神用语言欺骗小明将钞票给了魔神。魔神承诺拿到钞票后，会将钞票拆分成面额分别为 $n/2$，$n$ $mod$ $2$，$n/2$ 的钞票（显然钞票的总金额没有发生变化，而且会出现面值为 $0$ 的钞票），然后退回给小明。小明已经失去了理智，他会将所有面额大于 $1$ 的钞票与魔神兑换，请问他最后会有几张面额为 $0$ 的钞票。$n$ $mod$ $2$ 指 $n$ 除以 $2$ 的余数，例如 $3$ $mod$ $2 = 1，4$ $mod$ $2 = 0$ 。 $[x]$ 指最大且不大于 $x$ 的整数

输入描述

数据包括多组样例。首先输入 $T$，表示一共有 $T$ 组样例。样例最多 $100$ 组。每组输入包括一个整数 $n$ ，保证 $(1 ≤ n ≤ 10^{18})$

输出描述

对于每组数据，输出一行，包括一个正整数，表示一共有多少 $0$ 出现。

样例1

输入

1
100

输出

27

说明

$100$ 会分为 $2$ 个 $50$ 和 $1$ 个 $0$，然后分为 $4$ 个 $25$ 和 $2$ 个 $0$，然后分为 $8$ 个 $12$ 和 $4$ 个 $1$，然后分为 $16$ 个 $6$ 和 $8$ 个 $0$，然后分为 $32$ 个 $3$ 和 $16$ 个 $0$，接着分为 $64$ 个 $1$ 和 $32$ 个 $1$，至此共产生了 $27$ 个 $0$ 。