Algorithm for finding the smallest power of two that#39;s greater or equal to a given value(查找大于或等于给定值的 2 的最小幂的算法)
问题描述
我需要找到大于或等于给定值的 2 的最小幂.到目前为止,我有这个:
I need to find the smallest power of two that's greater or equal to a given value. So far, I have this:
int value = 3221; // 3221 is just an example, could be any number
int result = 1;
while (result < value) result <<= 1;
它工作正常,但感觉有点天真.有没有更好的算法来解决这个问题?
It works fine, but feels kind of naive. Is there a better algorithm for that problem?
编辑.有一些不错的汇编程序建议,所以我将这些标签添加到问题中.
EDIT. There were some nice Assembler suggestions, so I'm adding those tags to the question.
推荐答案
这是我最喜欢的.除了对它是否无效的初始检查(<0,如果你知道你只传入了 >=0 的数字,你可以跳过它),它没有循环或条件,因此将优于大多数其他方法.这与 erickson 的答案类似,但我认为我在开头递减 x 并在结尾加 1 比他的答案少一些尴尬(并且也避免了结尾的条件).
Here's my favorite. Other than the initial check for whether it's invalid (<0, which you could skip if you knew you'd only have >=0 numbers passed in), it has no loops or conditionals, and thus will outperform most other methods. This is similar to erickson's answer, but I think that my decrementing x at the beginning and adding 1 at the end is a little less awkward than his answer (and also avoids the conditional at the end).
/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
if (x < 0)
return 0;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x+1;
}
这篇关于查找大于或等于给定值的 2 的最小幂的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:查找大于或等于给定值的 2 的最小幂的算法
基础教程推荐
- C++ 标准:取消引用 NULL 指针以获取引用? 2021-01-01
- C++,'if' 表达式中的变量声明 2021-01-01
- 如何定义双括号/双迭代器运算符,类似于向量的向量? 2022-01-01
- C++ 程序在执行 std::string 分配时总是崩溃 2022-01-01
- 调用std::Package_TASK::Get_Future()时可能出现争用情况 2022-12-17
- 运算符重载的基本规则和习语是什么? 2022-10-31
- 如何在 C++ 中处理或避免堆栈溢出 2022-01-01
- 什么是T&&(双与号)在 C++11 中是什么意思? 2022-11-04
- 设计字符串本地化的最佳方法 2022-01-01
- 您如何将 CreateThread 用于属于类成员的函数? 2021-01-01