求 \(\sum\limits_{i=1}^{3\times 10^8} popcount(i)\) 。

仅考虑在暴力做法下的效率。

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int main(){
  n=3e8;
  for(int i=1;i<=n;i++){
    ans+=__builtin_popcount(i);
  }
  cout<<ans<<'\n';
}


#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int main(){
  n=3e8;
  for(int i=1;i<=n;i++){
    ans+=__builtin_popcount(i);
  }
  cout<<ans<<'\n';
}


#pragma GCC optimize(2)
#pragma GCC target("popcnt")
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int main(){
  n=3e8;
  for(int i=1;i<=n;i++){
    ans+=__builtin_popcount(i);
  }
  cout<<ans<<'\n';
}

方式

时间 1

时间 2

时间 3

平均值

枚举位

优化

__builtin_popcount

0.808s

0.876s

0.815s

0.833s

-O2

0.796s

0.702s

0.718s

0.739s

-O2, -popcnt

0.173s

0.175s

0.172s

0.173s