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.

Source: codewars | Difficulty: MEDIUM
Tags: Fundamentals

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'


import math

def f(b, n):
	if b == 2:
		return '01'[n]
	elif 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'


def mystery(n):
	return n ^ n // 2
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('(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
	p = 1 << n.bit_length()
	result = 0
	while p > 1:
		p >>= 1
		if n & p != 0:
			b = 1 - b
		result = (result << 1) + b
	return result

def name_of_mystery():
	return 'Gray code'