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

Question

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;
}

For working code, codereview.stackexchange.com is a good place. — chux
– chux, Commented Dec 12, 2015 at 4:59
Doesn't work for me. All it does is select the least significant 1 bit. The way to test a gray-code generator is to flip the bit, and then feed the resulting value into the generator. For example, starting with binary 0000, the bit to flip is 0, so the new value is 0001. Give that to the generator and the bit to flip is 0 again. So the value toggles between 0000 and 0001. As another example, start with 1111 and the sequence generated is 1110, 1100, 1000, 0000, 0001, 0000, 0001, ... That's not a gray code. — user3386109
– user3386109, Commented Dec 12, 2015 at 5:25
If you want to find the 1st "1" bit and the string of bits is long, there are some optimizations. Otherwise, about gray code generation. — Déjà vu
– Déjà vu, Commented Dec 12, 2015 at 5:30
The bit to flip in a gray-code is the same bit to which the first carry reaches in regular binary counting. So the pattern is 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 ... — Bryan Olivier
– Bryan Olivier, Commented Dec 12, 2015 at 7:59
The mask for the lowest-order 1-bit in n is n&-n. If your time intent is to flip the bit, that is what you need. (But I guess n needs to start at 1.) If you need the index of the bit, you can use a clz instruction. See the ffs function. — rici
– rici, Commented Dec 12, 2015 at 12:53

Community · Accepted Answer · 2017-05-23 12:17:23Z

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?

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related