Given an integer $n$, find each $\boldsymbol{x}$ such that:

$0\leq x\leq n$
$n+x=n\oplus x$

where $\oplus$ denotes the bitwise XOR operator. Return the number of $\boldsymbol{x}$'s satisfying the criteria.

Example 

$n=4$   

There are four values that meet the criteria:  

$4+0=4\oplus0=4$
$4+1=4\oplus1=5$
$4+2=4\oplus2=6$
$4+3=4\oplus3=7$    

Return $4$.  

Function Description

Complete the sumXor function in the editor below.  

sumXor has the following parameter(s): 

- int n: an integer   

Returns 

- int: the number of values found   

Input Format

A single integer, $n$.

Constraints

$0\leq n\leq10^{15}$

Subtasks

$0\leq n\leq100$ for $\textbf{60\%}$ of the maximum score.

Output Format

Sample Input 0

5

Sample Output 0

2

Explanation 0

For $n=5$, the $\boldsymbol{x}$ values $\mbox{0}$ and $2$ satisfy the conditions:

$5+0=5,\:\:5\oplus0=5$
$5+2=7,\:\:5\oplus2=7$

Sample Input 1

10

Sample Output 1

4

Explanation 1

For $n=10$, the $\boldsymbol{x}$ values $\mbox{0}$, $\mbox{1}$, $4$, and $5$ satisfy the conditions:

$10+0=10,~~10\oplus0=10$
$10+1=11,~~10\oplus1=11$
$10+4=14,~~10\oplus4=14$
$10+5=15,~~10\oplus5=15$

Difficulty: EASY
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
import sys
n = int(input().strip())
print(1 if n == 0 else 1 << bin(n)[2:].count('0'))


import sys
n = int(input().strip())
num_bits = 0
while n:
	if not n & 1:
		num_bits += 1
	n >>= 1
print(1 << num_bits)


import sys
n = int(input().strip())
zeros = 0
while n:
	if not n & 1:
		zeros += 1
	n >>= 1
print(2 ** zeros)


import sys
count = 1
n = int(input().strip())
for i in range(64):
	if n < 1 << i:
		break
	if n & 1 << i == 0:
		count *= 2
print(count)


import sys
n = int(input().strip())
res = 1
if n > 0:
	base_2_n = format(n, 'b')
	for c in base_2_n:
		if c == '0':
			res *= 2
print(res)


n = int(input().strip())
nbin = str(bin(n))[2:]
zeros = 0
for ch in nbin:
	if ch == '0':
		zeros += 1
if n == 0:
	zeros -= 1
print(2 ** zeros)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	binStr = bin(n)
	numZeros = binStr.count('0') - 1
	print(2 ** numZeros)


n = int(input())
if n == 0:
	print(1)
else:
	c = 2 ** (bin(n).count('0') - 1)
	print(c)


n = int(input().strip())

