python-3.xdata-structuresgray-code

Can anybody explain me print statement in this code?


I found this code on internet but I am not able to understand how the print statement is working.

I have already tried to see many answers but none answers it perfectly.

def main():
    n=int(raw_input())
    for i in range(0, 1<<n):
        gray=i^(i>>1)
        print "{0:0{1}b}".format(gray,n),

main()

Solution

  • for i in range(0, 1<<n):
    Here, 1 << n shifts 1 by n bits to left. It means:
    if n = 1, 1 << 1 would be 10, n = 2, 1 << 10 would be 100 [2 = binary 10]
    and so on.
    For decimal number the answer is equivalent 2 to the power n.
    For binary 'n' number of zeros are added.
    So the range is for i in range(0, 2 ** n).

    gray=i^(i>>1)
    

    Here i>>1 shifts i by 1 bit to right. It means:

       if i = 1, 1 >> 1 would be 0,    
           i = 2, 10 >> 1 would be 1 [2 = binary 10]   
           i = 3, 100 >> 1 would be 10 (in binary) 2 in decimal   
    

    and so on.
    For decimal numbers it is equivalent to dividing by 2 (and ignoring digits after . decimal point).
    For binary last digit is erased.

    ^ is exclusive OR operator. It is defined as:

    0 ^ 0 = 0,     
    0 ^ 1 = 1 ^ 0 = 1,   
    1 ^ 1 = 0  
    
    print "{0:0{1}b}".format(gray,n)
    

    Here {1} refers to n, b refers to binary. So gray is converted to binary and expressed in n digits.