Given two integers A and B, the task is to find an integer X such that (X XOR A) is minimum possible and the count of set bit in X is equal to the count of set bits in B.
Example 1:
Input: 
A = 3, B = 5
Output: 3
Explanation:
Binary(A) = Binary(3) = 011
Binary(B) = Binary(5) = 101
The XOR will be minimum when x = 3
i.e. (3 XOR 3) = 0 and the number
of set bits in 3 is equal
to the number of set bits in 5.
Example 2:
Input: 
A = 7, B = 12
Output: 6
Explanation:
(7)_{2}= 111
(12)_{2}= 1100
The XOR will be minimum when x = 6 
i.e. (6 XOR 7) = 1 and the number 
of set bits in 6 is equal to the 
number of set bits in 12.
Your task :
You don't need to read input or print anything. Your task is to complete the function minVal() that takes integer A and B as input and returns the value of X according to the question.
 
Expected Time Complexity : O(log MAX(A,B))
Expected Auxiliary Space : O(1)
 
Constraints :
1 <= A, B <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def minVal(self, a, b):

        #code here

Solutions:
class Solution:

	def minVal(self, a, b):
		num_set_bits_b = bin(b)[2:].count('1')
		a_bin_arr = list(bin(a)[2:])
		ans = ''
		for i in a_bin_arr:
			if i == '1' and num_set_bits_b:
				num_set_bits_b -= 1
				ans += '1'
			else:
				ans += '0'
		i = 1
		ans = list(ans)
		while num_set_bits_b:
			if a_bin_arr[-i] != '1':
				ans[-i] = '1'
				num_set_bits_b -= 1
			i += 1
		ans = ''.join(ans)
		return int(ans, 2)


class Solution:

	def minVal(self, a, b):
		x = ''
		c = bin(b).count('1')
		q = bin(a)[2:]
		if len(q) < len(bin(b)[2:]):
			for i in range(len(bin(b)[2:]) - len(q)):
				q = '0' + q
		for i in range(len(q)):
			if q[i] == '1':
				if c > 0:
					x += '1'
					c -= 1
				else:
					x += '0'
			else:
				x += '0'
		if c > 0:
			x = list(x)
			j = len(x) - 1
			while c > 0 and j > -1:
				if x[j] == '0':
					x[j] = '1'
					c -= 1
					j -= 1
				else:
					j -= 1
			return int(''.join(x), 2)
		return int(x, 2)


class Solution:

	def minVal(self, a, b):

		def countBits(num):
			num_bits = 0
			while num:
				num_bits += num & 1
				num >>= 1
			return num_bits
		b_bits = countBits(b)
		a_bits = countBits(a)
		diff = abs(a_bits - b_bits)
		if a_bits == b_bits:
			return a
		if a_bits > b_bits:
			while diff:
				a &= a - 1
				diff -= 1
		else:
			while diff:
				a |= a + 1
				diff -= 1
		return a


class Solution:

	def minVal(self, a, b):
		na = bin(a)[2:].count('1')
		nb = bin(b)[2:].count('1')
		output = a
		num = 32 * '0'
		num += bin(a)[2:]
		i = 0
		while na > nb:
			if num[-i - 1] == '1':
				output -= 2 ** i
				na -= 1
			i += 1
		while na < nb:
			if num[-i - 1] == '0':
				output += 2 ** i
				na += 1
			i += 1
		return output


class Solution:

	def minVal(self, a, b):
		setBits = bin(b).count('1')
		ans = 0
		for i in range(30, -1, -1):
			mask = 1 << i
			s = a & mask
			if s and setBits > 0:
				ans |= 1 << i
				setBits -= 1
			i = 0
		while setBits > 0:
			mask = 1 << i
			if ans & mask == 0:
				ans |= 1 << i
				setBits -= 1
			i += 1
		return ans


