popcount 系列函数#

一般来说，这种内建函数针对于不同类型的参数会设计不同的函数签名。一般来说，在 __builtin_popcount 后直接加上数据类型的简写就可以得到针对这种数据类型的函数。目前仅支持 int、long 和 long long 类型，除 int 类型外，函数签名分别追加 l 和 ll。对于这个函数就是 __builtin_popcountl() 和 __builtin_popcountll()。后文不再对这点进行赘述。

$\texttt{popcount}$ 用来计算该数在二进制表示下 ${1}$ 的总个数。一般我们会写的 $\mathcal O(\log n)$ 做法如下：

1
int popcount(int x) {
2
    int res = 0;
3
    while (x) {
4
        if (x & 1) res++;
5
        x >>= 1;
6
    }
7
    return res;
8
}

GCC 在实现这些函数时自动将函数设为内联 inline，因此通常情况下会效率更高。主要还是不用自己写

例子：

1
__builtin_popcount(5)               // 返回2，因为十进制的5等于二进制的101
2
__builtin_popcountll(INT_MAX + 1)   // 返回33
3
__builtin_popcountll(LLONG_MAX - 1) // 返回62

值得注意的是，GCC 并没有计算二进制下 ${0}$ 个数的函数。不过实现起来也很简单，把上文代码里的 b & 1 的判断条件取反即可。

clz、ctz 系列函数#

__builtin_clz() 用来获取二进制表示下前导 ${0}$ 的个数；__builtin_ctz() 则是二进制末尾 ${0}$ 的个数。日常使用中前导 ${0}$ 的个数不常使用，较常使用的是 ctz 函数。

$\mathcal O(\log n)$ 做法如下：

1
int clz(int x) {
2
    int res = 0;
3
    if (x == 0) return 0;
4
    for (int i = 32; i >= 0; i--) {
5
        if ((x >> i) & 1) return res;
6
        else res++;
7
    }
8
    return 0;
9
}
10

11
int ctz(int x) {
12
    if (x == 0) return 0;
13
    for (int i = 0; i <= 32; i++) {
14
        if ((x << i) & 1) return i;
15
    }
16
    return 0;
17
}

例子：

1
__builtin_clz(7)        // 29
2
__builtin_ctz(20071126) // 1

ffs 系列函数#

__builtin_ffs() 函数用来求得二进制位下第一个非零位的下标（从低位到高位，下标从 ${1}$ 开始），除开特殊数字 ${0}$ 外，都有 $\texttt{ffs}=\texttt{ctz}+1$。因此：

1
int ffs(int x) {
2
    if (x == 0) return 0;
3
    return ctz(x) + 1;
4
}
5
// 或者...
6
int ffs(int x) {
7
    if (x == 0) return 0;
8
    for (int i = 0; i <= 32; i++) {
9
        if ((x >> i) & 1) return i + 1;
10
    }
11
    return 0;
12
}

例子：

1
__builtin_ffs(14)            // 2
2
__builtin_ffs(INT_MAX - 1)   // 2

parity 系列函数#

__builtin_parity() 函数用来求解二进制下 ${1}$ 的个数的奇偶性（二进制下 ${1}$ 的个数对 ${2}$ 取模）。在某些游戏的二进制文件校验里可能会用到（具体是检测二进制文件下 ${1}$ 或 ${0}$ 的个数来判断文件是否损坏或被篡改）。

1
int parity(int x) {
2
    return popcount(x) % 2;
3
}
4
// 或者...
5
int parity(int x) {
6
    int res = 0;
7
    while (x) {
8
        if (x & 1) res++;
9
        x >>= 1;
10
    }
11
    return res % 2;
12
}

例子：

1
__builtin_parity(26)          // 1
2
__builtin_parity(INT_MAX / 2) // 0

INFINITY 宏#

考虑这样一个情境：你在赛时写出了一个最短路代码，由于害怕数据爆 int，你选择改用 long long，并把最短路的 $\operatorname{dist}$ 数组初始化成了 $\texttt{LLONG\_MAX}$。但临近结束时，经过一通推算，你发现数据不会爆 int，反而发现开一个过大的 long long 数组可能会爆空间。你又将它改成了 int 类型。比赛结束后，你在场外忽然想起初始化还是一个爆 int 的值，果不其然喜提零分评测……

如何避免像上边那样写出一个爆类型的极大值，我的建议是使用 $\texttt{INFINITY}$ 宏定义。编译时将会替换为 __builtin_inff() 函数（其实本来应该放到上边那一栏的）。它的具体值会随数据类型的改变而改变，例如：

1
int a = INFINITY;
2
long b = INFINITY;
3
long long c = INFINITY;
4
double d = INFINITY;
5
float e = INFINITY;
6
short f = INFINITY;
7
bool g = INFINITY;
8
char h = INFINITY;
9

10
cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << ' ' << f << ' ' << g << ' ' << h << endl;
11
// 输出 2147483647 2147483647 9223372036854775807 inf inf 32767 1 〼 （char 值为 127，对应字符 '\177'）

可见使用这种方法可以优雅地避开上述情景中的窘境，助力 $AK$。对于特定数据类型（一般是 int 和 long long），$\texttt{INT\_MAX}$ 和 $\texttt{LLONG\_MAX}$ 也能帮到你。

__gcd 函数#

在数学题中经常需要我们去求两个数的最大公约数，一般来说我们会写欧几里得算法（辗转相除法）：

1
int gcd(int a, int b) {
2
    return b ? gcd(b, a % b) : a;
3
}

库函数中 __gcd() 也可以实现这一功能，它要求传入的两个参数是同一数据类型。这一点与 min()、max() 函数是相同的。

如果想要求解最小公倍数，则只需用两个数的乘积除以它们的最大公约数即可。