我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
如果你需要OpenGL相关的东西:
/* Compute the nearest power of 2 number that is
* less than or equal to the value passed in.
*/
static GLuint
nearestPower( GLuint value )
{
int i = 1;
if (value == 0) return -1; /* Error! */
for (;;) {
if (value == 1) return i;
else if (value == 3) return i*4;
value >>= 1; i *= 2;
}
}
其他回答
如果你需要OpenGL相关的东西:
/* Compute the nearest power of 2 number that is
* less than or equal to the value passed in.
*/
static GLuint
nearestPower( GLuint value )
{
int i = 1;
if (value == 0) return -1; /* Error! */
for (;;) {
if (value == 1) return i;
else if (value == 3) return i*4;
value >>= 1; i *= 2;
}
}
对于任何unsigned类型,构建在Bit Twiddling Hacks上:
#include <climits>
#include <type_traits>
template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
v--;
for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
{
v |= v >> i;
}
return ++v;
}
这里并没有真正的循环,因为编译器在编译时知道迭代的次数。
还有一个,虽然我用的是循环,但这比数学操作数要快得多
功率两“地板”选项:
int power = 1;
while (x >>= 1) power <<= 1;
两个“ceil”选项的力量:
int power = 2;
x--; // <<-- UPDATED
while (x >>= 1) power <<= 1;
更新
正如在评论中提到的,在cell中有错误,它的结果是错误的。
以下是全部功能:
unsigned power_floor(unsigned x) {
int power = 1;
while (x >>= 1) power <<= 1;
return power;
}
unsigned power_ceil(unsigned x) {
if (x <= 1) return 1;
int power = 2;
x--;
while (x >>= 1) power <<= 1;
return power;
}
我认为这也是可行的:
int power = 1;
while(power < x)
power*=2;
答案就是力量。
c#中的可移植解决方案:
int GetNextPowerOfTwo(int input) {
return 1 << (int)Math.Ceiling(Math.Log2(input));
}
Math.Ceiling(Math.Log2(value))计算2的下一个幂的指数,1 <<通过移位计算实值。
更快的解决方案,如果你有。net Core 3或更高版本:
uint GetNextPowerOfTwoFaster(uint input) {
return (uint)1 << (sizeof(uint) * 8 - System.Numerics.BitOperations.LeadingZeroCount(input - 1));
}
这将使用system . numbers . bitoperations . leadingzerocount(),如果可用,则使用硬件指令:
https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs
更新:
RoundUpToPowerOf2()即将在。net 6!内部实现与上面的. net Core 3解决方案基本相同。
这里是社区更新。