题意

，给你，求

题解

我们先打表看看这个函数的信息

1  1
2  3
3  1
4  7
5  1
6  3
7  1
8  15
9  1
10 3
11 1
12 7
13 1
14 3
15 1

观察发现的值都是二进制下都是1的情况。若我们考虑右移操作和除二，那么可以得到 ，那么对于求和序列中奇数都是1，我们对偶数部分进行提取出个2的操作可以得到。


即有如下递推式。


这样的话也就是说能够递归在的级别来求解答案了。

复杂度

时间复杂度
空间复杂度

代码

python

#
# 
# @param n int整型 
# @return long长整型
#
class Solution:
    def Sum(self , n ):
        # write code here
        if(n==1):
            return 1
        return n+2*self.Sum(n//2)

c++/c

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long Sum(int n) {
        // write code here
        if(n==1)
            return 1;
        return n+2*Sum(n/2);
    }
};