The code, this page, and regexp strings on this page is
Copyright © 2000,2001,2002,2006,2007 Jim E. Michaels, All rights reserved.
...and strictly for my own personal use when I am out and about
writing programs. I may loosen the restrictions later. For
now, this makes some of my services worth something. Email me at jmichae3 att yahoo dott com if you want to use it.

[Bin2Gray] | [Gray2Bin] | [PrintBits]

binary-to-gray-code algorithm

Someday I'll work on analyzing the bit patterns to determine how to make such a device implementable in HW. I think I am close. I am sure it's been done, but I don't see it published anywhere yet. Strange how something as useful as this is not in the textbooks I had in college.

unsigned LeftmostOneBit(unsigned n, unsigned bitLength)
{
	//work from msb to lsb, storing bits as '1' or '0' in a string.
	for (unsigned bitMask = (1 << (bitLength - 1)); bitMask != 0U; bitMask >>= 1) {
		if ((n & bitMask) != 0U) {
			return bitMask;
		}
	}
	return (unsigned)0;  //should never get here unless n=0.
}



unsigned RightmostOneBit(unsigned n, unsigned bitLength)
{
	//work from lsb to msb, storing bits as '1' or '0' in a string.
	for (unsigned bitMask = 1; (bitMask <= (1 << (bitLength - 1))) && (bitMask != (unsigned)0); bitMask <<= 1) {
		if ((n & bitMask) != 0U) {
			return bitMask;
		}
	}
	return (unsigned)0;  //should never get here unless n=0.
}

unsigned BinaryToGrayCode(unsigned n, unsigned bitLength)
{
    //not recommended for high-speed operations - very bit-manip intensive.
    //this IS recommended for creating in HW - should be VERY fast.
    //simply move from lsb to msb-1, where newcurrentbit = currentBit XOR nextbit
    //notice the msb is always copied without modification.
    //buggy for now.
    unsigned result = 0;
    unsigned bitMask = 1<<0;
    unsigned nextBitMask = 1<<1;

    while (nextBitMask <= bitLength) {
        result |= (((n ^ nextBitMask) >> 1) ^ (n ^ bitMask));
        bitMask <<= 1;
        nextBitMask <<= 1;
    }
    return result;
}

//the fastest algorithm yet.
unsigned BinaryToGrayCode2(unsigned n)
{
	return n ^ (n >> 1);
}

//the fastest algorithm yet.
unsigned GrayCodeToBinary2(unsigned gray, unsigned bin)
{
	return gray ^ (bin >> 1);
}

//gray code test rig
int main(int argc, char* argv[])
{
	int i;
	for (i=0; i < 32; i++) {
		printbits(i,5);putchar(' ');
		printbits(BinaryToGrayCode2(i),5);putchar(' ');
		printbits(GrayCodeToBinary2(BinaryToGrayCode2(i), i),5);printf("\n");
	}
	return 0;
}

This concept in HW doesn't really need a shift register, just bits in the right places.

and I just saw I can optimize by eliminating the redundant msb xor.
The nice thing about this is that it has a minimal propogation delay.
It is probably prone to glitches though.

gray-code-to-binary algorithm

//the fastest algorithm yet.
unsigned GrayCodeToBinary2(unsigned g, unsigned b)
{
	return g ^ (b >> 1);
}

Somehow I think that this gray-code-to-binary algorithm and associated circuit I wrote is totally bogus. it seems that once the bits are in the grey code, I have not yet figured out a mathematical way to bring the gray code back to binary. sorry. so without further ado, here is C code from wikipedia gray code article. I am sure it works. the article does not seem to provide a fast binary-to-gray-code algorithm.

long inverseGray(long n) {
        long ish, ans, idiv;
        ish = 1;
        ans = n;
        while(true) {
                idiv = ans >> ish;
                ans ^= idiv;
                if (idiv <= 1 || ish == 32)
                        return ans;
                ish <<= 1; // double number of shifts next time
        }
   }

printbits

void printbits(unsigned n, unsigned numBits)
{
	int index = 0;
	static char bitstr[129];	//allocate space for null char also
	//work from msb to lsb, storing bits as '1' or '0' in a string.
	for (unsigned bit = 1 << (numBits - 1); bit > 0; bit >>= 1) {
		if ((n & bit) == unsigned(0)) {
			bitstr[index] = '0';
		} else {
			bitstr[index] = '1';
		}
		index++;
		bitstr[index] = '\0';
	}
#ifdef NO_IOSTREAM
	printf("%s",bitstr);
#else
	cout<<bitstr;
#endif
}

void printbit(unsigned n) { putchar('0'+n);}

void printbits(unsigned n, int nbits) {
	int i;
	for (i=nbits-1; i>=0; i--) {
		printbit( (n & (1<<i)) >>i);
	}
}