C# - different bit trick with explaination


  • 0

    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);
        }
    

Log in to reply
 

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