class Solution:

	def minVal(self, a, b):
		abit = bin(a)[2:]
		bbit = bin(b)[2:]
		temp = []
		alen = len(abit)
		(aco, bco) = (0, 0)
		for i in range(alen):
			if abit[i] == '1':
				aco += 1
				temp.append(i)
		for ele in bbit:
			if ele == '1':
				bco += 1
		if bco > alen:
			return int(''.join(('1' for i in range(bco))), 2)
		else:
			ans = [0] * alen
			for ele in temp:
				if bco > 0:
					ans[ele] = 1
				else:
					break
				bco -= 1
			j = alen - 1
			while bco > 0:
				if ans[j] != 1:
					ans[j] = 1
					bco -= 1
				j -= 1
		return int(''.join((str(ele) for ele in ans)), 2)


class Solution:

	def minVal(self, a, b):

		def count(n):
			ans = 0
			while n:
				if n & 1:
					ans += 1
				n >>= 1
			return ans
		A = count(a)
		B = count(b)
		if A == B:
			return a
		d = abs(A - B)
		if A > B:
			while d:
				a = a & a - 1
				d -= 1
		else:
			while d:
				a = a | a + 1
				d -= 1
		return a


class Solution:

	def minVal(self, a, b):
		x = bin(a)[2:]
		y = bin(b)[2:]
		if x.count('1') == y.count('1'):
			return a
		elif x.count('1') > y.count('1'):
			ans = ''
			c = y.count('1')
			for i in x:
				if i == '1' and c > 0:
					ans += '1'
					c -= 1
				else:
					ans += '0'
			return int(ans, 2)
		else:
			x = '0' * (32 - len(x)) + x
			arr = [0] * 32
			for i in range(len(x)):
				arr[i] = x[i]
			c = y.count('1') - x.count('1')
			for i in range(31, -1, -1):
				if arr[i] != '1' and c > 0:
					arr[i] = '1'
					c -= 1
			return int(''.join(arr), 2)


class Solution:

	def minVal(self, a, b):

		def countSetBits(N):
			count = 0
			for i in range(4 * 8):
				if N & 1 << i:
					count += 1
			return count
		x = countSetBits(a)
		y = countSetBits(b)
		diff = abs(x - y)
		if x == y:
			return a
		elif x > y:
			while diff:
				a = a & a - 1
				diff -= 1
		else:
			while diff:
				a = a | a + 1
				diff -= 1
		return a


class Solution:

	def minVal(self, a, b):
		setBits = str(bin(b)).count('1')
		setBits1 = str(bin(a)).count('1')
		ans = 0
		for i in range(32):
			mask = 1 << i
			set = a & mask
			if set == 0 and setBits > setBits1:
				ans |= mask
				setBits -= 1
			elif set != 0 and setBits1 > setBits:
				setBits1 -= 1
			else:
				ans |= set
		return ans


class Solution:

	def minVal(self, a, b):
		one_count = 0
		while b > 0:
			if b % 2 == 1:
				one_count += 1
			b //= 2
		answer = 0
		for i in range(32, -1, -1):
			if one_count <= 0:
				break
			if 1 << i & a == 1 << i:
				one_count -= 1
				answer += pow(2, i)
		i = 0
		while one_count > 0 and i <= 32:
			if 1 << i & a != 1 << i:
				one_count -= 1
				answer += pow(2, i)
			i += 1
		return answer


class Solution:

	def minVal(self, a, b):
		a1 = bin(a)[2:]
		c = a1.count('1')
		b1 = bin(b)[2:]
		c1 = b1.count('1')
		if c1 == c:
			return a
		elif c < c1:
			k = c1 - c
			s = ''
			a11 = a1[::-1]
			for i in a11:
				if i == '0' and k > 0:
					s += '1'
					k -= 1
				elif i == '1':
					s += '1'
				else:
					s += '0'
			while k:
				s += '1'
				k -= 1
			ss = s[::-1]
			return int(ss, 2)
		else:
			k = 0
			s = ''
			for i in a1:
				if k < c1 and i == '1':
					s += '1'
					k += 1
				else:
					s += '0'
			return int(s, 2)
			return 0


