Nav*_*een 170 c optimization bit-manipulation
我想写一个函数,返回最近的2个数的下一个幂.例如,如果我的输入是789,输出应该是1024.有没有任何方法可以实现这一点而不使用任何循环但只使用一些按位运算符？
flo*_*rin 129
检查Bit Twiddling Hacks.你需要得到基数2的对数,然后加1.32位值的示例:
最高可达2的最高功率
Run Code Online (Sandbox Code Playgroud)unsigned int v; // compute the next highest power of 2 of 32-bit v v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++;
其他宽度的扩展应该是显而易见的.
Pau*_*xon 77
next = pow(2, ceil(log(x)/log(2)));
这可以通过找到你已经提高2的数字来获得x(记录数字的对数,除以所需基数的日志,更多信息请参阅维基百科).然后用ceil向上舍入以获得最接近的整数幂.
这是一个比其他地方链接的按位方法更通用(即更慢!)的方法,但很高兴知道数学,嗯？
Ecl*_*pse 49
unsigned long upper_power_of_two(unsigned long v)
{
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
小智 48
我认为这也有效:
int power = 1;
while(power < x)
power*=2;
答案是power.
Yan*_*aud 31
如果你正在使用GCC,你可能想看一下Lockless公司优化next_pow2()函数.这个页面描述了一种使用内置函数的方法builtin_clz()(计数前导零),然后直接使用x86(ia32)汇编指令bsr(位扫描反转),就像它在另一个答案的gamedev网站链接中描述的那样.此代码可能比上一个答案中描述的更快.
顺便说一句,如果你不打算使用汇编程序指令和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));
}
Jak*_*idt 31
在标准中c++20，这包含在<bit>. 答案很简单
#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
return std::bit_ceil(v);
}
注意：
我给出的解决方案是 for c++，而不是，我会给出这个c问题的答案，但它作为这个问题的重复项被关闭！
vlk*_*vlk 15
还有一个,虽然我使用了循环,但是它比数学操作数快得多
两个"地板"选项的力量:
int power = 1;
while (x >>= 1) power <<= 1;
两个"ceil"选项的力量:
int power = 2;
x--; // <<-- UPDATED
while (x >>= 1) power <<= 1;
UPDATE
如评论中所述ceil,其结果错误的地方是错误的.
这里有完整的功能:
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;
}
kre*_*ieg 11
尽管这个问题在c这里被标记为我的五美分。幸运的是，C++ 20 将包含std::ceil2和std::floor2（请参阅此处）。它是consexpr模板函数，当前的GCC 实现使用位移并适用于任何整数无符号类型。
小智 10
对于任何未签名的类型,建立在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;
}
由于编译器在编译时知道迭代次数,因此实际上没有循环.
对于IEEE浮动,你可以做这样的事情.
int next_power_of_two(float a_F){
int f = *(int*)&a_F;
int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1
f >>= 23; // remove factional part of floating point number
f -= 127; // subtract 127 (the bias) from the exponent
// adds one to the exponent if were not a power of two,
// then raises our new exponent to the power of two again.
return (1 << (f + b));
}
如果你需要一个整数解决方案并且你能够使用内联汇编,BSR将为你提供x86上整数的log2.它计算设置了多少个右位,这正好等于该数字的log2.其他处理器(通常)具有类似的指令,例如CLZ,并且根据您的编译器,可能有一个内在可用于为您完成工作.
小智 8
这是我的 C 解决方案。希望这有帮助！
int next_power_of_two(int n) {
int i = 0;
for (--n; n > 0; n >>= 1) {
i++;
}
return 1 << i;
}
在 x86 中，您可以使用 sse4 位操作指令使其更快。
//assume input is in eax
popcnt edx,eax
lzcnt ecx,eax
cmp edx,1
jle @done //popcnt says its a power of 2, return input unchanged
mov eax,2
shl eax,cl
@done: rep ret
在 c 中，您可以使用匹配的内在函数。
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000) ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00) ? (8 +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0) ? (4 +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc) ? (2 +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2) ? (1) : (0))
#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8 __LOG2D
static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
i =i -1;
i =LOG2_UINT64(i);
return 1UL <<(1 +i);
#endif
}
如果您不想冒险进入未定义行为的领域，则输入值必须在1到2 ^ 63之间。该宏对于在编译时设置常量也很有用。
为了完整起见,这里是沼泽标准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);
}