C# bit manipulation solution after observation


  • 0
    H

    Gray Code Rule : code[i] = code[i-1] xor mask; (mask is a number only has one bit set to 1)

    As N = 3, list the code , mask, sequence number as below

    I notice the relation between mask and SeqNumber: mask bit = last bit of SeqNumber that is 1

    CODE    Mask    No.[0,1,2...]
    000      000      000
    001      001      001
    011      010      010
    010      001      011
    110      100      100
    111      001      101
    101      010      110
    100      001      111
    

    C# Code:

    public IList<int> GrayCode(int n) {
        
        int max = 1 << n;
        
        var arr = new int[max];
        
        var cur = 0;
        
        for (var i = 0; i < max; i++)
        {
            // i & -i will generate the mask bit
            cur ^= i & -i;
            
            arr[i] = cur;
        }
        
        return arr;
    }

Log in to reply
 

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