内建函数、二分查找函数

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

内建函数、二分搜索函数

1. 内建函数

__builtin 函数是 GCC 的内建函数，用于提高代码的执行效率，是一种相当神奇的位运算函数。

1.1. __builtin_ctz()

count trailing zeros 的缩写，即计算末尾的零的个数。

__builtin_ctz() 函数用于返回一个整数的二进制表示中从右往左第一个1的位置，返回基于0的索引位置。 或者说，返回括号内数的二进制表示数末尾0的个数。

1
2
3
4
int __builtin_ctz(unsigned int x);
int __builtin_ctzll(unsigned long long x);

int res = __builtin_ctz(18); // 二进制为 10010，返回 1, res = 1

1.2. __builtin_clz()

count leading zeros 的缩写，即计算前导零的个数。

__builtin_clz() 函数用于返回一个整数的二进制表示中从左往右第一个1的位置，返回基于0的索引位置。 或者说，返回括号内数的二进制表示数前导0的个数。

1
2
3
4
int __builtin_clz(unsigned int x);
int __builtin_clzll(unsigned long long x);

int res = __builtin_clz(18); // 二进制为 10010，返回 32 - 5 = 27, res = 27

1.3. __builtin_popcount()

population count 被称为汉明权重或者位计数，即计算二进制表示中1的个数。

__builtin_popcount() 函数用于返回一个整数的二进制表示中1的个数，返回值为整数。

1
2
3
4
int __builtin_popcount(unsigned int x);
int __builtin_popcountll(unsigned long long x);

int res = __builtin_popcount(18); // 二进制为 10010，返回 2, res = 2

1.4. __builtin_parity()

parity 是奇偶性的意思。

__builtin_parity() 函数用于返回一个整数的二进制表示中1的个数的奇偶性，奇数返回1，偶数返回0。

1
2
3
4
int __builtin_parity(unsigned int x);
int __builtin_parityll(unsigned long long x);

int res = __builtin_parity(18); // 二进制为 10010，返回 0, res = 0

1.5. __builtin_ffs()

find first set 的缩写，即查找第一个1的位置。

__builtin_ffs() 函数用于返回一个整数的二进制表示中从右往左第一个1的位置，返回基于1的索引位置。

1
2
3
4
int __builtin_ffs(int x);
int __builtin_ffsl(long x);

int res = __builtin_ffs(18); // 二进制为 10010，从右往左第一个 1 的位置为 2，返回 2, res = 2

1.6. __builtin_sqrt()

__builtin_sqrt() 函数用于返回一个整数的平方根，返回值为整数。

1
2
3
4
5
int __builtin_sqrt(int x);
int __builtin_sqrtf(float x);

int res = __builtin_sqrt(16); // 返回 4, res = 4
float res = __builtin_sqrtf(16.0); // 返回 4.0, res = 4.0

与 sqrt() 函数相比，__builtin_sqrt() 函数的返回值为整数，且返回值为平方根的整数部分。 由于__builtin_sqrt() 函数是通过移位运算实现的，所以运算速度更快。

1
2
int __builtin_parity(unsigned int x);
int __builtin_parityll(unsigned long long x);

2. 二分搜索函数

2.1. lower_bound()

lower_bound() 函数用于在有序序列中查找第一个大于等于给定值的元素，返回值为迭代器。

1
2
3
4
5
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
auto it = std::lower_bound(vec.begin(), vec.end(), 3) - vec.begin(); // it = 2

2.2. upper_bound()

upper_bound() 函数用于在有序序列中查找第一个大于给定值的元素，返回值为迭代器。

1
2
3
4
5
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val);

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
auto it = std::upper_bound(vec.begin(), vec.end(), 3) - vec.begin(); // it = 3

binary_search() 函数用于在有序序列中查找给定值是否存在，返回值为 bool 类型。

1
2
3
4
5
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
bool result = std::binary_search(vec.begin(), vec.end(), 3); // result = true

2.4. equal_range()

equal_range() 函数用于在有序序列中查找等于给定值的元素的范围，返回值为一对迭代器。

1
2
3
4
std::vector<int> vec = {1, 2, 2, 3, 3, 3, 4, 5, 6};
auto range = std::equal_range(vec.begin(), vec.end(), 3);
auto start = range.first - vec.begin();     // start = 3
auto end = range.second - vec.begin();      // end = 6

2.5. nth_element()

nth_element() 函数用于对序列进行部分排序，使得第 n 个元素为序列中第 n 大的元素，且序列中的其他元素没有特定的顺序。

适用于求解第 k 大或第 k 小元素的问题。

1
2
3
4
5
6
7
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

std::vector<int> vec = {3, 2, 1, 5, 6, 4};
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());//在[begin, end)中将索引为2的元素放到正确的位置，
// vec = {1, 2, 3, 5, 6, 4}                               //即 左边的元素都不大于索引为2的元素，右边的元素都不小于索引为2的元素

2.6. merge()

merge() 函数用于合并两个不同的有序序列，如：[1, 3, 5] 和 [2, 4, 6] 合并后为 [1, 2, 3, 4, 5, 6]。
merge() 函数将合并后的序列存储到另一个序列中。

1
2
3
4
5
6
7
8
9
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result;

std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(result));
// result = {1, 2, 3, 4, 5, 6}

2.7. inplace_merge()

inplace_merge() 函数用于合并同一数组中的两个有序序列。与 merge() 函数不同的是，inplace_merge() 函数将合并后的序列直接覆盖到原序列中。 各参数为：first 为第一个有序序列的起始迭代器；middle 为第一个有序序列的结束迭代器；last 为第二个有序序列的结束迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};

vec1.insert(vec1.end(), vec2.begin(), vec2.end());
std::inplace_merge(vec1.begin(), vec1.begin() + 3, vec1.end());
// vec1 = {1, 2, 3, 4, 5, 6}

std::vector<int> v{1, 3, 5, 2, 4, 6};
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
// v = {1, 2, 3, 4, 5, 6}

2.7. 经典题目

力扣 34. 在排序数组中查找元素的第一个和最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
         int n = nums.size();
        if (n == 0) return {-1, -1};

        auto start = std::lower_bound(nums.begin(), nums.end(), target);    // 返回第一个大于等于 target 的元素
        auto end = std::lower_bound(nums.begin(), nums.end(), target + 1);  // 返回第一个大于 target 的元素,

        if (start != nums.end() && *start == target)  
            // 如果 start 不等于 nums.end() 且 *start 等于 target，返回 start 和 end 的索引
            return {static_cast<int>(start - nums.begin()), static_cast<int>(end - nums.begin() - 1)};
        else return {-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return {-1, -1};
        auto range = std::equal_range(nums.begin(), nums.end(), target);
        if (range.first != nums.end() && *range.first == target) 
            return {static_cast<int>(range.first - nums.begin()), static_cast<int>(range.second - nums.begin() - 1)};
        else return {-1, -1};
    }
};