先前的2次幂

Question

关于如何找到给定值的2的下一个幂(参见参考文献)，有很多信息，但我找不到任何信息来获得之前的2的幂。

到目前为止，我发现的唯一方法是保持一个2到2^64幂的表，并进行简单的查找。

• 阿休斯片段
• gamedev
• 钻头缠绕式黑客
• 堆栈溢出

Answer 1

这是我目前的解，找到任意给定的正整数n中的下一个和先前的两个幂，以及一个小的函数来确定一个数是否是2的幂。

这个实现是针对Ruby的。

class Integer

  def power_of_two?
    (self & (self - 1) == 0)
  end

  def next_power_of_two
    return 1 if self <= 0
    val = self
    val = val - 1
    val = (val >> 1) | val
    val = (val >> 2) | val
    val = (val >> 4) | val
    val = (val >> 8) | val
    val = (val >> 16) | val
    val = (val >> 32) | val if self.class == Bignum
    val = val + 1
  end

  def prev_power_of_two
   return 1 if self <= 0
   val = self
   val = val - 1
   val = (val >> 1) | val
   val = (val >> 2) | val
   val = (val >> 4) | val
   val = (val >> 8) | val
   val = (val >> 16) | val
   val = (val >> 32) | val if self.class == Bignum
   val = val - (val >> 1)
  end
end

示例使用：

10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8

对于前面的2的幂，找到下一个和除以两个比上面的方法稍慢。

我不知道它是如何与Bignum一起工作的。

Answer 2

来自黑客之乐，一个很好的无分支解决方案：

uint32_t flp2 (uint32_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}

这通常需要12个指令。如果CPU有“计数前导零”指令，则可以在较少的时间内完成该操作。

Answer 3

uint32_t previous_power_of_two( uint32_t x ) {
    if (x == 0) {
        return 0;
    }
    // x--; Uncomment this, if you want a strictly less than 'x' result.
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}

谢谢你的回复。我会尽量把它们总结一下，并解释得更清楚一点。这个算法所做的就是在第一个‘1’位之后将所有的位都改为‘1’，因为这是唯一能使我们的“x”比它以前的2次方更大的位。在确认他们是“一个人”之后，它只会移除他们，留下第一个“一个”的原样。那一丁点的位置就是我们以前的两种力量。