1

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

4

9 回答 9

5
  1. 从给定的数字中找到以 2 为底的对数 => x := log (2, input)
  2. 将步骤 1 中获得的值向上和向下舍入 => y := round(x), z := round(x) + 1
  3. 找到 2^y, 2^z，将它们与输入进行比较，然后选择更适合的一个
于 2012-01-22T23:25:11.573 回答
2

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

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

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

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

于 2012-01-22T23:46:10.747 回答
2

根据您使用的语言，您可以使用按位运算轻松完成此操作。您希望设置的单个 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。

于 2012-01-22T23:49:46.687 回答
1

将 x 设置为 1。

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

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

于 2012-01-22T23:20:14.060 回答
0 
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;
    }
}
于 2012-01-22T23:40:36.953 回答
0

我将使用 5 作为简单示例的输入，而不是 50。

  • 将输入转换为位/字节，在本例中为 101
  • 由于您正在寻找 2 的幂，因此您的答案都将采用 10000...00 的形式（带有一定数量的零的一个）。您取输入值（3 位）并计算 100（3 位）和 1000（4 位）的整数值。整数 100 会小于输入，整数 1000 会更大。
  • 您计算输入和两个可能值之间的差异并使用最小的那个。在这种情况下 100 = 4（差 1）而 1000 = 8（差 3），所以搜索到的答案是 4
于 2012-01-22T23:42:10.200 回答
0 
public static int neareastPower2(int in) {
    return (int) Math.pow(2, Math.round(Math.log(in) / Math.log(2)));
}
于 2012-01-22T23:45:09.543 回答
0

这是一个函数的伪代码，它接受输入数字并返回你的答案。

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
}
于 2012-01-23T00:35:26.150 回答
0

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

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

while ( mask > value )
    mask >> 1

return ( mask & value == 0 ) ? mask : mask << 1
于 2012-01-23T04:39:06.397 回答