20: XOR Sum

uuuouou

问题可以转化为统计1~N这N个数中，每一个位上一共出现了多少次1，对于一个数x，其每一位上出现1的个数用f(x)表示，如果其为1的最高bit是n，则有f(x) = f((1<<n)-1) + f((x^(1<<n))+1)，其中+表示统计结果的对应项相加

1. #include <vector>
   
2. using std::vector;
   
3. 
   
4. class Solution {
   
5. public:
   
6.         typedef long long LL;
   
7.         static const int MAX = 60;
   
8.         static const LL  ONE = 1;
   
9.         void count(vector<LL>& c, LL x){
   
10.                 if(!x) return;
    
11.                
    
12.                 int n = 0;
    
13.                 for(int i = 0; i < MAX; ++i){
    
14.                         if(x & (ONE << i)) n = i;
    
15.                 }
    
16.                 LL y = x ^ (ONE << n);
    
17.                 c[n] += y + 1;
    
18.                 for(int i = 0; i < n; ++i){
    
19.                         c【i】 += ONE << (n-1);
    
20.                 }
    
21.                 count(c, y);
    
22.         }
    
23.         long long xorSum(long long x) {
    
24.                 vector<LL> c(MAX, 0);
    
25.                 count(c, x);
    
26.                 LL res = 0;
    
27.                 for(int i = 0; i < MAX; ++i){
    
28.                         if(c【i】 & 1) res |= ONE << i;
    
29.                 }
    
30.                 return res;
    
31.         }
    
32. };

复制代码

Sophia

赞赞的~~~下次我们会举办一次测试代码运行速度的比赛~~~欢迎参加~~大米送上~~~

h1031411

nice