通过宏内联函数

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),取自维基百科文章:

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

我将输出与你的函数f进行了比较,得出了第一百万个整数,并且它匹配了.