Return to Answer

###Perl, 7 chars

Perl, 7 chars

Edit: Since this challenge is now tagged fastest-code, let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:

A faster solution, if one exists, is likely to require hand-optimized assembly code. Even then, a good optimizing C compiler may be hard to beat.

Edit: Since this challenge is now tagged fastest-code, let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:

A faster solution, if one exists, is likely to require hand-optimized assembly code. Even then, a good optimizing C compiler may be hard to beat. Looking at the disassembly of the benchmark code below, it seems gcc compiles this into three Intel assembly instructions:

 8048428:       89 c2                   mov    %eax,%edx
 804842a:       d1 ea                   shr    %edx
 804842c:       31 c2                   xor    %eax,%edx

This (a register copy, a shift and an XOR) is about what I'd expect any decent compiler to produce. Of course, a good compiler might also be able to interleave the operations with surrounding code to improve pipelining. (In the benchmark, the inner loop is tight enough that there's not much room for that.)

Testing just how fast this is can be a bit tricky, since we need to make sure the compiler won't just optimize away the Gray code calculation, or even the entire testing loop. Here's a piece of code that sums up all unsigned 32-bit integers eight times over, either in Gray code order or, if NOGRAY is defined, in normal binary order. Obviously, the output should be zero in either case, but at least gcc isn't smart enough to realize that.

#include <inttypes.h>
#include <stdio.h>

#ifdef NOGRAY
#  define g(i) (i)
#else
#  define g(i) ((i)^(i)>>1)
#endif

int main (void) {
    uint32_t k, i, n = 0;
    for (k = 0; k < 8; k++) {
        for (i = 1; i != 0; i++) n += g(i);
    }
    printf("%lu\n", (unsigned long) n);
    return 0;
}

On my 2.2GHz AMD Athlon 64 X2 CPU, compiled with gcc 4.4.3 with -O3 for i486-linux-gnu, running this code takes about 46.9 seconds, compared to about 31.2 second with NOGRAY defined. That gives about 15.7 seconds for 2³⁵−8 Gray code calculations, which comes down to about 0.457 nanoseconds, or almost exactly one CPU cycle per calculation.

However, it's worth noting that that's the marginal cost of including the Gray code calculation in the loop. The total time to execute the benchmark loop (which includes two adds and a conditional jump in addition to the three lines of assembly I showed above) is about 1.365 nanoseconds, or three cycles per iteration.

###Perl, 7 chars

$_^$_/2

This is an expression that returns the Gray code, given the input in $_. You can use it on the command line with the -n switch:

perl -nE 'say $_^$_/2'

or use it in a map:

perl -E 'say for map $_^$_/2, 1 .. 10'
1
3
2
6
7
5
4
12
13
15

If you specifically want a function, I can do that too (in 20 chars):

sub g{$_[0]^$_[0]/2}

###Perl, 7 chars

$_^$_/2

This is an expression that returns the Gray code, given the input in $_. You can use it on the command line with the -n switch:

perl -nE 'say $_^$_/2'

or use it in a map:

perl -E 'say for map $_^$_/2, 1 .. 10'
1
3
2
6
7
5
4
12
13
15

If you specifically want a function, I can do that too (in 20 chars):

sub g{$_[0]^$_[0]/2}

Edit: Since this challenge is now tagged fastest-code, let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:

#define g(i) ((i)^(i)>>1)

A faster solution, if one exists, is likely to require hand-optimized assembly code. Even then, a good optimizing C compiler may be hard to beat.