1

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;
}
user3575075
  • 63
  • 5
  • 3
    For working code, http://codereview.stackexchange.com/ is a good place. – chux - Reinstate Monica Dec 12 '15 at 04:59
  • 1
    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 Dec 12 '15 at 05: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](http://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/). – Déjà vu Dec 12 '15 at 05: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 Dec 12 '15 at 07:59
  • You may also take a look at http://stackoverflow.com/questions/4166106/the-nth-gray-code – Bryan Olivier Dec 12 '15 at 08:14
  • user3386109: the output my program generates is correct, you are wrong to say it doesn't work. Or could you point to a value that you think is mistaken? I was just wondering if there is a more efficient way. Bryan Oliver: yes, the sequence you gave is the output of my program. Do you know a better way to generate it than the 2nd way I posted? ringo: yes, I realised my problem is equivalent to finding the position of the least significant "1" bit. Is there a better way than the one I posted? Thanks all. – user3575075 Dec 12 '15 at 12:37
  • 1
    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 Dec 12 '15 at 12:53
  • @user3575075 I see now that I misunderstood how you intend to use that function to generate the gray code. I agree with the comment by rici, that `int mask = n & -n` gives you a bit mask that can be used to flip the bit. – user3386109 Dec 12 '15 at 19:50
  • Thank you rici and user3386109 for the neat suggestion of a mask of `n & -n`. For my purposes I don't actually need to flip the bit, as I'm using a Gray code for something a bit different and not doing any bit twiddling per se--I just needed to generate the sequence of numbers that _would_ be used if I were doing Gray code. I think the loop in the function above in my edit, gray2(n), will end up being sufficient, as the lowest-order set bit will never be more than 7 or 8 shifts away from the first column. – user3575075 Dec 14 '15 at 01:41
  • First you wrote _The loop in main() is only there to demonstrate the output of the function_, last you wrote _I just needed to generate the sequence of numbers …_. It might matter whether you need one number at a time for a **random** _n_, or all the numbers in sequence, so which way is it? If the former, I think we can't do significantly better in pure C than your `gray2()` does, so you might post that as an answer below. – Armali Mar 09 '16 at 13:27

1 Answers1

1

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?

Community
  • 1
  • 1
ekim
  • 11
  • 2