CODEWITHSUNDEEP
cbit-manipulation
user3575075
user3575075

Reputation: 63

C code for generating next bit to flip in a gray code

I need a function that returns a number essentially telling me which bit would be the one to flip when moving to the nth element of a Gray code. It doesn't matter if it's the standard (reflecting) Gray code or some other minimal bit-toggling approach. I can do it, but it seems unnecessarily unwieldy. Currently I have this:

#include <stdio.h>

int main()
{
        int i;
        for (i=1; i<32; i++)
                printf("%d\n",grayBitToFlip(i));
}


int grayBitToFlip(int n)
{
        int j, d, n1, n2;

        n1 = (n-1)^((n-1)>>1);
        n2 = n^(n>>1);
        d = n1^n2;
        j = 0;
        while (d >>= 1)
                j++;
        return j;
}

The loop in main() is only there to demonstrate the output of the function.

Is there a better way?

EDIT: just looking at the output, it's obvious one can do this more simply. I've added a 2nd function, gray2, that does the same thing much more simply. Would this be the way to do it? This is not production code by the way but hobbyist.

#include <stdio.h>

int main()
{
        int i;
        for (i=1; i<32; i++)
                printf("%d  %d\n",grayBitToFlip(i), gray2(i));
}


int grayBitToFlip(int n)
{
        int j, d, n1, n2;

        n1 = (n-1)^((n-1)>>1);
        n2 = n^(n>>1);
        d = n1^n2;
        j = 0;
        while (d >>= 1)
                j++;
        return j;
}

int gray2(int n)
{
        int j;
        j=0;
        while (n)
                {
                if (n & 1)
                        return j;
                n >>= 1;
                j++;
                }
        return j;
}

Upvotes: 1

Views: 719

Answers (1)

ekim
ekim

Reputation: 9

The easiest Gray code to use is a Johnson Gray Code (JGC). 

BitNumberToFlip = ++BitNumberToFlip  % NumberOfBitsInCode;

JGC = JGC ^ (1 << BitNumberToFlip);         // start JGC = 0;

A Johnson code is linear in the number of bits required for representation.
A Binary Reflected Gray Code (BRGC) has a much better bit density since only a logarithmic number of bits are required to represent the range of BRGC codes. 

int powerOf2(int n){ return          //   does 16 bit codes
           ( n & 0xFF00 ? 8:0 )  +   //    88888888........
           ( n & 0xF0F0 ? 4:0 )  +   //    4444....4444....
           ( n & 0xCCCC ? 2:0 )  +   //    22..22..22..22..
           ( n & 0xAAAA ? 1:0 )  ; } //    1.1.1.1.1.1.1.1.
                           // much faster algorithms exist see ref.

int BRGC(int gc){ return (gc ^ gc>>1);} 

int bitToFlip(int n){ return powerOf2( BRGC( n ) ^ BRGC( n+1 ) ); }

for details see ref:
How do I find next bit to change in a Gray code in constant time?

Upvotes: 0

Related Questions