本文共 1032 字，大约阅读时间需要 3 分钟。

1. 题目

链接：

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

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

2. 解题

先算出 10 以内的 f(x)

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$;

class Solution {
   public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *      * @param n int整型      * @return long长整型     */    unordered_map
   
     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;    }};
   

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/111397239 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！