牛客 XOR和（找规律）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

链接：https://ac.nowcoder.com/acm/contest/10166/C 来源：牛客网

牛牛最近学会了异或操作，于是他发现了一个函数 f ( x ) = x ⊕ ( x − 1 ) f(x)=xoplus (x-1) f(x)=x⊕(x−1)，现在牛牛给你一个数 n，他想知道 ∑ i = 1 n f ( i ) sum_{i=1}^n f(i) ∑i=1n​f(i) 的值是多少，请你告诉他。

代码语言：javascript复制

示例1
输入
4
返回值
12
备注:
1≤n≤10^9

2. 解题

先算出 10 以内的 f(x)

代码语言：javascript复制

i      f(i)      S(i)
1      1         1      
2      3         4       
3      1         5       
4      7        12       
5      1        13       
6      3        16       
7      1        17       
8     15        32    

发现x奇数时， f ( x ) = 1 f(x) = 1 f(x)=1; x偶数时， f ( x ) = 2 ∗ f ( x / 2 ) 1 f(x) = 2*f(x/2) 1 f(x)=2∗f(x/2) 1 S u m ( n ) = n 2 ∗ S u m ( n / 2 ) ; Sum(n) = n 2*Sum(n/2); Sum(n)=n 2∗Sum(n/2);

代码语言：javascript复制

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    unordered_map<int, long long> m;
    long long Sum(int n) {
        // write code here
        if(n == 1) return 1;
        if(m.find(n) != m.end()) return m[n];
        long long s = n 2*Sum(n/2);
        return m[n] = s;
    }
};

---

sum 函数

0 人点赞