当前位置：首页 > news >正文

C++中一些可以在偷懒时直接使用的函数

news 来源：原创 2024/4/28 23:17:43

文章目录

前言
求解最大公约数
- 自定义实现
- 库函数
计算一个整数的二进制表示中有多少个1
- 自定义实现
- 内建函数
- - __builtin_popcount
  - __builtin_ffs
  - __builtin_clz
  - __builtin_ctz
  - __builtin_parity
- 库函数
- 更快速的源码
总结

前言

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

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

求解最大公约数

自定义实现

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

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

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

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

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

库函数

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

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

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

__builtin_ffs

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

__builtin_clz

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

__builtin_ctz

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

__builtin_parity

// 返回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> 中，函数定义如下：

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;
}