atcoder/ac-library

we should use std <bit> when C++20 is enabled

yosupo06 opened this issue · 1 comments

https://en.cppreference.com/w/cpp/header/bit C++20 provides bit manipulation functions as standard.

We should use these functions when C++20 is enabled

https://wandbox.org/permlink/tWmsqpe95cdZ5Gls
https://wandbox.org/permlink/RbNyFLtOEFZbWrFl

In wandbox & g++-12.1.0, __builtin_ctz is faster than std::bit::countr_zero when we don't specify -march=native (= without lzcnt). Probably this difference is due to the behavior of x=0 (__builtin_ctz:undefined vs countr_zero:bitwidth).

Because AtCoder don't plan to add -march=native option in new environment (ref: https://docs.google.com/spreadsheets/d/1HXyOXt5bKwhKWXruzUvfMFHQtBxfZQ0047W7VVObnXI/edit#gid=1305494725), we can't ignore this difference.

Options:

  • just ignore: This difference only affect the convolution function, and the effect should be small because we call builtin_ctz only O(N) times.
  • stop to use std::bit
  • ask AtCoder to add march=native