This library is for generating Gray codes. A Gray code over $n$ bits is a list of $2^n$ different $n$-bit strings subject to the following constraint: two adjacent bit string differ in only one position. For example, the Gray code over four bits is


0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000


Without further ado, let's proceed to code.

GrayCode.java

package net.coderodde.graycode;

import java.util.BitSet;

/**
 * This class holds the Gray code.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public final class GrayCode 

 private final BitSet code;
 private final int bits;

 GrayCode(BitSet code, int bits) 
 this.code = code;
 this.bits = bits;
 

 public boolean isValid() 
 if (getNumberOfBits() == 0) 
 return code.length == 0;
 

 int rowLength = getNumberOfBits();
 BitSet previousRow = getRow(0);

 for (int row = 1; row < getNumberOfRows(); row++) 
 BitSet currentRow = getRow(row);

 if (getDifferenceCounts(previousRow, currentRow) != 1) 
 return false;
 

 previousRow = currentRow;
 

 return true;
 

 public int getNumberOfBits() 
 return bits;
 

 public int getNumberOfRows() 
 return this.code.length;
 

 public BitSet getRow(int index) 
 BitSet bitSet = new BitSet(getNumberOfBits());

 for (int i = 0; i < bits; ++i) 
 bitSet.set(i, code[index].get(i));
 

 return bitSet;
 

 public boolean readBit(int row, int column) 
 return code[row].get(column);
 

 @Override
 public String toString() 
 StringBuilder stringBuilder = new StringBuilder();
 String rowSeparator = "";

 for (int row = 0; row < code.length; ++row) 
 stringBuilder.append(rowSeparator);
 rowSeparator = "n";
 rowToBitString(stringBuilder, code[row]);
 

 return stringBuilder.toString();
 

 private void rowToBitString(StringBuilder stringBuilder, BitSet bitSet) 
 for (int i = 0; i != bits; ++i) 
 stringBuilder.append(bitSet.get(i) ? '1' : '0');
 
 

 private int getDifferenceCounts(BitSet row1, BitSet row2) 
 int differenceCount = 0;

 for (int i = 0; i < bits; ++i) 
 if (row1.get(i) != row2.get(i)) 
 differenceCount++;

 if (differenceCount == 2) 
 return differenceCount;
 
 
 

 return differenceCount;
 

GrayCodeGenerator.java

package net.coderodde.graycode;

import java.util.BitSet;

/**
 * This class provides a method for generating Gray code over particular number
 * of bits.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public class GrayCodeGenerator 

 public static GrayCode generate(int bits) 
 checkBits(bits);

 if (bits == 0) 
 return new GrayCode(new BitSet[0], 0);
 

 BitSet bitSetArray = new BitSet[getNumberOfBitStrings(bits)];

 for (int i = 0; i != bitSetArray.length; ++i) 
 bitSetArray[i] = new BitSet(bits);
 

 bitSetArray[1].set(bits - 1);

 for (int bitIndex = bits - 1, columnHeight = 2, width = 1;
 bitIndex > 0;
 bitIndex--, columnHeight <<= 1, ++width) 
 // Mirror down:
 for (int row1 = columnHeight,
 row2 = columnHeight - 1;
 row1 < (columnHeight << 1); 
 row1++,
 row2--) 
 for (int w = bits - 1; w > bitIndex - 1; w--) 
 bitSetArray[row1].set(w, bitSetArray[row2].get(w));
 
 

 // Fill the prefix bits:
 for (int row = columnHeight; row < (columnHeight << 1); ++row) 
 bitSetArray[row].set(bitIndex - 1);
 
 

 return new GrayCode(bitSetArray, bits);
 

 /**
 * Returns the number of rows in the Gray code over @code bits bits.
 * 
 * @param bits the number of bits.
 * @return the number of rows in the resulting Gray code.
 */
 private static int getNumberOfBitStrings(int bits) 
 return 1 << bits;
 

 /**
 * Checks that the number of bits is not negative.
 * 
 * @param bits the number of bits to check.
 */
 private static void checkBits(int bits) 
 if (bits < 0) 
 throw new IllegalArgumentException(
 "Negative number of bits requested: " + bits);
 
 

