我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
我认为这也是可行的:
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解决方案基本相同。
这里是社区更新。
c++ 14 clp2的constexpr版本
#include <iostream>
#include <type_traits>
// Closest least power of 2 minus 1. Returns 0 if n = 0.
template <typename UInt, std::enable_if_t<std::is_unsigned<UInt>::value,int> = 0>
constexpr UInt clp2m1(UInt n, unsigned i = 1) noexcept
{ return i < sizeof(UInt) * 8 ? clp2m1(UInt(n | (n >> i)),i << 1) : n; }
/// Closest least power of 2 minus 1. Returns 0 if n <= 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value && std::is_signed<Int>::value,int> = 0>
constexpr auto clp2m1(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n <= 0 ? 0 : n)); }
/// Closest least power of 2. Returns 2^N: 2^(N-1) < n <= 2^N. Returns 0 if n <= 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value,int> = 0>
constexpr auto clp2(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n-1)) + 1; }
/// Next power of 2. Returns 2^N: 2^(N-1) <= n < 2^N. Returns 1 if n = 0. Returns 0 if n < 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value,int> = 0>
constexpr auto np2(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n)) + 1; }
template <typename T>
void test(T v) { std::cout << clp2(v) << std::endl; }
int main()
{
test(-5); // 0
test(0); // 0
test(8); // 8
test(31); // 32
test(33); // 64
test(789); // 1024
test(char(260)); // 4
test(unsigned(-1) - 1); // 0
test<long long>(unsigned(-1) - 1); // 4294967296
return 0;
}
在标准c++20中,这包含在<bit>中。 答案很简单
#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
return std::bit_ceil(v);
}
注意: 我给出的解决方案是针对c++,而不是c,我会给出这个问题的答案,但它是这个问题的副本!
如果您正在使用GCC,您可能想要看看Lockless Inc.优化next_pow2()函数。本页描述了一种使用内置函数builtin_clz()(计数前导零)的方法,然后直接使用x86 (ia32)汇编指令bsr(位扫描反向),就像它在另一个答案的游戏开发站点链接中所描述的那样。此代码可能比前面的回答中描述的更快。
顺便说一下,如果你不打算使用汇编指令和64位数据类型,你可以使用这个
/**
* return the smallest power of two value
* greater than x
*
* Input range: [2..2147483648]
* Output range: [2..2147483648]
*
*/
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 1);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
return 1 << (32 - __builtin_clz (x - 1));
}
为了完整起见,这里是用标准C语言实现的浮点数。
double next_power_of_two(double value) {
int exp;
if(frexp(value, &exp) == 0.5) {
// Omit this case to round precise powers of two up to the *next* power
return value;
}
return ldexp(1.0, exp);
}