write a code the find n-th number of Gray Code list [closed]

Question

Write a function that, given N >= 0, finds the N^th number in a standard Gray code.

Example input:

1
2
3
4

Example output:

1
3
2
6

Additional reference

Answer 1

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. 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.

Answer 2

Golfscript, 4 chars

.2/^

Answer 3

scala:

It's not a code-golf!

However - if you like to golf:

def g(n:Int)=n^(n/2)

20 chars, according to my set of natural numbers.

But since speed matters, I produce a compilable form:

object Graycode extends App {

  def graycode (n: Int) = n^(n/2)

  def test (max: Int) {
    var i = 0
    val start = System.nanoTime ()
    while (i < max) { 
      graycode (i) 
      i += 1
    }
    val stop = System.nanoTime ()
    
    val diff = (stop-start)*1.0 / (1000*1000*1000)
    println ("Time: " + diff + "s\tn: " + max + "\tspeed: " + max * 1.0/diff + " /s")  
  }
  
  override def main (args: Array[String]) = {
    var max = args(0).toInt 
    val graycode = Graycode
    graycode.test (max)
  }
}

You can compare it against your solution this way:

scala Graycode 1000000000
Time: 23.882410496s n: 1000000000   speed: 4.1871820274066865E7 /s

About 4 million ints per second on my machine. If I comment out the call to graycode, I get as speed: 7.683713972447292E8 /s, so it is not mainly the time used to loop, which is measured above.

Of course your absolute times will vary, but you may compare it to measurements of your code. Please provide measurement methods with your solutions too.