Optimize CeilLg2 to O(1)

atcoder / ac-library

AtCoder Library

Creative Commons Zero v1.0 Universal

1.89k stars 240 forks source link

Optimize CeilLg2 to O(1) #139

Closed OIer1048576 closed 1 year ago

TumoiYorozu commented 2 years ago

__builtin_expect is wrong and cannot compile in either GCC or Clang.

Wrong:

if (__builtin_expect(n != 0)) return 32 - __builtin_clz(n - 1);

Collect:

if (__builtin_expect(n != 0, 1)) return 32 - __builtin_clz(n - 1);

Also, as a fundamental issue, __builtin_expect is not supported by Visual Studio, so it is better not to use __builtin_expect .

yosupo06 commented 1 year ago

Thanks,

the reason why we didn't optimize ceil_pow2 is, the cost of this function willn't be any bottleneck in current usage. (In contrast, we call bsf in the convolution function many times so we have to optimize this)

As already you discussed, __builtin_xxx is a non-standard function of C++ and we want to avoid to use as much as possible.