前言

在解决一些算法题时，会遇到一些“嵌套”问题，也就是一个题目中包含多个小的算法知识点，比如计算一个整数的二进制表示中1的个数，或者计算两个数的最大公约数，如果这些小问题本身就是题目，那么就只能“手撕”了。

但是如果这些内容只是解决题目中的一小部分，我们其实是可以偷个懒的，有很多函数已经被纳入函数库，可以直接拿过来使用，接下来我们可以简单看几个。

求解最大公约数

自定义实现

求最大公约数的一种常用方法叫做辗转相除法，又名欧几里德算法(Euclidean algorithm)，算法本身并不复杂，可以写成如下逻辑实现：

int my_gcd(int x, int y) {
    while (y != 0) {
        int z = x % y;
        x = y;
        y = z;
    }
    return x;
}

或者简单写成递归的实现：

1
2
3

int my_gcd(int x, int y) {
    return y ? my_gcd(y, x%y) : x;
}

因为计算机处理加减法的性能要远高于计算乘除法，所以辗转相除法有很多变形实现，比如辗转相减、用移位运算代替除法计算等。

库函数

其实在C++17中，最大公约数计算已经被加到了函数库中，头文件为 <numeric>，直接调用 std::gcd() 就可以了，本身是一个模板函数，定义如下：

1 2	template< class M, class N> constexpr std::common_type_t<M, N> gcd(M m, N n);

计算一个整数的二进制表示中有多少个1

自定义实现

这也是一道经典的算法题了，常见的实现如下：

int count1(int n) {
    int cnt = 0;
    while (n > 0) {
        cnt++;
        n &= (n-1);
    }
    return cnt;
}

这种实现方法不能说最优解法，但是也算的上是一个优秀的实现思路了。

内建函数

关于二进制的形式的各种操作，GCC提供了一系列的builtin函数，可以实现一些简单快捷的功能来方便程序编写，并且可用来优化编译结果。

__builtin_popcount

1 2	// 返回n的二进制表示形式中1的个数 int __builtin_popcount(unsigned int n)

__builtin_ffs

1 2	// 返回n的二进制表示形式中最后一位1的是从后向前第几位 int __builtin_ffs(unsigned int n)

__builtin_clz

1 2	// 返回n的二进制表示形式中前导0的个数 int __builtin_clz(unsigned int n)

__builtin_ctz

1 2	// 返回n的二进制表示形式中结尾0个个数 int __builtin_ctz(unsigned int n)

__builtin_parity

1 2	// 返回n的奇偶校验位，即n的二进制表示形式中的1的个数模2的结果 int __builtin_parity(unsigned int n)

上述列举的这些函数参数都是 unsigned int 类型，如果参数为 usigned long 或者 usigned long long，只需要在函数名后面加上 l 或 ll 就可以了，比如 __builtin_popcountl。

遗憾的是，这些builtin函数一般没有可移植性，使用时要注意。

库函数

但值得庆幸的是，这些优秀的函数在C++20中得以转正，成为了C++的标准函数，比如 std::popcount，定义在头文件 <bit> 中，函数定义如下：

1 2	template<class T> constexpr int popcount(T x) noexcept;

更快速的源码

计算一个整数的二进制表示中包含1的个数，除了前面提到的 n &= (n-1) 外，还有下面这种变形的二分法实现：

unsigned popcount (unsigned int u)
{
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

采用这种二分法的实现，基本上可以媲美单字节打表的速度了，上述二分法是利用变量u来分组统计1的个数，两两合并到一起进而得到最后结果的。

总结

计算两个数的最大公约数可以在C++17环境下使用 std::gcd() 函数
计算一个整数二进制表示中1的个数可以在C++20环境下使用 std::popcount() 函数
__builtin 开头的函数是GCC提供的方便程序编写的函数，并且可用来优化编译结，但是使用时要注意不可移植性

==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

在繁华中自律
在落魄中自愈
谋生的路上不抛弃良知
谋爱的路上不抛弃尊严

2021-4-11 21:27:25