GrayCodeDemo.java

package net.coderodde.graycode;

/**
 * This class implements a sample Gray code demonstration.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public final class GrayCodeDemo 

 public static void main(String args) 
 GrayCode grayCode = GrayCodeGenerator.generate(4);
 System.out.println(grayCode);
 System.out.println("Valid Gray code: " + grayCode.isValid());
 

GrayCodeTest.java

package net.coderodde.graycode;

import java.util.BitSet;
import org.junit.Test;
import static org.junit.Assert.*;

public class GrayCodeTest 

 @Test
 public void test() 
 GrayCode grayCode = GrayCodeGenerator.generate(2);
 assertEquals(4, grayCode.getNumberOfRows());
 assertEquals(2, grayCode.getNumberOfBits());
 System.out.println(grayCode);
 assertTrue(grayCode.isValid());

 // Check first column:
 assertFalse(grayCode.readBit(0, 0));
 assertFalse(grayCode.readBit(1, 0));
 assertTrue(grayCode.readBit(2, 0));
 assertTrue(grayCode.readBit(3, 0));

 // Check second column:
 assertFalse(grayCode.readBit(0, 1));
 assertTrue(grayCode.readBit(1, 1));
 assertTrue(grayCode.readBit(2, 1));
 assertFalse(grayCode.readBit(3, 1));

 BitSet row1 = grayCode.getRow(1);
 assertFalse(row1.get(0));
 assertTrue(row1.get(1));
 

 @Test
 public void bruteForceTest() 
 for (int bits = 0; bits < 12; bits++) 
 assertTrue(GrayCodeGenerator.generate(bits).isValid());
 
 

Critique request

Please tell me anything that comes to mind. I am most interested in comments regarding the API design.

As interface design is pivotal in type design, I'm happy to start there -

let me refer to java.util.BitSet. In no uncertain terms, the documentation summarises in just two sentences what BitSet is about: element access and

bulk boolean operations (see java.math.BigInteger for something irritatingly similar)

(leaving out summaries (cardinality() and intersects​(BitSet other)) and paraphernalia).

I like that it is possible to have non-reflected binary codes - assuming a
GrayCode(int nBits, long ... codes): new GrayCode(3, 0, 1, 3, 7, 6, 4).

I second AJD in preferring a constructor with a single int parameter as an alternative to a separate generator class for reflected binary Gray codes.

With that change, the whole API collapses to public boolean GrayCode.isValid() - which in itself is weird:

Objects should be constructed in a valid state and never get invalid if that can be helped.

(Another hint about the API is the lack of documentation - compare to BitSet.)

Then, there is implementation:

• getRow() could just return (BitSet) code[index].clone();




• int getDifferenceCount(BitSet row1, BitSet row2) 
   BitSet bits = (BitSet) row1.clone();
   bits.xor(row2);
   return bits.cardinality();
  
  

isValid() needs to initialise BitSet previousRow = getRow(getNumberOfRows()-1); and start from 0 to check every transition - but even that is just one necessary condition where a second comes to mind: no code may repeat. (I don't know better that to sort with a "throwing comparator".)

Personally, I would have put the generator code (and helper functions) within the GrayCode class, not within its own class. A key point here is that there is not initialiser for the GrayCodeGenerator class.
You can then use this to see if the gray code has been set - useful for avoiding programming errors where the future code declares a GrayCode but does not generate with it.
You could also use this for a new constructor where only a number of bits is passed, and the GrayCode class then automatically generates the BitSet. Yes, you could also do this with the current code, but having the generator inside the GrayCode class will make it neater.

What is a bit missing, is the logic / proof / explanation. And it is generative, creating a sequence.

Hence one could look at an immediate mapping function:

static int grayCode(int n) grayCode(high - 1 - lows); // Reverse order backwards

• Proof can be done by induction because of the recursion.


• The recursion can be resolved a bit. (Also generative with a non-tail recursion.)


• An explanation is simple too:

Having a valid sequence of 0 .. 2^k - 1, the following 2^k numbers can be retrieved by reversing the list and adding a bit 1 in front: every step also flips one single bit.

I did not want to spoil this nice usage of BitSet, but Gray Codes seem useful, like de-Bruijn sequences.