「黑历史」GCC自带位运算系列函数

Aleph1022

2018-07-29 22:30:02

Tech. & Eng.

谈到GCC的黑科技，大家想到的一定是这句：

#pragma GCC optimize (3)//吸氧

抑或是这句：

#pragma GCC diagnostic error "-std=c++11"//C++11

然而又有多少人知道__builtin_xxx()这群神奇的存在？

举个栗子：树状数组的核心思想就是一个叫做lowbit()的函数，它是这样写的：

inline int lowbit(const int &x)
{
    return x & -x;
}

什么，你说长？你嫌慢？

#define lowbit(x) ((x) & -(x))

什么，你还是不想自己写？非得用内置函数？

那么恭喜你，这是你新的出路：

lowbit(x) == (1 << __builtin_ctz(x))

当然，对于lowbit()函数，大家看不到什么好处（喜欢这样用的才有问题吧(-_-)）

再举一个栗子：P2704， 一道状压DP入门题目，它要求输出：

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

那么，DP的时候，对于每一行的状态，若它在二进制下的第i位以0表示不放，以1表示放的话，我们就得统计它二进制下1的个数，于是考虑用一个inline的函数count()来统计：

inline int count(int x)//摘自本人AC代码
{
    int ret = 0;
    while(x)
    {
        ret += x & 1;
        x >>= 1;
    }
    return ret;
}

统计一下，这里一共有135字节的内容。

使用它的代码长这样：sum[tot] = count(i);，改一下，变成这样：sum[tot] = __builtin_popcount(i);

有人又要钻牛角尖：就算你把函数定义的码量给省了，但是你每次调用函数都会增加strlen("__builtin_pop") == 13字节的码量啊？

那还不简单define下就好了

除了上述函数，本人另外还整理了一部分用得到的__builtin_系列函数：

另外以上函数的唯一参数都为unsigned int类型，并且都有unsigned long long版本，即在函数名后面加上ll，Like __builtin_popcountll(x)。

对于其他的__builtin_系列函数，可以自行查阅GNU C所提供的文档

又双叒叕及：感谢@ComeIntoPower 管理员大大普及：可以在程序开头加入这样一行：

#pragma GCC target ("popcnt")

根据大大的说法，这条GCC指令可以让__builtin_popcount被编译器识别为一条指令。

什么用呢？就是加速！时 间 减 半！它本身就够快了，还可以加速%%%，鄙人真是孤陋寡闻。

注意：有些计算机可能不支持popcnt指令，然后GCC就会GG。（大部分计算机都有）

还有一点注意，有一种说法是NOI系列赛事中禁止使用以下划线开头的函数，因此在NOI系列比赛中使用有风险，这只是给平时做题提供一些便利

此外，既然是黑科技自然有地方不给用，我已经测试了各大OJ对于该系列函数的支持情况：（务必选用G++/GCC作为编译器）