public List<Integer> grayCode(int n) {
List<Integer> result = new LinkedList<>();
for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1);
return result;
}
The idea is simple. G(i) = i^ (i/2).
Just added information for those who are interested (all credited to Wiki gray code
/*
The purpose of this function is to convert an unsigned
binary number to reflected binary Gray code.
The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}
/*
The purpose of this function is to convert a reflected binary
Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
unsigned int mask;
for (mask = num >> 1; mask != 0; mask = mask >> 1)
{
num = num ^ mask;
}
return num;
}
I don't know how to come up with the solution i^(i>>1)
, but I will try to explain why it works.
Adding one to a number results in flipping all the bits from the rightmost zero bit to the end, e.g. 110011 + 1 = 110100
In the general form, i = ...?01...1, i+1 = ...?10...0
, ?
represents the left bit of the rightmost zero bit, the length of tailing one bits of i
is the same as the length of tailing 0 bits of i+1
, and the bits from the beginning to the ?
are the same.
Then i^(i>>1) = xxx(?^0)10...0, (i+1)^((i+1)>>1) = xxx(?^1)10...0
. Since the bits from the beginning to the ?
are the same, xxx
part of both results must be same, it's obvious the tailing parts of 10...0
must be same, and its length is the same as the length of tailing one bits of i
, so there is only one bit difference comes from (?^0)
and (?^1)
.
It's beautiful
@Fanchao I don't know this idea and build another more complicated solution, but it works.
I think you provide incomplete code.
grayCodeList cannot be empty before you try to call get()
@angarita said in An accepted three line solution in JAVA:
You don't need to know what Grey Code is nor bit* operations. You can simply do the following equivalent algorithm:
int x = 2;
for(int i=0; i<n-1; i++) {
for(int j=grayCodeList.size()-1; j>=0; j--)
grayCodeList.add(grayCodeList.get(j) + x);
x *=2;
}
@newdev You're right. This code is for n>=2 and the list already contains elements 0 and 1