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

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 类型)并且大于零。我从这个计算器中得到了 LOG2 解决方案 question .有几个很好的答案，但所有答案似乎都在四舍五入(包括这个)。我需要四舍五入。我对修改它们以进行汇总的解决方案不够满意。任何帮助将不胜感激!!!!

Answer 1

我很确定:

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)。

这将返回正确的 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