For all x in the range of integers [0, 2 ** n), let y[x] be the binary exclusive-or of x and x // 2. Find the sum of all numbers in y.

Write a function sum_them that, given n, will return the value of the above sum.

This can be implemented a simple loop as shown in the initial code. But once n starts getting to higher numbers, such as 2000 (which will be tested), the loop is too slow.

There is a simple solution that can quickly find the sum. Find it!

Assume that n is a nonnegative integer.

Hint: The complete solution can be written in two lines.

Difficulty: introductory

Starter code:

def sum_them(n):
	

Solutions:
def sum_them(n):
    return 2 ** (n - 1) * (2 ** n - 1)

sum_them=lambda n: int('1'*n, 2)*(int('1'*n, 2)+1)//2 if n else 0

def sum_them(n):
    return  2 ** (n*2-1) - 2 ** (n-1)

sum_them=lambda n:int(n*'1'+~-n*'0'or'0',2)

def sum_them(n):
  return 2**n*(2**n-1)>>1

def sum_them(n):
    return n and int('1' * n + '0' * (n-1), 2)

sum_them=lambda n:~-2**n*2**~-n

def sum_them(n):
    return ((1 << n) - 1) << (n - 1) if n > 0 else 0

def sum_them(n):
    n=2**n
    return (n*(n-1))//2

def sum_them(n):
    return (1 << n) - 1 << (n - 1 if n else 0)