[可能有用科技]GCC内建函数

前言

我不会卡常。

我也不会底层优化，这个博客就当个乐子吧。

GCC官方文档

内建函数

编译器 内置的函数，使用会导致减少兼容性和可移植性，于是不适合程序开发，但是 Linux 内核用到了内建函数。

不过 NOI 系列赛事用的编译器都一样，就可以放心用了。

内建函数功能很多，包括访问一些底层信息，这里只讲优化效率的一些函数。

__builtin_expect()

众所周知编译器需要进行合理的分支预测来进行对条件判断的优化，于是这个函数就是用来手动调整分治预测的。

例如 ：

if(__builtin_expect(foo == 0,0))
    puts("Never");
else puts("Gonna Give You Up");

意思就是告诉编译器 foo 为 0 大概率为伪，于是编译器会在这个 if-else 取指令时偏向 else。

使用实例 ：

在基于 fread() 的手写缓冲区的快读，需要经常判断是否已经读取完毕当前缓冲区的字符，如果已经读取完毕就需要进行下一次 fread()。

但是缓冲区通常开得比较大，那么就将判断缓冲区已满 if 加上 __builtin_expect(...,0) 代表这个条件通常不成立。

__builtin_prefetch()

__builtin_prefetch(Never) 把指针 Never 指向的数据加入 cache 进行预取，如果该数据已经加入 cache 内反而会降低效率。

使用实例 ：

不敢用，怕把 cache 炸了。

__builtin_clz()

查询一个 unsigned 类型的前导零个数，传入 0 时为 UB。

同样的，对于 long 有 __builtin_clzl()，

对于 long long 有 __builtin_clzll()。

使用实例 ：

一个数以 2 为底的对数向下取整就是其二进制位数减去 1。

那么对于 32 位整型，直接 31 - __builtin_clz(NeverGonna) 即可。

然后这个方法比计算浮点数的 log2() 计算速度快，比起预处理不需要内存寻址，也快。

__builtin_ctz()

查询一个 unsigned 类型的结尾零个数，传入 0 时为 UB。

同样的，对于 long 有 __builtin_ctzl()，

对于 long long 有 __builtin_ctzll()。

使用实例 ：

众所周知更相减损法求 \gcd 的时候首先需要一直除 2 直到除不了为止。

这里直接用这个方式把结尾零全部右移掉，剩下的一定是个奇数。

inline int gcd(int a,int b) {
    if(!a || !b) return a | b;
    int k = __builtin_ctz(a | b);
    a >>= k,b >>= k;
    a >>= __builtin_ctz(a);
    b >>= __builtin_ctz(b);
    while(a && b) {
        if(a > b) std::swap(a,b);
        b -= a;
    }
    return a << k;
}

__builtin_popcount()

__builtin_popcount(GiveYouUp) 求出整型 GiveYouUp 二进制形式下 0 的个数。

同样的，对于 long 有 __builtin_popcountl()，

对于 long long 有 __builtin_popcountll()。

使用实例 ：

需要的时候自然用上了。

__builtin_parity()

__builtin_parity(Gonna) 求出整型 Gonna 二进制形式下 0 的个数的奇偶性。

比 __builtin_popcount() & 1 更快。

使用实例 ：

需要的时候自然用上了。

__builtin_ffs()

求一个整型二进制最低位 1 的位数。

就是 __builtin_ctz() + 1。