f(x)=x^ (x-1)让我想起了按位消去正整数n二进制形式中最右边的1，即x&(x-1),假设x的二进制中最右边的1在第i位(从个位开始数)，即x的二进制形式为b10..0，其中b表示x二进制第i位左边的形式，1右边一共有i-1个0，则x-1的二进制形式为b01...1，b的不变，第i位变成0,第i位右边的数字全部变成1, 则x&(x-1)按位运算的结果为b10...0&b01...1=b00...0(b的右边一共i个0)，对比x的二进制就发现消去了最右边的1，而x ^(x-1) = (b10...0)^(b01...0) = 11...1(一共i个1),对应的十进制为图片说明 -1.
如果n是奇数，则n的二进制个位数上一定是1，即i=1，则f(n)=2**1 -1=1
如果n是偶数，令n=2m，假设m的二进制最右边的1是在第i位,即b10...0, 则f(m)=图片说明 -1, n=2m,转换为二进制乘法n=10 m = 10 x b10...0 = xb10...00(此时1的右边一共i个0)，则n的二进制形式中最右边的1在第i+1位，则f(n) = f(2m) = 图片说明 -1=2ff(m) + 1
对f(n)的前n项求和也分奇偶进行;
如果n是奇数，令n=2m+1，则
Sum(n)=Sum(2m+1)=f(1) + f(2) + ... + f(2m+1)
=[f(1) + f(3) + ... + f(2m+1)] + [f(2) + f(4) + ... + f(2m)]
=m + 1 + [(2f(1) + 1) + (2f(2) + 1) + ... + (2f(m) + 1)]
=m + 1 + [2(f(1) + f(2) + ... + f(m)) + m]
=m + 1 + m + 2Sum(m)
=n + 2Sum(n//2)
如果n是偶数， 令n=2m，则
Sum(n)=Sum(2m)=f(1) + f(2) + ... + f(2m)
=[f(1) + f(3) + ... + f(2m-1)] + [f(2) +f(4) + ... + f(2m)]
=m + [(2f(1)+1) + (2f(2) + 1) +... + (2f(m) + 1)]
=m + m + 2[f(1) + f(2) + ... + f(m)]
=2m + 2Sum(m)
=n + 2Sum(n//2)
综上Sum(n) = n + 2Sum(n//2), Sum(1) = 1