__builtin 开头系列函数

Matr1xqwq · 2023-11-06 19:08:34 · 个人记录

__builtin_ 系列函数是 GCC 的内建函数，性能极高。

本文介绍一些位运算相关的 __builtin_ 系列函数的常见应用及其记忆方法。

__builtin_ 拆开就是 built + in，也就是内建，很好记忆。

• __builtin_popcount(unsigned x)

返回 x 的二进制表示中 1 的个数。

用于快速求 popcount。

记忆方式：要我教你 popcount 怎么拼吗？

• __builtin_ctz(unsigned x)

返回 x 的二进制表示中末尾连续的 0 的个数。当 \boldsymbol{x=0} 时结果未定义。

显然 1 << __builtin_ctz(x) = lowbit(x)，不过经测试没啥优化，树状数组模板上表现地还不如 x & -x 快。

还有一个用处是除以最大的 2 的整数幂的因子。先求出 y = __builtin_ctz(x)，然后再让 x >>= y。这个可以用于 Binary GCD，凭什么更相减损术跑的这么快？这就是 __builtin_ctz 带给它的自信！

记忆方式：是 Count Trailing Zeroes 的缩写。

• __builtin_clz(unsigned x)

返回 x 的二进制表示中前导零的个数。当 \boldsymbol{x=0} 时结果未定义。

注意到 31 - __builtin_clz(x) = std::__lg(x)，ST 表模板中表现和 std::__lg 差不多。

记忆方式：是 Count Leading Zeroes 的缩写而非陈亮舟。

• __builtin_parity(unsigned x)

返回 x 的二进制表达中 1 的出现次数的奇偶性。1 表示奇数，0 表示偶数。

等效于 __builtin_popcount(x) & 1，本地测试速度差不多？感觉没啥用。

记忆方式：parity 有奇偶性的意思，于是我们愉快地掌握了一个新单词。

• __builtin_ffs(int x)

返回 x 的二进制表示中从低位开始第一个 1 的位置（最低位编号为 1）。当 \boldsymbol{x = 0} 时返回 \boldsymbol 0。

当 x\ne 0 时，__builtin_ffs(x) = __builtin_ctz(x) + 1。所以可以用 ffs 代替 ctz 来防止 UB。

记忆方式：是 Find First Set bit 的缩写，set bit 是一个词组，表示一个位。

最常用的还是 __builtin_popcount！

如果你想要传入 long long 或 unsigned long long 类型的 x，你应当在函数名后面加上 ll，例如 __builtin_popcountll。