# C# - different bit trick with explaination

• Here is a way that is a little different.

Let's look at how bits move for case of n = 4, consider first 8 numbers:

``````index 0)  0 0 0 0
index 1)  0 0 0 1
index 2)  0 0 1 1
index 3)  0 0 1 0
index 4)  0 1 1 0
index 5)  0 1 1 1
index 6)  0 1 0 1
index 7)  0 1 0 0
``````

Notice that index 1 can be achieved by taking index 0 and turning on first bit (duh!). Ok, keep going, notice that you can get index 2 by taking index 1 and turning on second bit and index 3 is like index 0 also turning on second bit. We are starting to see a pattern. Let's look at this more clearly.

``````index 0 -> index 0 + 0 bit (this is 0)
index 1 -> index 0 + 1st bit
index 2 -> index 1 + 2nd bit
index 3 -> index 0 + 2nd bit
index 4 -> index 3 + 3rd bit
index 5 -> index 2 + 3rd bit
index 6 -> index 1 + 3rd bit
index 7 -> index 0 + 3rd bit
``````

you can see every power of 2 you are in essence repeating the existing solved elements in reverse order and getting the current value by turning on the next power of 2 bit. This solution leads to the following code.

``````    public IList<int> GrayCode(int n)
{
int len = (int)Math.Pow(2, n);
int[] dp = new int[len];
int posBack = 0;
int nextBit = 0;
for (int i = 1; i < len; i++)
{
bool isPow2 = (i & (i - 1)) == 0;
if (isPow2)
{
posBack = 1;
nextBit = nextBit == 0 ? 1 : (nextBit << 1);
}

dp[i] = dp[i - posBack] | nextBit;
posBack += 2;
}

return new List<int>(dp);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.