C：整数的快速求幂（幂 2）+ 二进制对数（四舍五入）

Question

我正在尝试找到用 C:

计算以下内容的最快方法

p = 2^(ceil(log2(x)));

到目前为止，查看 Stack overflow（和其他地方）中的答案我已经做到了：

#define LOG2(X) ((int) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
int p = 1 << LOG2( (unsigned long long)x );

x 将始终是一个整数（类型 int）并且大于零。我从这个 Whosebug question 得到了 LOG2 解决方案。有几个很好的答案，但所有答案似乎都在四舍五入（包括这个）。我需要四舍五入。我对修改它们以进行汇总的解决方案不够满意。任何帮助将不胜感激!!!!

Answer 1

什么鬼，我会把它作为一个答案。

要将 "round down" 转换为 "round up"，只需计算 log(x-1) 向下舍入并将结果加 1。

一般来说，向上舍入的结果总是比向下舍入多 1（即 floor(something) 和 ceil(something) 相差 1），除非 something 是一个精确的整数；在这种情况下，当您的输入是 2 的幂时。从输入中减去 1 并将结果加 1 的技巧是通用的；它适用于任何单调函数，如 log()。

为了完全正确，您可能希望将特殊情况 0 作为输入，但对于您的原始公式也是如此，因为 log(0) 未定义。

Answer 2

我很确定：

2^(ceil(log2(x)))

可以读作大于或等于 x 的最小幂，但 x 为零且未定义的情况除外。

在这种情况下，可以通过以下方式找到它：

unsigned int fn (unsigned int x) {
    if (x == 0) return 0;
    unsigned int result = 1;
    while ((result < x) && (result != 0))
        result <<= 1;
    return result;
}

效率相对较高，数据类型中的每个位数最多需要一次迭代（例如，32 位整数为 32）。

这将 return 要么是正确的 2 的幂，要么是错误的零（如果输入数字为零，或者结果无法用数据类型表示）。

您可以在以下程序中看到它的运行情况：

#include <stdio.h>
#include <limits.h>

unsigned int fn (unsigned int x) {
    if (x == 0) return 0;
    unsigned int result = 1;
    while ((result < x) && (result != 0))
        result <<= 1;
    return result;
}

int main (void) {
    printf ("%u -> %u\n\n", 0, fn(0));
    for (unsigned int i = 1; i < 20; i++)
        printf ("%u -> %u\n", i, fn(i));
    printf ("\n%u -> %u\n", UINT_MAX, fn(UINT_MAX));
    return 0;
}

输出：

0 -> 0

1 -> 1
2 -> 2
3 -> 4
4 -> 4
5 -> 8
6 -> 8
7 -> 8
8 -> 8
9 -> 16
10 -> 16
11 -> 16
12 -> 16
13 -> 16
14 -> 16
15 -> 16
16 -> 16
17 -> 32
18 -> 32
19 -> 32

4294967295 -> 0

C：整数的快速求幂（幂 2）+ 二进制对数（四舍五入）

C : Fast Exponentiation (Power 2) + Binary Logarithm (Rounded up) for Integers

c

math

casting

bit-manipulation