Given a number X find the total numbers A such that A OR X > X,  and 1<=A<=X.
Example 1:
Input: X = 10
Output: 7 
Explanation: In the range [1,10] if the 
OR is taken of 10 and any number in the 
set {1,3,4,5,6,7,9} the resulting value 
will be greater than 10.
Example 2:
Input: X = 5
Output: 2
Explanation: In the range [1,5] if the
OR is taken of 5 and any number in the
set {2,3} the resulting value
will be greater than 5.
Your Task:  
You dont need to read input or print anything. Complete the function getCount() which takes X as input parameter and returns the the total count of the different value of A possible.
Expected Time Complexity: O(logn)
Expected Auxiliary Space: 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 getCount (ob, X):
        # code here 

Solutions:
class Solution:

	def getCount(ob, X):
		cnt = 0
		for i in range(31):
			if X >= 1 << i:
				if X & 1 << i:
					cnt += 1
		return X - 2 ** cnt + 1


class Solution:

	def getCount(ob, X):
		temp = X
		c = 0
		while X != 0:
			c += X % 2
			X = X // 2
		return temp - 2 ** c + 1


class Solution:

	def getCount(ob, X):
		c = 0
		X1 = X
		while X:
			if X & 1:
				c += 1
			X = X >> 1
		return X1 - 2 ** c + 1


class Solution:

	def getCount(ob, X):
		count = 0
		x1 = X
		while X:
			if X & 1:
				count += 1
			X = X >> 1
		return x1 - pow(2, count) + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		X = input()
		X = int(X)
		ob = Solution()
		print(ob.getCount(X))


import math

class Solution:

	def getCount(ob, X):
		count = 1
		y = X
		while y != 0:
			count += count
			y = y & y - 1
		log_val = math.log(X, 2)
		if int(log_val) == math.ceil(log_val):
			return X - count + 1
		return X - count + 1


class Solution:

	def getCount(ob, X):
		count = 0
		x1 = X
		while X != 0:
			if X & 1 != 0:
				count += 1
			X = X >> 1
		return x1 - pow(2, count) + 1