将值舍入到最接近的 2 次方

Question

我正在寻找 C# 中将值舍入到最接近的 2 的幂的最快方法。 我发现如果使用像这样的按位运算符，将值四舍五入到二的下一个幂的最快方法。

int ToNextNearest(int x)
{
    if (x < 0) { return 0; }
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

但这给出了下一个最接近的而不是最接近的，我只想有最接近的二的幂。 这是一个简单的方法。

int ToNearest(int x)
{
    Math.Pow(2, Math.Round(Math.Log(x) / Math.Log(2)));
}

但是有没有更好的优化版本来查找两个值的最接近的幂？

非常感谢。

Answer 1

当然，最好的方法是使用按位例程找到下一个 2 的幂，然后将该结果除以 2。这给你以前的二的幂。那么简单的比较一下就知道两者哪个更接近了。

int ToNearest(int x)
{
  int next = ToNextNearest(x);
  int prev = next >> 1;
  return next - x < x - prev ? next : prev;
}

未经测试的代码，但你明白了。

Answer 2

.Net6 引入了一种方法 this

using System.Numerics;

var nearestPowOf2 = BitOperations.RoundUpToPowerOf2(100); //returns 128

Answer 3

在 .Net Core 上，最快的方法可能是使用内在函数：

private static int NearestPowerOf2(uint x)
{
    return 1 << (sizeof(uint) * 8 - BitOperations.LeadingZeroCount(x - 1));
}

在支持LZCNT指令的CPU上，它只是6个CPU指令，没有分支。

Answer 4

我正在用这个：

public static int CeilPower2(int x)
{
    if (x < 2) {
        return 1;
    }
    return (int) Math.Pow(2, (int) Math.Log(x-1, 2) + 1);
}

public static int FloorPower2(int x)
{
    if (x < 1) {
        return 1;
    }
    return (int) Math.Pow(2, (int) Math.Log(x, 2));
}

Answer 5

这个怎么样：

int ToNearest(int val, int pow)
{
    if (pow < 0) return 0;
    if (pow == 0) return val;

    if (val & (1 << (pow - 1))) {
        return ((val >> pow) + 1) << pow;
    } else {
        return (val >> pow) << pow;
    }
}

Answer 6

尚未测试，但我认为这可行

int ToNearest(value x)
{
    int num = 0;
    for(int i=1; i < 65; i++)
    {
        int cur = Math.Abs(value - 0<<i);
        if(Math.Abs(value - 0<<i) < Math.Abs(value - num))
            num = cur;
        else if(num != 0) break;
    }
    return num;
}

Answer 7

这是 @john 建议的解决方案的完整实现，但如果该值恰好位于下一个和上一个 2 的幂之间，它将向上舍入。

public static int RoundToNextPowerOfTwo(int a)
{
    int next = CeilToNextPowerOfTwo(a);
    int prev = next >> 1;
    return next - a <= a - prev ? next : prev;
}

public static int CeilToNextPowerOfTwo(int number)
{
    int a = number;
    int powOfTwo = 1;

    while (a > 1)
    {
        a = a >> 1;
        powOfTwo = powOfTwo << 1;
    }
    if (powOfTwo != number)
    {
        powOfTwo = powOfTwo << 1;
    }
    return powOfTwo;
}

Answer 8

由于 C# 需要 IEEE754 浮点数，因此在任何不模拟浮点函数的平台上可能有一种更快的方法：

int ToNearestPowerOf2(int x) =>
  1 << (int)(BitConverter.DoubleToInt64Bits(x + x/3) >> 52) - 1023;

理由：

• x + x/3

  
  最接近的 2 次方，基本上是 *4/3

• (BitConverter.DoubleToInt64Bits(x) >> 52) - 1023

  
  取浮点指数作为下限(ln2(x))

• 1 << x

  
  以 2 为底的指数函数

该函数显然需要 x 为正值。 0 不起作用，因为最接近的 2 的幂是 -∞， 负值有复数对数。

这是否是最快的方法可能很大程度上取决于 JIT 优化器从代码中提取的内容，更具体地说，它如何处理 DoubleToInt64Bits 中的硬指针转换。这可能会妨碍其他优化。

您不必使用任何比较来获得最近的 2 的幂。由于 2 的所有幂都由相同的因子分隔，因此舍入点始终位于下一个 2 幂的 3/4（即恰好是最上面的） 2 位已设置）。因此乘以倒数然后截断就可以了。

Answer 9

static int Pow2Ceil(int value)
  => ((value << 1) & ~(int)(uint.MaxValue >> BitOperations.LeadingZeroCount((uint)value)));
static int Pow2Floor(int value)
  => (value & ~(int)(uint.MaxValue >> (BitOperations.LeadingZeroCount((uint)value) + 1)));