c++ - 通过宏内联函数

Question

我有一个递归函数，我知道它只会调用自己 32 次。

int f(int x) { return (x == 0) ? 0 : YY + f(~x & (YY - 1)); }

(YY 是一个宏，它隔离了 x 的最高有效位，为了您的理智，不包括在内)。为了好玩，我正在尝试优化函数，以便在 UVA 在线判断中获得最佳结果(我永远不会在实际代码上进行此优化)。有没有办法把这个函数变成一个宏/内联函数，这样一个函数就永远不需要被调用(即编译器扩展一个语句足够长以至于不需要递归)，或者有没有办法通过一个内联方法？

如果需要，这是宏:

#define YY ((((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) | ((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) >> 2)) | (((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) | ((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) >> 2)) >> 1)) ^ ((((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) | ((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) >> 2)) | (((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) | ((((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) | (((x | (x >> 16)) | ((x | (x >> 16)) >> 8)) >> 4)) >> 2)) >> 1)) >> 1))

Answer 1

如果您想做的只是转换为标准格雷码，实际上比您想象的要简单得多。您所需要的只是将二进制值与自身右移一位进行异或运算。这是一个等效函数(类型声明为 unsigned)，取自 Wikipedia article :

unsigned int binaryToGray(unsigned int num)
{
    return num ^ (num >> 1);
}

我将前一百万个整数的输出与您的函数 f 进行了比较，结果匹配。