def num0s(x):
	if x == 0:
		return 0
	return int(x % 2 == 0) + num0s(x // 2)
print(2 ** num0s(n))


n = int(input())
if n == 0 or n == 1:
	print(1)
	exit()
v = bin(n).count('0') - 1
print(2 ** v)


import sys
n = int(input().strip())
if n == 0:
	print(1)
	sys.exit()
n = str(bin(n))[2:]
count = 0
for i in n:
	if i == '0':
		count += 1
print(2 ** count)


import sys
n = int(input().strip())
count = bin(n).count('0') - 1
print(2 ** count) if n > 0 else print(1)


n = int(input())
st = '{0:#b}'.format(n)
if n != 0:
	zeroes = sum([1 for digit in st[2:] if digit == '0'])
	answer = 2 ** zeroes
	print(answer)
else:
	print(1)


import sys
import math
n = int(input().strip())
zeros = []
x = 1
i = 1
while n != 0:
	if n % 2 == 1:
		zeros += [1]
	else:
		zeros += [0]
	i += 1
	n = n >> 1
print(2 ** (len(zeros) - sum(zeros)))


N = int(input().strip())
res = 0
while N:
	if not N & 1:
		res += 1
	N >>= 1
print(2 ** res)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	result = 1
	for c in bin(n)[2:]:
		if c == '0':
			result *= 2
	print(result)


import sys
n = int(input())
if n == 0:
	print(1)
else:
	n = str(bin(n))[2:]
	print(2 ** n.count('0'))


import sys
from collections import Counter
n = int(input().strip())
if n == 0:
	print(1)
else:
	b = Counter(bin(n))
	print(2 ** (b['0'] - 1))


from math import *
n = int(input())
if n == 0:
	print(1)
else:
	n_b = bin(n)[2:]
	nb0_n = sum([1 for i in range(len(n_b)) if n_b[i] == '0'])
	print(int(pow(2, nb0_n)))


import sys
n = int(input().strip())
ans = 1
while n:
	b = n & 1
	if b == 0:
		ans *= 2
	n = n >> 1
print(ans)


import sys
n = int(input().strip())
b = bin(n)
b = str(b[2:])
c = int(b.count('0'))
if n == 0:
	print(1)
else:
	print(2 ** c)


import sys

def dec_to_bin(x):
	return bin(x)[2:]
c = 0
n = int(input().strip())
if n == 0:
	print(1)
	exit(0)
c = list(dec_to_bin(n)).count('0')
print(2 ** c)


num = int(input())
string = bin(num)
counter = 0
for x in range(2, len(string)):
	if string[x] == '0':
		counter += 1
if num == 0:
	print(1)
else:
	print(2 ** counter)


import sys
n = int(input().strip())
nbin = bin(n)[2:]
c = nbin.count('0')
if n != 0:
	print(2 ** c)
else:
	print(1)


import sys
n = int(input().strip())
bin_n = '{0:b}'.format(n)
sum = 1
for i in range(len(bin_n) - 1, 0, -1):
	if str(bin_n[i]) == '0':
		sum *= 2
print(sum)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	a = bin(n)
	z = 0
	for i in range(2, len(a)):
		if a[i] == '0':
			z += 1
	print(pow(2, z))


n = int(input().strip())
print(1 if n == 0 else 1 << bin(n)[2:].count('0'))


n = int(input())
if n <= 0:
	print(1)
else:
	i = bin(n)[2:].count('0')
	print(2 ** i)


n = int(input())
print(2 ** (n.bit_length() - bin(n).count('1')))


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	num1s = bin(n).count('1')
	length = len(bin(n)) - 2
	print(2 ** (length - num1s))


import sys, math
n = int(input().strip())
if n == 0:
	print(1)
else:
	c = math.pow(2, list(bin(n)[2:]).count('0'))
	print(int(c))


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	ans = 1
	while n > 0:
		if n % 2 == 0:
			ans = ans * 2
		n = n // 2
	print(ans)


import sys

def dec_to_bin(x):
	return bin(x)[2:]

def sat_sum_xor(n):
	if n == 0:
		return 1
	bin_number = dec_to_bin(n)
	zero_space = 0
	for digit in bin_number:
		if digit == '0':
			zero_space += 1
	return 2 ** zero_space
n = int(input().strip())
print(sat_sum_xor(n))


n = int(input())
bin_str = bin(n)[2:]
count = 0
for i in range(0, len(bin_str)):
	if bin_str[i] == '0':
		count = count + 1
if n != 0:
	print(2 ** count)
else:
	print('1')


import sys
n = int(input().strip())
count = 0
while n != 0:
	count += 1 if not n % 2 else 0
	n = n // 2
print(int(2 ** count))


n = int(input())
if n == 0:
	print(1)
else:
	s = bin(n)[2:]
	c = sum((c == '0' for c in s))
	if c == 0:
		print(0)
	else:
		print(1 << c)


t = int(input())
a = bin(t)[2:]
b = [1 for i in range(len(a))]
for i in range(len(a)):
	if a[i] == '1':
		b[i] = 0
if t == 0:
	print(1)
else:
	print(2 ** b.count(1))


import sys
n = int(input().strip())
cnt = 0
while n > 0:
	if n % 2 == 0:
		cnt += 1
	n //= 2
print(2 ** cnt)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	s = bin(n)[2:]
	cnt = 0
	for c in s:
		if c == '0':
			cnt += 1
	print(2 ** cnt)


n = int(input())
st = str(bin(n))
st = st[2:]
c0 = st.count('0')
c1 = st.count('1')
if n == 0:
	print(1)
else:
	print(max(1, 2 ** c0))


n = int(input())
print(1 if n == 0 else 2 ** sum((c == '0' for c in bin(n)[2:])))


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	b = str(bin(n))[2:]
	print(2 ** list(b).count('0'))


import sys
import math
n = int(input().strip())
if n == 0:
	print(1)
else:
	num_zeros = 0
	for b in bin(n)[2:]:
		if b == '0':
			num_zeros += 1
	print(2 ** num_zeros)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	binstr = '{0:b}'.format(n)
	binlst = list(binstr)
	nzeros = binlst.count('0')
	print(2 ** nzeros)


import math
import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	number_as_bin = bin(n)[2:]
	zeros = len([char for char in number_as_bin if char == '0'])
	print(int(math.pow(2, zeros)))


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	s = '{0:b}'.format(n)
	count = 0
	for c in s:
		if c == '0':
			count = count + 1
	print(2 ** count)


from collections import Counter
n = int(input().strip())
if n == 0:
	print(1)
else:
	c = Counter(bin(n)[2:])
	print(2 ** c['0'])


n = int(input())
z = bin(n)[3:].count('0')
print(2 ** z)


n = int(input().strip())
if n == 0:
	print(1)
else:
	z = bin(n)[2:].count('0')
	print(2 ** z)


import sys
import math

def dectobin(n):
	s = ''
	i = 0
	r = 1
	while r < n:
		s = ('1' if n & r else '0') + s
		i += 1
		r = int(math.pow(2, i))
	return s
n = int(input().strip())
s = dectobin(n).replace('1', '')
print(int(math.pow(2, len(s))))


import sys
n = int(input().strip())
count = 0
while n != 0:
	if n % 2 == 0:
		count += 1
	n //= 2
print(2 ** count)


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


n = int(input().strip())
if n == 0:
	print(1)
else:
	print(2 ** bin(n)[2:].count('0'))


n = int(input())
binary = bin(n)[2:]
length = binary.count('0')
if n == 0:
	print(1)
else:
	print(2 ** length)


import sys
n = int(input().strip())
c = 0
while n:
	if n % 2 == 0:
		c += 1
	n //= 2
c = 2 ** c
print(c)


import sys
n = int(input().strip())
i = 0
while n:
	if not n & 1:
		i += 1
	n = n >> 1
print(1 << i)


import sys
n = int(input().strip())
cnt = 0
while n != 0:
	if n % 2 == 0:
		cnt += 1
	n = n // 2
print(2 ** cnt)


import sys
n = int(input().strip())
print(1 if n == 0 else 2 ** bin(n)[2:].count('0'))


n = int(input())
s = bin(n)[2:]
exp = 0
if n > 0:
	exp = sum([1 for x in s if x == '0'])
print(2 ** exp)


import sys
n = int(input().strip())

def countZeroBits(n):
	count = 0
	while n:
		count += 1 if not n & 1 else 0
		n >>= 1
	return count

def sumVSxor(n):
	return 2 ** countZeroBits(n)
print(sumVSxor(n))


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	m = len([x for x in bin(n)[2:] if x == '0'])
	print(2 ** m)


import sys
n = int(input().strip())
if n != 0:
	b = bin(n)[2:].count('0')
	print(1 << b)
else:
	print(1)


import sys
n = int(input().strip())
b = n
num = 0
count = 0
while b > 0:
	if b % 2 == 0:
		count += 1
	b = b // 2
print(2 ** count)


import sys
import math
n = int(input().strip())
res = 0
binary_number = bin(n)[2:]
while n > 0:
	if n & 1 == 0:
		res += 1
	n = n >> 1
res = 1 << res
print(res)


import sys
n = int(input().strip())
zeros = len([i for i in bin(n) if i == '0']) - 1
if n == 0:
	print(1)
else:
	print(2 ** zeros)


n = int(input().strip())
s = 0
while n > 0:
	s += 1 if n % 2 == 0 else 0
	n //= 2
print(2 ** s)


import sys
n = int(input().strip())
x = 1
mask = 1
result = 1
while x <= n:
	if n & mask == 0:
		result *= 2
	mask <<= 1
	x |= mask
print(result)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	print(2 ** (bin(n).count('0') - 1))


import sys
n = int(input().strip())
count = 0
while n > 0:
	if 0 == n & 1:
		count += 1
	n >>= 1
print(1 << count)


import sys
n = int(input().strip())
res = 0
while n:
	if n & 1 == 0:
		res += 1
	n >>= 1
print(1 << res)


n = int(input().strip())
ans = 0
ans += 2 ** (bin(n).count('0') - 1)
print(1 if n == 0 else ans)


n = int(input().strip())
k = 0
while n:
	if n % 2 == 0:
		k += 1
	n //= 2
print(2 ** k)


import sys
n = int(input().strip())
if n == 0:
	print(1)
	sys.exit(0)
print(2 ** (bin(n).count('0') - 1))


n = int(input())
print(2 ** sum((1 for b in bin(n)[2:] if b == '0')) if n > 0 else 1)


import sys
n = int(input().strip())
no_zeros = 0
while n > 0:
	if 0 == n & 1:
		no_zeros += 1
	n = n // 2
c = pow(2, no_zeros)
print(c)


import sys
n = int(input().strip())
if not n:
	print(1)
else:
	b = '{0:b}'.format(n)
	print(2 ** b.count('0'))


import sys
import itertools
n = int(input())
bitPosition = 0
numUnsetBits = 0
while 2 ** bitPosition <= n:
	if n & 2 ** bitPosition == 0:
		numUnsetBits += 1
	bitPosition += 1
print(2 ** numUnsetBits)


N = int(input())
if N == 0:
	print(1)
else:
	B = bin(N)[2:].count('0')
	print(2 ** B)


import sys

def bitLen(int_type):
	length = 0
	while int_type:
		int_type >>= 1
		length += 1
	return length
n = int(input().strip())
st = '{0:b}'.format(n)
elev = 0
for v in st:
	if v == '0':
		elev += 1
if n == 0:
	elev -= 1
print(1 << elev)


import sys

def bitCount(n):
	count = 0
	while n:
		count += 1 - (n & 1)
		n >>= 1
	return 2 ** count
n = int(input().strip())
print(bitCount(n))


import sys
n = int(input().strip())
if n:
	l = sum([(int(i) + 1) % 2 for i in bin(n)[2:]])
else:
	l = 0
print(2 ** l)


import sys
n = int(input().strip())
count = 0
while n > 0:
	if n % 2 == 0:
		count += 1
	n = n // 2
print(2 ** count)


n = int(input())
c = 0
while n > 0:
	if n & 1 == 0:
		c += 1
	n >>= 1
print(1 << c)


n = int(input())
zeros = 0
while n > 1:
	if n & 1 == 0:
		zeros += 1
	n >>= 1
print(2 ** zeros)


import sys
n = int(input().strip())
if n > 0:
	zeros = format(n, 'b').count('0')
	total = 2 ** zeros
	print(total)
else:
	print(1)


import sys
n = int(input().strip())
bit = 1
numZero = 0
while bit < n:
	if bit & n == 0:
		numZero += 1
	bit <<= 1
print(2 ** numZero)


n = int(input().strip())
if n == 0:
	print(1)
else:
	string = bin(n)[2:]
	numZeroes = 0
	for i in string:
		if i == '0':
			numZeroes += 1
	print(2 ** numZeroes)


import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	zeros = bin(n).count('0') - 1
	print(2 ** zeros)


import sys
c = 0
n = int(input().strip())
while n:
	if n % 2 == 0:
		c += 1
	n //= 2
c = pow(2, c)
print(c)


import sys
n = int(input().strip())
b_n = bin(n)[2:]
c = b_n.count('0')
if n == 0:
	print(1)
else:
	print(2 ** c)


n = int(input())
numZeroes = 0
while n:
	if n & 1 == 0:
		numZeroes += 1
	n >>= 1
print(1 << numZeroes)


n = int(input().strip())
cnt = 0
while n > 0:
	if n % 2 == 0:
		cnt += 1
	n = int(n / 2)
print(2 ** cnt)


import math
import sys
n = int(input().strip())
if n == 0:
	print(1)
else:
	print(int(math.pow(2, bin(n).count('0') - 1)))


import sys
n = int(input().strip())
zero = 0
bina = bin(n)[2:]
if len(bina) > 1:
	for k in bina:
		if k == '0':
			zero += 1
	print(2 ** zero)
else:
	print(1)


import sys
n = int(input().strip())
n = int(bin(n)[2:])
c = 0
while n > 0:
	if n % 10 == 0:
		c += 1
	n //= 10
print(2 ** c)


n = int(input())
t = [n]
while n > 1:
	x = n // 2
	t.append(x)
	n = x
t.reverse()
i = 1
cur = 1
while i < len(t):
	a = t[i]
	if a % 2 == 0:
		cur = cur * 2
	i = i + 1
print(cur)


import sys
n = int(input().strip())
k = str(bin(n))[2:].count('0')
print(2 ** k if n > 0 else 1)


n = int(input().strip())
num_zeros = 0
while n > 0:
	if 0 == n & 1:
		num_zeros += 1
	n >>= 1
print(1 << num_zeros)


def fuck(n):
	r = []
	while n > 0:
		r.append(n % 2)
		n //= 2
	return r

def main():
	n = int(input())
	b = fuck(n)
	c = b.count(1)
	print(2 ** (len(b) - c))
main()


import sys
import math
n = int(input().strip())

def solve(n):
	if n == 0:
		return 1
	cz = 0
	for i in range(int(math.log(n, 2) + 1)):
		cz += 1 - bool(n & 1 << i)
	return 2 ** cz
print(solve(n))