直观比较 popcount 的效率差异

问题

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

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

枚举位

__builtin_popcount

#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';

}

-O2

#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';

}

-O2,-popcnt

#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

巴特西

直观比较 popcount 的效率差异

问题

枚举位

__builtin_popcount

-O2

-O2,-popcnt

效率

最新文章

热门文章