我有一个递归函数,我知道它只会调用自己 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))
最佳答案
如果您想做的只是转换为标准格雷码,实际上比您想象的要简单得多。您所需要的只是将二进制值与自身右移一位进行异或运算。这是一个等效函数(类型声明为 unsigned
),取自 Wikipedia article :
unsigned int binaryToGray(unsigned int num)
{
return num ^ (num >> 1);
}
我将前一百万个整数的输出与您的函数 f
进行了比较,结果匹配。
关于c++ - 通过宏内联函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37095011/