四舍五入到下一个2的幂

我想写一个函数,返回最近的2个数的下一个幂.例如,如果我的输入是789,输出应该是1024.有没有任何方法可以实现这一点而不使用任何循环但只使用一些按位运算符？

1> florin..：

---

检查Bit Twiddling Hacks.你需要得到基数2的对数,然后加1.32位值的示例:

最高可达2的最高功率

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++;

其他宽度的扩展应该是显而易见的.

---

这不是最有效的解决方案,因为许多处理器都有特殊的指令来计算前导零,这可以用来非常有效地计算log2.请参阅https://en.wikipedia.org/wiki/Find_first_set

---

@Simon:这是便携式解决方案.对于所有体系结构,没有通用的高效算法

---

如果数字本身是2的幂,该怎么办？

---

链接已经死了.

2> Paul Dixon..：

---

next = pow(2, ceil(log(x)/log(2)));

这可以通过找到你已经提高2的数字来获得x(记录数字的对数,除以所需基数的日志,更多信息请参阅维基百科).然后用ceil向上舍入以获得最接近的整数幂.

这是一个比其他地方链接的按位方法更通用(即更慢!)的方法,但很高兴知道数学,嗯？

---

这个成本至少可能是200个周期而且甚至都不正确.为什么会有这么多的赞成？

---

但是要小心浮动精度.`log(pow(2,29))/ log(2)`= 29.000000000000004,结果是2**30而不是返回2**29.我认为这就是为什么存在log2函数的原因？

---

@SuperflyJon但它提到了按位运算符,我认为任何问题都暗示了正确性,除非另有说明.

---

从C99开始,如果您的工具支持,您也可以使用[log2](http://www.cprogramming.com/fod/log2.html).海湾合作委员会和VS似乎没有:(

---

你错过了一个括号... next = pow(2,ceil(log(x)/ log(2)));

---

也许是因为问题没有提到性能？

3> Eclipse..：

---

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;

}

---

如果你把它归为它会很好(除非你发现它).它来自尖锐的黑客页面.

---

@florin,如果v是64位类型,你不能只在16之后加一个"c | = v >> 32"吗？

---

仅适用于特定位宽的代码应使用固定宽度类型，而不是最小宽度类型。这个函数应该接受并返回一个`uint32_t`。

---

那是32位数吗？扩展为64位？

4> 小智..：

---

我认为这也有效:

int power = 1;
while(power < x)
    power*=2;

答案是power.

---

很公平,问题没有循环.但是,与其他一些功能一样聪明,对于性能不敏感的代码,快速,容易理解并验证为正确的答案总能赢得我的支持.

---

@Vallentin应该由编译器自动优化.

---

这并没有返回最近的2的幂,但是它的力量立即大于X.仍然非常好

---

如果x太大（即没有足够的位来表示2的下一个幂），请当心无限循环。

5> Yann Droneau..：

---

如果你正在使用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));
}

---

请注意，这会返回大于或等于x的2的最小幂。将（x -1）更改为x会使函数返回大于x的2的较小幂。

6> vlk..：

---

还有一个,虽然我使用了循环,但是它比数学操作数快得多

两个"地板"选项的力量:

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;
}

---

如果`x`是2的幂,则结果不正确.如果输入是2的幂则需要微测试.`#define ISPOW2(x)((x)> 0 &&!((x)&(x-1)))`

7> 小智..：

---

对于任何未签名的类型,建立在Bit Twiddling Hacks:

#include 
#include 

template 
UnsignedType round_up_to_power_of_2(UnsignedType v) {
  static_assert(std::is_unsigned::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;
}

由于编译器在编译时知道迭代次数,因此实际上没有循环.

---

请注意,问题是关于C.

8> Jasper Bekke..：

---

对于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,并且根据您的编译器,可能有一个内在可用于为您完成工作.

9> Philip J. Fr..：

---

/*
** 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之间。该宏对于在编译时设置常量也很有用。

10> doynax..：

---

为了完整起见,这里是沼泽标准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);
}

---

随机浏览器,如果您没有专门的浮点硬件,这将会变得非常慢.在x86上,您可以使用bit twiddling围绕此代码运行圆圈.`rep bsr ecx,eax; mov eax,0; cmovnz eax,2; shl eax,cl`快约25倍.