class Solution:

	def minVal(self, a, b):

		def bit(n):
			ans = []
			while n > 0:
				ans.append(n % 2)
				n = n // 2
			return ans
		arr1 = bit(a)
		arr2 = bit(b)
		arr1 = arr1[::-1]
		arr2 = arr2[::-1]
		sm1 = sum(arr1)
		sm2 = sum(arr2)
		if sm2 == sm1:
			return a
		elif sm2 < sm1:
			ans = []
			for i in range(len(arr1)):
				if sm2 == 0:
					ans.append(0)
				else:
					ans.append(arr1[i])
					if arr1[i] == 1:
						sm2 = sm2 - 1
		else:
			arr1 = arr1[::-1]
			sm2 = sm2 - sm1
			ans = []
			for i in range(len(arr1)):
				if arr1[i] == 0 and sm2 > 0:
					arr1[i] = 1
					sm2 = sm2 - 1
			while sm2 > 0:
				arr1.append(1)
			ans = arr1[::-1]
		ans1 = 0
		ans = ans[::-1]
		for i in range(len(ans)):
			if ans[i] == 1:
				ans1 = ans1 + 2 ** i
		return ans1


from math import log

def countSetBits(x):
	count = 0
	while x:
		x = x & x - 1
		count = count + 1
	return count

class Solution:

	def minVal(self, a, b):
		c = countSetBits(b)
		bits = int(log(a, 2))
		X = 0
		for i in range(bits, -1, -1):
			if a & 1 << i:
				X |= 1 << i
				c -= 1
			if c == 0:
				break
		if c != 0:
			for i in range(bits + 1):
				if a & 1 << i == 0:
					X |= 1 << i
					c -= 1
				if c == 0:
					break
		return X


class Solution:

	def minVal(self, a, b):
		if bin(a)[2:].count('1') == bin(b)[2:].count('1'):
			return a
		elif bin(a)[2:].count('1') > bin(b)[2:].count('1'):
			while bin(a)[2:].count('1') != bin(b)[2:].count('1'):
				a = a - 1
			return a
		else:
			while bin(a)[2:].count('1') != bin(b)[2:].count('1'):
				a += 1
			return a


class Solution:

	def minVal(self, a, b):
		if a == b:
			return 0
		x = bin(a)
		y = bin(b)
		c1 = x.count('1')
		c2 = y.count('1')
		x = 0
		for i in range(0, 32):
			m = 1 << i
			k = a & m
			if k == 0 and c2 > c1:
				x |= m
				c2 -= 1
			elif k and c1 > c2:
				c1 -= 1
			else:
				x |= k
		return x


class Solution:

	def minVal(self, a, b):
		if a == b:
			return 0
		x = bin(a)[2:]
		y = bin(b)[2:]
		c1 = x.count('1')
		c2 = y.count('1')
		r = 0
		if c1 == c2:
			return a
		k = len(x) - 1
		for i in range(len(x)):
			if c2 == 0:
				break
			if x[i] == '1':
				r += 1 << k
				c2 -= 1
			k -= 1
		if c2 == 0:
			return r
		else:
			k = 0
			for i in range(len(x) - 1, -1, -1):
				if c2 == 0:
					break
				if x[i] == '0':
					r += 1 << k
					c2 -= 1
				k += 1
			n = len(x)
			while c2 != 0:
				r += 1 << n
				c2 -= 1
				n += 1
			return r


class Solution:

	def minVal(self, a, b):

		def ct(dig):
			count = 0
			for i in range(33):
				num = 2 ** i
				if num & dig != 0:
					count += 1
			return count
		bct = ct(b)
		act = ct(a)
		if act == bct:
			return a
		for i in range(33):
			num = 2 ** i
			if act < bct:
				if num & a == 0:
					a = a | num
					act += 1
			elif num & a != 0:
				a -= num
				act -= 1
			if act == bct:
				break
		return a


