如何找到与给定输入最接近的 2^N 值？

Question

我必须以某种方式保持程序运行，直到指数函数的输出超过输入值，然后将其与指数函数的先前输出进行比较。即使只是伪代码，我该如何做这样的事情？

Answer 1

1. 求给定数以 2 为底的对数 => x := log(2, input)
2. 将步骤1中获取的值向上和向下舍入=> y := round(x), z := round(x) + 1
3. 找到 2^y, 2^z，将它们与输入进行比较并选择更适合的一个

Answer 2

根据您使用的语言，您可以使用按位运算轻松完成此操作。您需要设置的单个 1 位大于输入值中设置的最高一位的值，或者设置为输入值中设置的最高一位的值。

如果您确实将最高设置位以下的所有位设置为 1，则添加 1，最终得到下一个更大的 2 的幂。您可以右移此值以获得下一个较低的二的幂并选择两者中更接近的一个。

unsigned closest_power_of_two(unsigned value)
{
    unsigned above = (value - 1); // handle case where input is a power of two
    above |= above >> 1;          // set all of the bits below the highest bit
    above |= above >> 2;
    above |= above >> 4;
    above |= above >> 8;
    above |= above >> 16;
    ++above;                      // add one, carrying all the way through
                                  // leaving only one bit set.

    unsigned below = above >> 1;  // find the next lower power of two.

    return (above - value) < (value - below) ? above : below;
}

请参阅 Bit Twiddling Hacks 了解其他类似的技巧。

Answer 3

除了循环之外，还有一种解决方案可能会更快，具体取决于编译器如何映射 nlz 指令：

public int nextPowerOfTwo(int val) {
   return 1 << (32 - Integer.numberOfLeadingZeros(val - 1)); 
}

没有显式循环，并且肯定比使用 Math.pow 的解决方案更有效。如果不查看编译器为 numberOfLeadingZeros 生成的代码，很难说更多。

这样我们就可以轻松获得 2 的较低幂，然后比较哪个更接近 - 在我看来，每个解决方案都必须完成最后一部分。

Answer 4

将 x 设置为 1。

当 x <目标，设置 x = 2 * x

，然后返回 x 或 x / 2，以更接近目标的为准。

Answer 5

public static int neareastPower2(int in) {
    if (in <= 1) {
        return 1;
    }
    int result = 2;

    while (in > 3) {
        in = in >> 1;
        result = result << 1;
    }

    if (in == 3) {
        return result << 1;
    } else {
        return result;
    }
}

Answer 6

我将使用 5 作为输入，而不是 50。

• 将输入转换为位/字节，在本例中为 101
• 由于您正在寻找 2 的幂，因此您的答案将全部采用 10000...00 的形式（a具有一定数量的零）。您获取输入值（3 位）并计算 100（3 位）和 1000（4 位）的整数值。整数 100 将小于输入，整数 1000 将大于输入。
• 您计算输入值与两个可能值之间的差值并使用最小的值。在本例中，100 = 4（差值 1），而 1000 = 8（差值 3），因此搜索到的答案为 4

Answer 7

public static int neareastPower2(int in) {
    return (int) Math.pow(2, Math.round(Math.log(in) / Math.log(2)));
}

Answer 8

下面是一个函数的伪代码，该函数接受输入数字并返回您的答案。

int findit( int x) {
  int a = int(log(x)/log(2));
  if(x >= 2^a + 2^(a-1))
    return 2^(a+1)
  else
    return 2^a
}

Answer 9

这是一个按位解决方案——如果出现平局，它将返回 2^N 和 2^(N+1) 的减数。与调用 log() 函数相比，这应该非常快

let mask = (~0 >> 1) + 1

while ( mask > value )
    mask >> 1

return ( mask & value == 0 ) ? mask : mask << 1