C++(g++ 7.5.0) 解法, 执行用时: 111ms, 内存消耗: 436K, 提交时间: 2023-01-11 13:29:19

#include<iostream>
#define ll long long int
ll dp(ll n){
	if(n==2||n==1)return 0;
	else if(n&1) return dp(n/2)+dp(n/2+1)+1;
	else return dp(n/2)*2;
}
using namespace std;
int main(){
	ll t,n;
	cin>>t;
	while(t--){
		cin>>n;
		cout<<dp(n)<<endl;
	}
}

JavaScript V8 解法, 执行用时: 237ms, 内存消耗: 7252K, 提交时间: 2023-07-19 15:57:33

let dfs = (n) => {
    if(n == 1 || n == 2) return 0;
    if(n & 1) return dfs(Math.floor(n/2)) + dfs(Math.floor(n / 2) + 1) + 1;
    else return dfs(n / 2) * 2
}

let t =readline()
while(t --) {
    let n = parseInt(readline())
    print(dfs(n))
}

C++(clang++ 11.0.1) 解法, 执行用时: 122ms, 内存消耗: 556K, 提交时间: 2023-07-30 09:52:05

#include<iostream>
using namespace std;
long long t,n;
long long f(long long n)
{
	if(n<=2)return 0;
	if(n&1)return f(n/2)+f(n/2+1)+1;
	return f(n/2)*2;
}
int main()
{
	cin>>t;
	while(t--){
		cin>>n;
		cout<<f(n)<<endl;
	}
    return 0;
}

Python3 解法, 执行用时: 224ms, 内存消耗: 9668K, 提交时间: 2021-11-28 15:59:11

d={1:0,2:0,3:1}
def f(n):
    if n in d:
        return d[n]
    if n%2==0:
        d[n]= f(n//2)*2
    else:
        d[n] = f(n//2)+f(n//2+1)+1
    return d[n]

T=int(input())
for i in range(T):
    n=int(input())
    print(f(n))

pypy3 解法, 执行用时: 753ms, 内存消耗: 27820K, 提交时间: 2022-12-23 17:21:43

def solve(n):
    if n==1 or n==2:return 0
    if n%2==0:return (solve(n>>1))<<1
    else:return solve(n>>1)+solve((n>>1)+1)+1
t=int(input())
while t>0:
    t-=1
    n=int(input())
    print(solve(n))