class Solution:

	def minVal(self, a, b):
		k = bin(b).count('1')
		x = 0
		for i in range(29, -1, -1):
			if k and a & 1 << i:
				x |= 1 << i
				k -= 1
		a = ~a
		for i in range(30):
			if k and a & 1 << i:
				x |= 1 << i
				k -= 1
		return x


class Solution:

	def find(self, a):
		c = 0
		while a > 0:
			if a % 2 != 0:
				c += 1
			a //= 2
		return c

	def minVal(self, a, b):
		v1 = [0] * 32
		v2 = [0] * 32
		bit_a = 0
		bit_b = 0
		ans = 0
		for i in range(0, 32):
			if a & 1 << i > 0:
				bit_a += 1
			if b & 1 << i > 0:
				bit_b += 1
		if bit_a == bit_b:
			return a
		elif bit_a > bit_b:
			while bit_a > bit_b:
				a = a & a - 1
				bit_a -= 1
		else:
			while bit_b > bit_a:
				a = a | a + 1
				bit_b -= 1
		return a


class Solution:

	def tobin(self, a):
		x = []
		while a > 0:
			x.append(a % 2)
			a //= 2
		return x

	def minVal(self, a, b):
		abin = self.tobin(a)
		bbin = self.tobin(b)
		if sum(abin) == sum(bbin):
			return a
		if sum(abin) > sum(bbin):
			ans = 0
			cnt = 0
			i = 0
			while cnt < sum(abin) - sum(bbin):
				if abin[i]:
					ans += pow(2, i)
					cnt += 1
				i += 1
			return a - ans
		ans = 0
		cnt = 0
		i = 0
		while cnt < sum(bbin) - sum(abin):
			if i >= len(abin) or abin[i] == 0:
				ans += pow(2, i)
				cnt += 1
			i += 1
		return ans + a


class Solution:

	def minVal(self, a, b):
		count = 0
		(A, B) = (a, b)
		count0 = 0
		while a > 0:
			count += a & 1
			a >>= 1
		while b > 0:
			if b & 1:
				count0 += 1
			b >>= 1
		if count > count0:
			while count != count0:
				A = A & A - 1
				count -= 1
		elif count < count0:
			while count < count0:
				A = A | A + 1
				count += 1
		return A


class Solution:

	def minVal(self, a, b):

		def count_setbit(n):
			count = 0
			while n:
				n = n & n - 1
				count = count + 1
			return count

		def UnsetRightmostsetBit(n):
			return n & n - 1

		def setRightmostUnsetBit(n):
			if n & n + 1 == 0:
				return n
			return n | n + 1
		setbitB = count_setbit(b)
		setbitA = count_setbit(a)
		X = a
		if setbitA == setbitB:
			return X
		else:
			setbitdiff = setbitB - setbitA
			if setbitdiff > 0:
				while count_setbit(X) != setbitB:
					X = setRightmostUnsetBit(X)
			if setbitdiff < 0:
				setbitdiff = -setbitdiff
				while count_setbit(X) != setbitB:
					X = UnsetRightmostsetBit(X)
		return X


class Solution:

	def countBits(self, n):
		count = 0
		while n:
			count += n & 1
			n >>= 1
		return count

	def minVal(self, a, b):
		(x, B) = (0, self.countBits(b))
		for i in range(31, -1, -1):
			if a & 1 << i and B:
				x |= 1 << i
				B -= 1
		for i in range(32):
			if not x & 1 << i and B:
				x |= 1 << i
				B -= 1
		return x


