找规律

  • 当奇数比偶数大1的时候，odd^even=1
  • 当偶数比奇数大1的时候，取决于even的最左边的二进制1的位置『但是，为了简化代码，请自己找规律』 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long Sum(int n) {
        // write code here

        //找到规律
        //前偶后奇（偶数比奇数小），异或就是结果就是1
        //前奇后偶数，异或结果就是——根据后边偶数最左边的位置-1
        //第2个规律还能优化，看在哪个2^n周围

        long long sum=0;
        //奇数和偶数，
        if( n&1 )
        {
            sum=n/2+1;
        }
        else
        {
            sum=n/2;
        }

        for( int i=2; i<=n; i+=2 )
        {
            sum+=( i^(i-1) );
        }


        return sum;
    }
};