ac-library icon indicating copy to clipboard operation
ac-library copied to clipboard

Optimize CeilLg2 to O(1)

Open OIer1048576 opened this issue 3 years ago • 1 comments

OIer1048576 avatar May 31 '22 10:05 OIer1048576

__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 .

TumoiYorozu avatar May 31 '22 11:05 TumoiYorozu

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.

related: https://github.com/atcoder/ac-library/issues/153

yosupo06 avatar Mar 06 '23 19:03 yosupo06