class Solution:

	def minVal(self, a, b):
		set_bits = 0
		while b:
			set_bits += b & 1
			b = b >> 1
		a_copy = a
		a_bits = []
		while a:
			a_bits.append(a & 1)
			a = a >> 1
		a_bits.reverse()
		x = 0
		n = len(a_bits)
		for i in range(n):
			if set_bits == 0:
				break
			if set_bits == n - i:
				x += 2 ** (n - i - 1)
				set_bits += -1
			elif a_bits[i] == 1:
				x += 2 ** (n - i - 1)
				set_bits += -1
		while set_bits > 0:
			x += 2 ** n
			set_bits += -1
			n += 1
		return x


class Solution:

	def minVal(self, a, b):
		(counta, countb) = (0, 0)
		for i in bin(b):
			if i == '1':
				countb += 1
		for i in bin(a):
			if i == '1':
				counta += 1
		if counta == countb:
			return a
		elif counta > countb:
			diff = counta - countb
			while diff:
				a &= a - 1
				diff -= 1
			return a
		else:
			diff = countb - counta
			while diff:
				a |= a + 1
				diff -= 1
			return a


class Solution:

	def minVal(self, a, b):
		cnt = bin(b)[2:]
		cnt = cnt.count('1')
		a_cnt = bin(a)[2:]
		ans = str()
		for i in a_cnt:
			if i == '1' and cnt > 0:
				ans += '1'
				cnt -= 1
			else:
				ans += '0'
		if cnt > 0:
			ans = [char for char in ans]
			ans = ans[::-1]
			for i in range(len(ans)):
				if cnt == 0:
					break
				if ans[i] == '0':
					cnt -= 1
					ans[i] = '1'
			ans = ans[::-1]
			ans = ''.join(ans)
		ans = int(ans, 2)
		return ans


class Solution:

	def countBits(self, no):
		count = 0
		while no != 0:
			if no & 1 != 0:
				count += 1
			no = no >> 1
		return count

	def minVal(self, a, b):
		setbits = self.countBits(b)
		result = 0
		for i in reversed(range(32)):
			if setbits > 0 and a & 1 << i != 0:
				result = result | 1 << i
				setbits -= 1
		if setbits > 0:
			for i in range(32):
				if setbits > 0 and result & 1 << i == 0:
					result = result | 1 << i
					setbits -= 1
		return result


class Solution:

	def minVal(self, A, B):
		(ans, setB) = (0, 0)
		b = B
		while B > 0:
			if B & 1:
				setB += 1
			B >>= 1
		B = b
		for i in range(31, -1, -1):
			mask = 1 << i
			set = A & mask
			if set and setB > 0:
				setB -= 1
				ans |= mask
		i = 0
		while setB > 0:
			if not ans & 1 << i:
				setB -= 1
				ans |= 1 << i
			i += 1
		return ans


class Solution:

	def minVal(self, a, b):
		setb = bin(b)[2:].count('1')
		seta = bin(a)[2:].count('1')
		ans = 0
		for i in range(0, 32):
			mask = 1 << i
			set = a & mask
			if set == 0 and setb > seta:
				ans |= mask
				setb -= 1
			elif set and seta > setb:
				seta -= 1
			else:
				ans |= set
		return ans


class Solution:

	def minVal(self, A, B):
		(setB, setA) = (0, 0)
		(a, b) = (A, B)
		while B > 0:
			if B & 1:
				setB += 1
			B >>= 1
		while A > 0:
			if A & 1:
				setA += 1
			A >>= 1
		(A, B) = (a, b)
		if setA == setB:
			return A
		ans = 0
		for i in range(0, 32):
			mask = 1 << i
			set = A & mask
			if set == 0 and setB > setA:
				ans |= mask
				setB -= 1
			elif set and setA > setB:
				setA -= 1
			else:
				ans |= set
		return ans


import math

class Solution:

	def minVal(self, a, b):
		ans = 0
		setBits = bin(b).count('1')
		for i in range(31, 0, -1):
			if setBits != 0:
				if a & 1 << i:
					ans |= 1 << i
					setBits = setBits - 1
		for i in range(0, 31):
			if setBits != 0:
				if ans & 1 << i == 0:
					ans |= 1 << i
					setBits = setBits - 1
		return ans


