c - 四舍五入到 2 的幂(使用预处理器常量)

Question

使用 unsigned int 可以像这样四舍五入到 2 的幂:

unsigned int power_of_2_max_u(unsigned int x)
{
    x -= 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return x + 1;
}

或者……

int is_power_of_2_i(int n)
{
    return (n & (n - 1)) == 0;
}

int power_of_2_max_i(int n)
{
    if (is_power_of_2_i(n))
        return n;

    do {
        n = n & (n - 1);
    } while (!is_power_of_2_i(n));

    return n * 2;
}

然而，当值是常量时，应该可以使用预处理器来避免每次都计算该值。 e.例如:

i = power_of_2_max_u(sizeof(SomeStruct));

这是一个等价于 power_of_2_max_u 的宏。

#define POW2_CEIL(v) (1 + \
(((((((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) | \
     ((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) >> 0x04))) | \
   ((((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) | \
     ((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) >> 0x04))) >> 0x02))) | \
 ((((((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) | \
     ((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) >> 0x04))) | \
   ((((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) | \
     ((((v) - 1) | (((v) - 1) >> 0x10) | \
      (((v) - 1) | (((v) - 1) >> 0x10) >> 0x08)) >> 0x04))) >> 0x02))) >> 0x01))))

由这个 Python-3 脚本生成。

import math
BITS = 32
data = (["(v - 1)"] +
        ["(v | (v >> 0x%02x))" % i
         for i in reversed([2 ** j
         for j in range(int(math.log2(BITS)))])])
macro = "1 + v"
for l in reversed(data):
    macro = macro.replace('v', '(%s)' % l)
print("#define POW2_CEIL(v)", macro) 

使用 statement expressions它可以做得更好一些，但这依赖于 GCC 扩展。

#define POW2_CEIL(x_) ({      \
    unsigned int x = x_; \
    x -= 1;              \
    x = x | (x >> 1);    \
    x = x | (x >> 2);    \
    x = x | (x >> 4);    \
    x = x | (x >> 8);    \
    x = x | (x >>16);    \
    x + 1; })

虽然这是一个相当丑陋的宏，但我仔细检查了一下，编译器确实将它正确地缩减为一个常量(它应该如此)所以 unsigned int a = 8; 完全等同于 unsigned int a = POW2_CEIL(7);, 但是我很想知道是否有更好的方法来做到这一点(可能不限于 int 范围)。

Answer 1

However when the value is a constant, it should be possible to use the preprocessor to avoid having to calculate the value every time.

可读性>>>性能。首先，问问自己“”这是我的代码中真正的瓶颈吗？

如果答案是“否”，那么什么都不做；继续前进，不要考虑过早地对您的代码进行微“优化”。

即使这是您代码的重要部分，请考虑您的函数是纯函数。它们的返回值仅取决于它们的参数，因为它们执行简单的计算(基本上是映射)。 很有可能，任何体面的优化编译器在使用编译时已知的表达式调用时都会不断折叠您的函数。

例如下面的代码……

#include <stdio.h>

static unsigned power_of_2_max_u(unsigned x)
{
    x -= 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return x + 1;
}

struct Foo {
    int x;
    char c;
    int i;
};

int main()
{
    printf("%zu %u\n", sizeof(struct Foo), power_of_2_max_u(sizeof(struct Foo)));

    return 0;
}

…由clang -O2 -flto翻译成以下程序集:

/tmp/constfold:
(__TEXT,__text) section
_main:
0000000100000f50    pushq   %rbp
0000000100000f51    movq    %rsp, %rbp
0000000100000f54    leaq    0x37(%rip), %rdi  ## literal pool for: "%zu %u\n"
0000000100000f5b    movl    $0xc, %esi        ## *** sizeof(struct Foo) == 12
0000000100000f60    movl    $0x10, %edx       ## *** rounded up == 16
0000000100000f65    xorl    %eax, %eax
0000000100000f67    callq   0x100000f70       ## symbol stub for: _printf
0000000100000f6c    xorl    %eax, %eax
0000000100000f6e    popq    %rbp
0000000100000f6f    retq

因此，您不需要为编译器执行任何操作以常量折叠您的函数。

仅当您观察到它们未常量折叠时，才考虑将您的函数重写为上述宏之一(或使用不可移植的编译器内部函数)。