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.

Source: codewars | Difficulty: EASY
Tags: Bit manipulation

Ad-hoc

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


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


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