class Solution:

	def minVal(self, a, b):

		def bitLength(a):
			cnt = 0
			i = 1
			while a >= i:
				i *= 2
				cnt += 1
			return cnt

		def bitCount(a):
			cnt = 0
			while a > 0:
				if a % 2:
					cnt += 1
				a = int(a / 2)
			return cnt
		a = int(a)
		b = int(b)
		i = bitLength(a)
		j = bitCount(b)
		x = 0
		while i >= 0 and j > 0:
			if a & 2 ** i:
				x = x | 2 ** i
				j -= 1
			i -= 1
		i = 0
		while j > 0:
			if x & 2 ** i == 0:
				x = x | 2 ** i
				j -= 1
			i += 1
		return x


class Solution:

	def minVal(self, a, b):
		x = bin(a).count('1')
		y = bin(b).count('1')
		if x == y:
			return a
		while x > y:
			a = a & a - 1
			x -= 1
		while y > x:
			a = a | a + 1
			y -= 1
		return a


class Solution:

	def minVal(self, a, b):
		ob = 0
		while b:
			if b % 2 != 0:
				ob += 1
			b >>= 1
		(ba, oa) = (0, 0)
		va = a
		while a:
			if a % 2 != 0:
				oa += 1
			ba += 1
			a >>= 1
		if ba <= ob:
			return 2 ** ob - 1
		n = oa - ob
		ans = 0
		ba -= 1
		c = ba
		while va:
			if n == 0 and va % 2 != 0:
				ans += 2 ** (ba - c)
			elif n < 0:
				if va % 2 == 0:
					n += 1
				ans += 2 ** (ba - c)
			elif n > 0 and va % 2 != 0:
				n -= 1
			c -= 1
			va >>= 1
		return ans


class Solution:

	def minVal(self, a, b):
		b_a = list(bin(a))
		b_b = list(bin(b))
		c_a = b_a.count('1')
		c_b = b_b.count('1')
		if c_b > c_a:
			c = c_a
			c_r = c_b - c_a
		else:
			c = c_b
			c_r = 0
		s = ''
		b_a1 = b_a
		b_a1.remove('0')
		b_a1.remove('b')
		for i in b_a:
			if i == '1' and c > 0:
				s += '1'
				c -= 1
			else:
				s += '0'
		if c_r > 0:
			l = list(s)
			c_l = l.count('0')
			if c_r <= c_l:
				c_1 = c_r
				c_2 = 0
			else:
				c_1 = c_l
				c_2 = c_r - c_l
			for i in reversed(range(len(l))):
				if l[i] == '0' and c_1 > 0:
					l[i] = 1
					c_1 -= 1
			while c_2 > 0:
				l = ['1'] + l
			s = ''
			for i in range(len(l)):
				s += str(l[i])
		return int(s, 2)


class Solution:

	def minVal(self, a, b):

		def countBits(x):
			res = 0
			while x > 0:
				if x % 2:
					res += 1
				x //= 2
			return res

		def convert(x):
			res = ''
			while x > 0:
				res = str(x % 2) + res
				x //= 2
			return res

		def decimal(x):
			res = 0
			base = 1
			i = len(x) - 1
			while i >= 0:
				res += base * int(x[i])
				base *= 2
				i -= 1
			return res
		curr = convert(a)
		count = countBits(b)
		i = 0
		ans = []
		while i < len(curr):
			if curr[i] == '1':
				if count > 0:
					ans += ['1']
					count -= 1
				else:
					ans += ['0']
			else:
				ans += ['0']
			i += 1
		index = len(ans) - 1
		while count > 0 and index >= 0:
			if ans[index] == '0':
				ans[index] = '1'
				count -= 1
			index -= 1
		while count > 0:
			ans += ['1']
			count -= 1
		return decimal(ans)


