CODEWITHSUNDEEP
c++coptimizationmacrosinline
Jacob Denson
Jacob Denson

Reputation: 391

Inline function via macro

I have a recursive function which I know will only ever call itself 32 times.

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

(YY is a macro which isolates the most significant bit of x, which is not included for your sanity). For fun, I'm trying to optimize the function so I can get the best result on the UVA online judge (I would never do this optimization on real code). Is there a way to make this function into a macro / inline the function so that a function need not ever be called (i.e. the compiler expands a statement long enough that recursion is not needed), or is there a way to do this via an inline method?

Here's the macro, if needed:

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

Upvotes: 1

Views: 102

Answers (1)

Tom Karzes
Tom Karzes

Reputation: 24052

If all you want to do is convert to standard gray code, it's actually far simpler than you may realize. All you need is to XOR the binary value with itself shifted right by one. Here's an equivalent function (with the types declared unsigned), taken from the Wikipedia article:

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

I compared the output to your function f for the first million integers, and it matched.

Upvotes: 5

Related Questions