Given a number X find the total numbers A such that A XOR X >= X,  and 1<=A<=X.
 
Example 1:
Input: 10
Output: 5
Explanation: Calculating XOR of 10 with
{1, 4, 5, 6, 7} give values greater than 
equal to 10.
Example 2:
Input: 5
Output: 2
Explanation: Calculating XOR of 5 with 
{2, 3} give values greater than 5.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function maximize_xor_count() which takes X as input parameter and returns total numbers A.
 
Expected Time Complexity: O(log(n))
Expected Space Complexity: O(1)
 
Constraints:
1 <= X <= 10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

	def maximize_xor_count(self, n):

		# Code here



Solutions:
class Solution:

	def maximize_xor_count(self, n):
		ans = 0
		k = 1
		while n:
			if n & 1 == 0:
				ans += k
			n >>= 1
			k <<= 1
		return ans


class Solution:

	def maximize_xor_count(self, n):
		pos = 0
		c = 0
		while n:
			if n & 1 == 0:
				c += 2 ** pos
			pos += 1
			n >>= 1
		return c


class Solution:

	def maximize_xor_count(self, n):
		i = 1
		count = 0
		while n > 0:
			if not n & 1:
				count += i
			n = n >> 1
			i = i * 2
		return count


class Solution:

	def maximize_xor_count(self, n):
		count = 0
		num = 1
		while n > 0:
			if n & 1 == 0:
				count += num
			n = n >> 1
			num = num << 1
		return count


class Solution:

	def maximize_xor_count(self, n):
		s = len(bin(n)) - 2
		return 2 ** s + ~n