Given a number N, find the total number of possible X such that (N XOR X) == (N OR X), where 0<=X<=N.
Example 1:
Input: N = 5
Output: 2
Explanation:
5 XOR 2 == 5 OR 2 and 
5 XOR 0 == 5 OR 0
Example 2:
Input: N = 7
Output: 1
Explanation: 7 XOR 0 == 7 OR 0
Your Task:
You don't need to read or print anything. Your task is to complete the function total_count() which takes N as input parameter and returns total count of X. 
 
Expected Time Complexity: O(log(N))
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:
	def total_count(self, n):
		# Code here


Solutions:
class Solution:

	def total_count(self, n):
		cnt = 0
		for i in range(64):
			if 1 << i <= n and 1 << i & n == 0:
				cnt += 1
		return 1 << cnt


class Solution:

	def total_count(self, n):
		num = bin(n)[2:]
		count = 0
		for item in num:
			count += item == '0'
		return 2 ** count


class Solution:

	def total_count(self, n):
		count = 1
		while n:
			if not n & 1:
				count *= 2
			n >>= 1
		return count


class Solution:

	def total_count(self, n):
		count = 0
		while n > 0:
			zero = n % 2
			if zero == 0:
				count += 1
			n = n // 2
		ans = pow(2, count)
		return ans


class Solution:

	def total_count(self, n):
		tmp = n
		count = 1
		while tmp > 0:
			if tmp & 1 == 0:
				count *= 2
			tmp = tmp >> 1
		return count


class Solution:

	def total_count(self, n):
		if n + 1 & n == 0:
			return 1
		s = 0
		while n > 0:
			if n % 2 == 0:
				s = s + 1
			n = n // 2
		return 2 ** s