Grey Codes Consider all the bit strings of a certain length. For example length

Question

Grey Codes

Consider all the bit strings of a certain length. For example length 3:

000

001

010

011

100

101

110

111

The above listing of all 8 such strings is in a particular order -- the numerical order if the

strings are interpreted as base-2 integers.

Of course we can order them any way we want.

Suppose we want to order them such that each string differs from the string

preceding it in exactly one bit position.

Clearly the above sequence does not qualify (e.g., 100 follows 011 and these two

strings differ in all three bit positions!).

Is there a way to generate all bit strings of length n such that every pair of adjacent

strings differ in exactly one position?

The answer is yes!

Let

Explanation / Answer

Answer

Grey codes in C using recursion

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void gcodes (int n) {
        char bits[256][8];

        if (n == 1) {
                bits[0][0] = '0';
                bits[1][0] = '1';
        }

        int i, j; //print array
    int x = pow (2, n);
        for (i=0; i<x; i++) {
                for (j=0; j<n; j++) {
                        printf("%c", bits[i][j]);
                }
        printf(" ");
        }
}

int main(int argc, char *argv[]) {
        if (argc != 2) {
                printf("Invalid number of arguments ");
                return 0;
        }

        int n;
        n = atoi (argv[1]);

        if (n > 8 || n <= 0) {
                printf("Invalid integer ");
                return 0;
    }

        gcodes (n);
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.