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

系统管理员 2022-11-18 02:06 482阅读 0赞

### 文章目录 ###

*  前言
 *  求解最大公约数
 *   *  自定义实现
     *  库函数
 *  计算一个整数的二进制表示中有多少个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;
    }

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

# 总结 #

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

--------------------

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

--------------------

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

[_ _]: https://blog.csdn.net/albertsh/article/details/115435926