0%

寻找不小于给定整数的最小的 2 的幂方

这是一篇简单的记录。

最近在写 YTL 的过程中遇到这样一个子问题:需要定义一个函数 uint32_t func(uint32_t num),返回不小于 num 的最小的 2 的幂方。例如

1
2
3
4
5
1 == func(1);
2 == func(2);
4 == func(3);
4 == func(4);
// ……

一开始我想了个用位运算的奇技淫巧,自我感觉还不错:

1
2
3
4
5
6
7
uint32_t func(uint32_t num) {
uint32_t res = 1;
while (res < num) {
res <<= 1;
}
return res;
}

后来一想,「不要在编译器面前装屄」,于是发现老实用 std::log2 来计算的话,效率要高出五倍多:

1
2
3
4
// #include <cmath>
uint32_t func(uint32_t num) {
return 1 << static_cast<int>(std::ceil(std::log2(num)));
}

再一想,std::ceil 本来就快,std::log2 有快速解法。那么如果把 1 << foo 换成 std::pow(2.0, foo) 会怎样呢?结果发现,大概是由于 std::pow 是为浮点数运算设计的,所以没为 2 的幂方做优化,所以效率还不如位运算:

1
2
3
4
// #include <cmath>
uint32_t func(uint32_t num) {
return std::pow(2.0, std::ceil(std::log2(num)));
}

以上。

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。