Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight $u \oplus v$ (where $\oplus$ is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.


-----Input-----

The only line contains an integer n (2 ≤ n ≤ 10^12), the number of vertices in the graph.


-----Output-----

The only line contains an integer x, the weight of the graph's minimum spanning tree.


-----Example-----
Input
4

Output
4


-----Note-----

In the first sample: [Image] The weight of the minimum spanning tree is 1+2+1=4.

Difficulty: HARD
Tags: Bit manipulation

Graph algorithms

Implementation

Dynamic programming

Mathematics
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
a = 0
n = int(input()) - 1
for i in range(40):
	k = 1 << i
	a += (n + k) // (k * 2) * k
print(a)


a = int(input())

def ans(n, p=1):
	return ans((n + 1) // 2, p * 2) + n // 2 * p if n > 1 else 0
print(ans(a))


n = int(input())
(a, t) = (n - 1, 1)
n -= 1
i = 2
while i <= n:
	a += n // i * t
	i *= 2
	t *= 2
print(a)


n = int(input().strip())
res = 0
i = 1
n -= 1
while i <= n:
	res += ((n - i) // (i << 1) + 1) * i
	i <<= 1
print(res)


from sys import stdin, stdout
n = int(stdin.readline())
psze = 41
ans = 0

def trans(s):
	cnt = 0
	for i in range(psze * 2):
		if i < len(s) and s[i] == '1':
			cnt += 1 << i
	return cnt
n -= 1
for i in range(psze):
	if 1 << i > n:
		break
	s = '0' * i + '1'
	cnt = 1
	(l, r) = (0, n + 1)
	while r - l > 1:
		m = l + r >> 1
		f = bin(m)[2:][::-1]
		if trans(s + f) <= n:
			l = m
		else:
			r = m
	ans += (1 << i) * (l + 1)
stdout.write(str(ans))


def gao(n):
	if n == 1:
		return 1
	else:
		return 2 * gao(n // 2) + (n + 1) // 2
while True:
	try:
		n = int(input())
		print(gao(n - 1))
	except BaseException:
		break


n = int(input()) - 1
r = 0
while n != 0:
	zz = 1
	a = 1
	z = 1
	while zz <= n:
		z <<= 1
		zz <<= 1
		zz += 1
		a <<= 1
		a += z
	zz >>= 1
	a -= z
	a >>= 1
	n -= zz
	r += a
	if n:
		n -= 1
		r += z
print(r)


n = int(input())

def pow2(x):
	r = 1
	while x > 0:
		x -= 1
		r *= 2
	return r

def val_pow_2(x):
	lst = []
	lst.append(0)
	for i in range(x):
		lst.append(2 * lst[i] + pow2(i))
	return lst

def lg2(x):
	r = 0
	ans = 1
	while x > 1:
		x = int(x / 2)
		ans *= 2
		r += 1
	return r

def max_pow_2(x):
	ans = 1
	while x > 1:
		x = int(x / 2)
		ans *= 2
	return ans

def func(x, lst):
	if bin(x).count('1') == 1:
		return lst[lg2(x)]
	elif x == 0:
		return 0
	else:
		y = max_pow_2(x)
		return lst[lg2(y)] + y + func(x - y, lst)
lst = val_pow_2(int(lg2(n)))
print(func(n, lst))


def main():
	n = int(input()) - 1
	res = n
	power = 1
	while n // 2 ** power > 0:
		res += n // 2 ** power * 2 ** (power - 1)
		power += 1
	print(res)
main()


n = int(input())
level = 1
res = 0
while n > 1:
	res += level * (n // 2)
	level *= 2
	n = n // 2 + n % 2
print(res)


from math import log
n = int(input()) - 1
divider = 2 ** int(log(n) / log(2))
total = 0
doubled = 0
while divider > 0:
	total += (n // divider - doubled) * divider
	doubled += n // divider - doubled
	divider //= 2
print(total)


import sys
import math
import collections
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
r = sys.stdin.readline
N = int(r())
N -= 1
i = 1
ans = N
while 2 ** i <= N:
	ans += N // 2 ** i * 2 ** (i - 1)
	i += 1
print(ans)


n = int(input()) - 1
dp = [0] * 40
for i in range(1, 40):
	dp[i] = 2 * dp[i - 1] + 2 ** (i - 1)
c = 0
for i in range(40):
	if 1 << i & n:
		c += dp[i] + 2 ** i
print(c)


f = lambda x: f(x // 2) * 2 + (x + 1) // 2 if x else 0
print(f(int(input()) - 1))


def f(n):
	if n == 0:
		return 0
	return 2 ** (n - 1) + 2 * f(n - 1)
f = [0] * 60
for n in range(1, 60):
	f[n] = 2 ** (n - 1) + 2 * f[n - 1]
n = int(input())
ans = 0
for k in range(60, 0, -1):
	if n >= 2 ** k:
		ans += f[k]
		n -= 2 ** k
		if n > 0:
			ans += 2 ** k
print(int(ans))


def slow_cal(x):
	if x == 0:
		return 0
	else:
		return slow_cal(x - 1) + min((x ^ v for v in range(x)))

def med_cal(x):
	if x == 0:
		return 0
	return sum((min((i ^ j for j in range(i))) for i in range(1, x + 1)))

def fast_cal(x):
	res = 0
	for bit in range(50):
		res += (x // (1 << bit) - x // (1 << bit + 1)) * (1 << bit)
	return res
n = int(input()) - 1
print(fast_cal(n))


import sys, queue
try:
	import dev_act_ffc429465ab634
	DEV = True
except:
	DEV = False

def log(*s):
	if DEV:
		print('LOG', *s)

class EJudge:

	def __init__(self, problem='default', reclim=1 << 30):
		self.problem = problem
		sys.setrecursionlimit(reclim)

	def use_files(self, infile='', outfile=''):
		if infile != '':
			self.infile = open(infile)
			sys.stdin = self.infile
		if outfile != '':
			self.outfile = open(outfile, 'w')
			sys.stdout = self.outfile

	def use_bacs_files(self):
		self.use_files(self.problem + '.in', self.problem + '.out')

	def get_tl(self):
		while True:
			pass

	def get_ml(self):
		tmp = [[[5] * 100000 for _ in range(1000)]]
		while True:
			tmp.append([[5] * 100000 for _ in range(1000)])

	def get_re(self):
		s = (0,)[8]

	def get_wa(self, wstr='blablalblah'):
		for _ in range(3):
			print(wstr)
		exit()

class IntReader:

	def __init__(self):
		self.ost = queue.Queue()

	def get(self):
		return int(self.sget())

	def sget(self):
		if self.ost.empty():
			for el in input().split():
				self.ost.put(el)
		return self.ost.get()

	def release(self):
		res = []
		while not self.ost.empty():
			res.append(self.ost.get())
		return res

def tokenized(s):
	word = []
	for ch in s.strip():
		if ch == ' ':
			if word:
				yield ''.join(word)
				word = []
		elif 'a' <= ch <= 'z' or 'A' <= ch <= 'Z' or '0' <= ch <= '9':
			word.append(ch)
		else:
			if word:
				yield ''.join(word)
				word = []
			yield ch
	if word:
		yield ''.join(word)
		word = []
ej = EJudge()
int_reader = IntReader()
fmap = lambda f, *l: list(map(f, *l))
parse_int = lambda : fmap(int, input().split())
n = bin(int(input()) - 1)[2:][::-1]
log(n)
bit_full_cost = [(1 << i) * (i + 1) for i in range(100)]
bit_cost = [1 << i for i in range(100)]
log(bit_cost)
ans = 0
for i in range(len(n)):
	if n[i] == '1':
		if i > 0:
			ans += bit_full_cost[i - 1]
		ans += bit_cost[i]
print(ans)


n = int(input())

def PotenciaDosMasCercana(n):
	if n == 0:
		return (0, 0)
	p = 1
	i = 0
	while p <= n:
		p = p << 1
		i += 1
	return (p >> 1, i - 1)

def C_Conexas(b):
	dp = [int] * 2
	dp[0] = 0
	for i in range(1, b + 1):
		dp[1] = 2 * dp[0] + 2 ** (i - 1)
		dp[0] = dp[1]
	return dp[0]

def main(n):
	(a, b) = PotenciaDosMasCercana(n)
	Ans = 0
	if n == a:
		Ans = C_Conexas(b)
	else:
		(c, d) = PotenciaDosMasCercana(n - a)
		Ans = C_Conexas(b) + main(n - a) + a
	return Ans
print(main(n))


L = input().split()
n = int(L[0]) - 1
k = 0
while 1 << k < n:
	k += 1
ans = 0
for i in range(0, k + 1):
	ans += (1 << i) * ((n + (1 << i + 1) - (1 << i)) // (1 << i + 1))
print(ans)


n = int(input())
ans = 0
_pow = 2
while 2 * n > _pow:
	ans += _pow // 2 * (n // _pow + (1 if n % _pow > _pow // 2 else 0))
	_pow *= 2
print(ans)


n = int(input())
ans2 = [0]
for i in range(1, 64):
	ans2.append(ans2[i - 1] + ans2[i - 1] + pow(2, i - 1))

def ans(n):
	if n == 0:
		return 0
	else:
		length = n.bit_length() - 1
		if n == pow(2, length):
			return ans2[length]
		else:
			return ans2[length] + ans(n - pow(2, length)) + pow(2, length)
print(ans(n))


import math
n = int(input())
ans = 0
cur = 1
while cur < n:
	cnt = math.ceil((n - cur) / (cur << 1))
	ans += cnt * cur
	cur <<= 1
print(ans)


import atexit
import io
import sys
import math
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def main():
	n = int(input())
	ss = 0
	k = 1
	while n > 1:
		ss += k * (n // 2)
		n = math.ceil(n / 2)
		k *= 2
	print(ss)
main()


import math
n = int(input())
level = 1
r = [0, 0, 1, 3]
cnt = 0
while level <= n:
	num = math.ceil(n / level)
	d_ = num // 4
	r_ = num % 4
	cnt += d_ * level * 4
	cnt += r[r_] * level
	level *= 4
print(cnt)


ans = 0
n = int(input())
k = 2 ** 63
lpre = [0]
for i in range(50):
	lpre.append(lpre[-1] * 2 + 2 ** i)
lmax = -1
for i in range(42, -1, -1):
	if n & 2 ** i:
		ans += lpre[i]
		if lmax != -1:
			ans += 2 ** lmax
		lmax = i
print(ans)


n = int(input())
import math
ans = 0
n -= 1
divby = 1
while divby <= n:
	ans += (n + divby) // (divby * 2) * divby
	divby *= 2
print(ans)


n = int(input())
out = 0
mult = 1
while n > 1:
	out += mult * (n // 2)
	n -= n // 2
	mult *= 2
print(out)


import sys
input = sys.stdin.readline
n = int(input())
ans = 0
w = 1
while n > 1:
	cnt = n // 2
	ans += w * cnt
	n = (n + 1) // 2
	w <<= 1
print(ans)


def main():
	import sys
	input = sys.stdin.readline

	def rec(n, k):
		if n == 1:
			return 0
		return n // 2 * k + rec((n + 1) // 2, 2 * k)
	print(rec(int(input()), 1))
	return 0
main()


def f(n):
	if n == 2:
		return 1
	if n == 3:
		return 3
	if n % 2 == 0:
		return 2 * f(n // 2) + n // 2
	else:
		return 2 * f(n // 2 + 1) + n // 2
n = int(input())
print(f(n))


import bisect
MaxN = 64
powers = [1] * MaxN
for i in range(MaxN - 1):
	powers[i + 1] = powers[i] * 2

def solve(x):
	ans = 0
	while x > 0:
		biggest = bisect.bisect(powers, x) - 1
		ans += biggest * powers[biggest - 1]
		x -= powers[biggest]
		if x > 0:
			ans += powers[biggest]
	return ans

def main():
	n = int(input())
	print(solve(n))
main()


nn = input()
n = int(nn)
st = 0
dv = 1
step = []
while dv <= n:
	step.append(dv)
	dv = dv * 2
	st += 1
step.append(dv)
step.append(dv * 2)
otv = 0
f = 1
q = 0
while f != 0:
	if n == 0:
		break
	if n == 1:
		break
	for i in range(len(step)):
		if step[i] > n:
			q = i - 1
			break
	if n == step[q]:
		otv += step[q - 1] * q
		n -= step[q]
	else:
		otv += step[q] + step[q - 1] * q
		n -= step[q]
print(otv)


n = int(input())
n = n - 1
ans = 0
dp = []
dp.append(1)
for i in range(1, 41):
	dp.append(2 * dp[i - 1] + pow(2, i))
for i in range(40, -1, -1):
	if n & 1 << i > 0:
		ans += pow(2, i)
		if i != 0:
			ans += dp[i - 1]
print(ans)


import math
n = int(input())
t = 1
ret = 0
while n > 1:
	ret += t * (n // 2)
	n = math.ceil(n / 2)
	t = t * 2
print(ret)


n = int(input())
ans = 0
a = 1
while n > 1:
	ans += n // 2 * a
	n = (n + 1) // 2
	a *= 2
print(ans)


n = int(input())
res = 0
inc = 1
while n > 1:
	res += inc * (n // 2)
	n += 1
	n //= 2
	inc *= 2
print(res)


import sys
input = sys.stdin.readline
n = int(input())
n -= 1
ans = 0
for i in range(50):
	ans += (n // (1 << i) - n // (1 << i + 1)) * (1 << i)
print(ans)


import sys
n = int(sys.stdin.readline())
L = [0, 1]
for i in range(1, 48):
	L.append(2 * L[i] + 2 ** i)
B = bin(n - 1)[2:]
result = 0
l = len(B)
for i in range(0, len(B)):
	if B[i] == '1':
		result = result + 2 ** (l - 1 - i) + L[l - 1 - i]
print(result)
L


a = [0]
cur = 1
while cur < 10 ** 13:
	x = a[-1]
	a.append(x * 2 + cur)
	cur *= 2
n = int(input())
n -= 1
ans = 0
i = 1
cur = 1
while n > 0:
	x = n % 2
	n = n // 2
	if x > 0:
		ans += cur + a[i - 1]
	i += 1
	cur *= 2
print(ans)


n = int(input())
n -= 1
tot = n // 2
ans = 0
ans += n - tot
mask = 1
while mask <= 40:
	curr = 1 << mask
	strt = curr // 2
	cnt = (tot - strt) // curr + 1
	ans += curr * cnt
	mask += 1
print(ans)


def func(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n % 2:
		return func(n // 2) * 2 + n // 2 + 1
	else:
		return func(n // 2) * 2 + n // 2
n = int(input())
a = [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1]
print(func(n - 1))


n = int(input())
c = 0
for i in range(39, 0, -1):
	s = pow(2, i)
	if s <= n:
		n -= s
		c += s // 2 * i
		if n != 0:
			c += s
print(c)


from math import log2, ceil
n = int(input())
out = 0
n -= 1
for i in range(ceil(log2(n)) + 1):
	out += ((n - 2 ** i) // 2 ** (i + 1) + 1) * 2 ** i
print(out)