The `mystery` function is defined over the non-negative integers. The more common name of this function is concealed in order to not tempt you to search the Web for help in solving this kata, which most definitely would be a very dishonorable thing to do.

Assume `n` has `m` bits. Then `mystery(n)` is the number whose binary representation is the entry in the table `T(m)` at index position `n`, where `T(m)` is defined recursively as follows:

```
T(1) = [0, 1]
```

`T(m + 1)` is obtained by taking two copies of `T(m)`, reversing the second copy, prepending each entry of the first copy with `0` and each entry of the reversed copy with `1`, and then concatenating the two. For example:

```
T(2) = [ 00, 01, 11, 10 ]
```

and

```
T(3) = [ 000, 001, 011, 010, 110, 111, 101, 100 ]
```

`mystery(6)` is the entry in `T(3)` at index position 6 (with indexing starting at `0`), i.e., `101` interpreted as a binary number. So, `mystery(6)` returns `5`.

Your mission is to implement the function `mystery`, where the argument may have up to 63 bits. Note that `T(63)` is far too large to compute and store, so you'll have to find an alternative way of implementing `mystery`. You are also asked to implement `mystery_inv` ( or `mysteryInv` ), the inverse of `mystery`. Finally, you are asked to implement a function `name_of_mystery` ( or `nameOfMystery` ), which shall return the name that `mystery` is more commonly known as. After passing all tests you are free to learn more about this function on Wikipedia or another place.

Hint: If you don't know the name of `mystery`, remember there is information in passing as well as failing a test.

Difficulty: interview

Starter code:

def mystery(n):
	

Solutions:
def mystery(n):
    return n ^ (n >> 1)

def mystery_inv(n):
    mask = n >> 1
    while mask != 0:
        n = n ^ mask
        mask = mask >> 1
    return n;

def name_of_mystery():
    return "Gray code"

def mystery(n):
    return n ^ (n >> 1)

def mystery_inv(n):
    mask = n >> 1
    while mask:
        n = n^mask
        mask = mask >> 1
    return n

def name_of_mystery():
    return "Gray code"

import math
def f(b,n):
    if b==2: return '01'[n]
    else:
        if n>=b//2: return '1'+f(b//2,b//2-1-(n-b//2))
        else: return '0'+f(b//2,n)
def mystery(n):
    if n==0: return 0
    b=2**(int(math.log(n,2))+1)
    a=f(b,n)
    return (int(a,2))
    

def mystery_inv(n):
    if n==0: return 0
    s=bin(n)[2:]
    x=0
    for i in range(len(s)):
        if int(s[len(s)-1-i]): x=(2**i)+(2**i-1-x)
    return x 
def name_of_mystery():
    return 'Gray code'

mystery=lambda n:n ^ (n >> 1)
mystery_inv=lambda n,i=0,li=[0]:int(''.join(map(str,li)),2) if i==len(bin(n)[2:]) else mystery_inv(n,i+1,li+[int(li[-1])^int(bin(n)[2:][i])])
name_of_mystery=lambda:'Gray code'

def dec_to_bin(num):
    if num <= 0:
        return '0'

    bits = ''
    while num > 0:
        bits = str(num % 2) + bits
        num = num / 2
        
    return bits
    
def bin_to_dec(binary):
    dec = 0
    power = 0
    for b in reversed(binary):
        dec += int(b) * 2 ** power
        power += 1
        
    return dec
    
def mystery(num):
    b = dec_to_bin(num)
    out = ''
    reverse = False
    for bit in b:
        if not reverse:
            out += bit
        else:
            out += '0' if bit == '1' else '1'
            
        reverse = not reverse if out[-1] == '1' else reverse    
            
    return bin_to_dec(out)
    
def mystery_inv(num):
    if num == 0:
        return num

    b = dec_to_bin(num)
    out = ''
    reverse = b[0] == '0'
    for bit in b:
        if not reverse:
            out += bit
        else:
            out += '0' if bit == '1' else '1'
            
        reverse = not reverse if bit == '1' else reverse
        
    return bin_to_dec(out)

def name_of_mystery():
    return 'Gray code'

def mystery(n):
    return n ^ (n >> 1)

def mystery_inv(n):
    res = 0
    while n > 0:
        res ^= n
        n >>= 1
    return res

def name_of_mystery():
    return 'Gray code'

mystery = lambda n: n ^ (n >> 1)
def mystery_inv(n):
    m = n >> 1
    while m != 0:
        n ^= m
        m >>= 1
    return n
name_of_mystery = lambda: 'Gray code'

""" 
    When you do know almost nothing about bitwise operators except of their existence...
    ...and that you make by chance a good guess... 
"""
def mystery(n):  return n ^ (n//2)


"""
    Then you do some pattern recognition to solve the kata! 
"""
import re, string
TABLE = string.maketrans('01', '10')

def mystery_inv(n):
    return int(''.join( a+b.translate(TABLE)+c for a,b,c in re.findall(r'(1)(0*1?)(0*)', bin(n)[2:]) ) or '0', 2)
    

def name_of_mystery(): return "Gray code"

def mystery(n):
    return n^n>>1

def mystery_inv(n):
    i = n>>1
    while i > 0:
        n ^= i
        i >>= 1
    return n

def name_of_mystery():
    return "Gray code"

def mystery(n):
    return n ^ (n >> 1)

def mystery_inv(n):
    b = 0 #next bit to append to result
    p = 1 << (n).bit_length() #power of 2 greater than n
    result = 0
    while p > 1:
        p >>= 1
        if n & p != 0: b = 1 - b #flip bit when a 1 is in corresponding bit position in n
        result = (result << 1) + b
    return result

def name_of_mystery():
    return 'Gray code'