class Solution:

	def minVal(self, a, b):
		count_b = 0
		while b:
			if b & 1:
				count_b += 1
			b = b // 2
		array = [0] * 32
		for i in range(31, -1, -1):
			if a & 1 << i and count_b > 0:
				array[i] = 1
				count_b -= 1
		j = 0
		while j < 32 and count_b > 0:
			if array[j] == 0:
				array[j] = 1
				count_b -= 1
			j += 1
		ans = 0
		for i in range(32):
			if array[i]:
				ans |= 1 << i
		return ans


class Solution:

	def minVal(self, A, B):
		a = bin(A).count('1')
		b = bin(B).count('1')
		if a == b:
			return A
		while a > b:
			A = A & A - 1
			a -= 1
		while a < b:
			A = A | A + 1
			b -= 1
		return A


class Solution:

	def minVal(self, a, b):
		cnt = 0
		for i in range(32):
			if b & 1 << i:
				cnt += 1
		i = 31
		ans = 0
		while i >= 0 and cnt > 0:
			if a & 1 << i:
				ans = ans | 1 << i
				cnt -= 1
			i -= 1
		i = 0
		while i < 32 and cnt > 0:
			if not ans & 1 << i:
				ans = ans | 1 << i
				cnt -= 1
			i += 1
		return ans


class Solution:

	def minVal(self, a, b):
		set_bits = 0
		for i in range(31):
			if b & 1 << i:
				set_bits += 1
		ans = 0
		for i in range(30, -1, -1):
			if a & 1 << i and set_bits > 0:
				ans |= 1 << i
				set_bits -= 1
		i = 0
		while set_bits > 0:
			while a & 1 << i:
				i += 1
			ans |= 1 << i
			set_bits -= 1
			i += 1
		return ans


class Solution:

	def minVal(self, a: int, b: int) -> int:
		numB = self.count_num_of_set_bits(b)
		numA = self.count_num_of_set_bits(a)
		diff = numA - numB
		while diff > 0:
			diff -= 1
			a &= a - 1
		i = 0
		while diff < 0:
			if a & 1 << i == 0:
				diff += 1
				a |= 1 << i
			i += 1
		return a

	def count_num_of_set_bits(self, n: int) -> int:
		cnt = 0
		while n:
			cnt += 1
			n &= n - 1
		return cnt


class Solution:

	def minVal(self, a, b):
		ca = 0
		cb = 0
		k = a
		while k:
			ca += 1
			k = k & k - 1
		k = b
		while k:
			cb += 1
			k = k & k - 1
		if ca == cb:
			return a
		if ca > cb:
			ans = 0
			for i in range(30, -1, -1):
				if cb and a >> i & 1:
					cb -= 1
					ans += 1 << i
			return ans
		else:
			ans = a
			for i in range(30):
				if a >> i & 1 == 0:
					if cb > ca:
						cb -= 1
						ans += 1 << i
			return ans


import math

class Solution:

	def minVal(self, a, b):
		cb = bin(b)[2:].count('1')
		res = 0
		i = math.ceil(math.log(a, 2))
		while i >= 0 and cb:
			if a & 1 << i:
				res += 2 ** i
				cb -= 1
			i -= 1
		i = 0
		while cb:
			if not res & 1 << i:
				res += 2 ** i
				cb -= 1
			i += 1
		return res


class Solution:

	def minVal(self, a, b):
		c = 0
		z = a
		while z > 0:
			if z & 1:
				c += 1
			z = z >> 1
		y = b
		co = 0
		while y > 0:
			if y & 1:
				co += 1
			y = y >> 1
		if co == c:
			return a
		ans = 0
		if co < c:
			r = co
			for i in range(31, -1, -1):
				if a & 1 << i:
					ans |= 1 << i
					r -= 1
				if r == 0:
					return ans
		ans = a
		if co > c:
			r = co - c
			for i in range(32):
				if not a & 1 << i:
					ans |= 1 << i
					r -= 1
				if r == 0:
					return ans
		return 0