Description

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.
Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

---

Example

Example 1:

Input: num1 = 3, num2 = 5
Output: 3
Explanation:
The binary representations of num1 and num2 are 0011 and 0101, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.
Example 2:

Input: num1 = 1, num2 = 12
Output: 3
Explanation:
The binary representations of num1 and num2 are 0001 and 1100, respectively.
The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.

---

Constraints

1 <= num1, num2 <= 109

---

내 풀이

기본적으로 문제를 생각하는 방식이 너무 인간적이라 풀이법에 전혀 접근하지 못 했다고 볼 수 있다.

num1, num2 를 이진수로 변환했을 때, num2 의 1의 개수와 동일한 개수를 가진 x 가 있다.
이 x 와 num1 이 이진 XOR 연산을 했을 때, 최솟값이 나오는 x 를 구하는 알고리즘을 구하여라

1. num2 를 이진수로 변환했을 때, 1의 개수를 구하는 로직
2. num1 과 XOR 연산을 했을 때, 정해진 1의 개수로 가장 작은 값을 도출하는 알고리즘
   *. 1의 개수 조건에 따른 상황 설정
   ㄱ. num2 의 1의 개수가 num1 보다 적은 경우: num1 의 왼쪽 1부터 0으로 치환한 수
   ㄴ. num2 의 1의 개수가 num1 과 같은 경우: x = min(num1, num2)
   ㄷ. num2 의 1의 개수가 num1 보다 큰 경우: num2 가 더 많은 1의 개수만큼 num1 의 오른쪽 0부터 치환한 수

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        def bin_rev(num):
            return list(bin(num).lstrip('0b'))[::-1]
        
        num1_bin = list(bin(num1).lstrip('0b')) # string of binary num1
        num2_bin = list(bin(num2).lstrip('0b')) # string of binary num2
        
        digit = max(len(num1_bin), len(num2_bin))
        print(f'digit: {digit}')
        
        num1_counter = Counter(num1_bin)
        num2_counter = Counter(num2_bin)
        
        num1_one_cnt = num1_counter['1']
        num2_one_cnt = num2_counter['1']
        
        ones = abs(num1_one_cnt-num2_one_cnt)
        
        rev_num1 = list('0'*(digit-1)) + bin_rev(num1)
        x = rev_num1[:]
        print(f'original x: {x}')
        
        if num1_one_cnt > num2_one_cnt:
            for i in range(digit):
                if ones == 0: break
                if rev_num1[i] == '1':
                    x[i] = '0'
                    ones -= 1
            return int(''.join(x), 2)
            
        elif num1_one_cnt == num2_one_cnt:
            return min(num1, num2)
        else:
            for i in range(digit-1, -1, -1):
                if ones == 0: break
                print(f'rev_num1[{i}]: {rev_num1[i]}')
                if rev_num1[i] == '0':
                    x[i] = '1'
                    print(f'x: {x}')
                    ones -= 1
            return int(''.join(x), 2)

s = Solution()
print(s.minimizeXor(17, 15))

나름대로 문제를 해결할 수 있는 로직과 경우의 수를 나누어 봤지만, 문제의 전제 조건인 1 <= num1, num2 <= 109 조차 활용하지 못 했다.
위 코드는 문제를 해결하지 못 한다. 1의 개수를 구하기 위해 collections.Counter 를 활용해 보고자 했지만, 과한 스펙이었다.
이진수를 문자열과 리스트로 만지작 거리며 연산을 시도했지만, 이진수의 자릿수 길이를 특정하지 않아 문제가 발생했다.

---

가능한 풀이

class Solution(object):
	def minimizeXor(self, num1, num2):
		a, b = bin(num1).count('1'), bin(num2).count('1')
		res = num1
  		for i in range(32):
			if a > b and (1 << i) & num1 > 0:
				res ^= 1 << i
                a -= 1
            if a < b and (1 << i) & num1 == 0:
                res ^= 1 << i
                a += 1
        return res

전체 로직 요약

1. num1의 1비트 개수(a)와 num2의 1비트 개수(b)를 구한다.
2. 결과를 담을 res를 num1으로 초기화한다.
3. 0번째 비트부터 31번째 비트까지 순회하며,
   • 만약 현재 res(초기에 num1과 동일)에 1비트가 b보다 많이 잡혀 있다면(a > b), 1인 비트를 0으로 만들면서(토글) 1비트 개수를 줄인다(a -= 1).
   • 만약 1비트가 부족하면(a < b), 0인 비트를 1로 만들면서(토글) 1비트 개수를 늘린다(a += 1).
4. 이렇게 32비트 각각을 확인·조정한 뒤 최종적으로 res를 반환한다.

상세 단계

1. 1비트 개수 세기

a, b = bin(num1).count('1'), bin(num2).count('1')

• bin(num1)은 num1을 이진수 형태의 문자열로 만들어 준다. 예: num1 = 13이면 bin(num1)은 '0b1101'.
• .count('1')은 이 문자열에서 '1'이 몇 개 있는지 세어 준다. 예: '0b1101'에는 '1'이 3개이므로 3.
• 따라서 a에는 num1의 1비트 개수가, b에는 num2의 1비트 개수가 저장된다.

2. 결과값 초기화

res = num1

• 결과값(res)을 num1으로 초기화한다.
• 이후에는 res의 비트를 하나씩 수정해 나가며 최종 해답을 만든다.

3. 비트 조정(루프)

for i in range(32):
    if a > b and (1 << i) & num1 > 0:
        res ^= 1 << i
        a -= 1
    if a < b and (1 << i) & num1 == 0:
        res ^= 1 << i
        a += 1

• i를 0부터 31까지 순회하면서, 32비트 정수의 각 비트 위치를 하나씩 확인한다.
• (1 << i)는 1을 왼쪽으로 i번 시프트한 값으로, 2^i를 의미한다.
• (1 << i) & num1가 0보다 크다는 것은 num1의 i번째 비트가 1이라는 뜻이다. 반대로 0이면 i번째 비트가 0이라는 뜻이다.

3.1. if a > b and (1 << i) & num1 > 0:

• 현재 res(초기에 num1)에서 1비트가 너무 많다면(a > b), i번째 비트가 1인 경우 그 비트를 끈다(토글).
  • res ^= (1 << i)는 i번째 비트를 반전(XOR)시키는 연산이다. i번째 비트가 1이었다면 0이 된다.
  • 1비트를 하나 없앴으므로 a -= 1.

3.2. if a < b and (1 << i) & num1 == 0:

• 현재 res에서 1비트가 부족하다면(a < b), i번째 비트가 0인 경우 그 비트를 켠다(토글).
  • res ^= (1 << i)는 i번째 비트를 반전시킨다. i번째 비트가 0이었다면 1이 된다.
  • 1비트를 하나 늘렸으므로 a += 1.

4. 최종 res 반환

• 위 과정을 마치고 나면, res는 num2와 동일한 개수의 1비트를 갖고, 동시에 num1 XOR res가 최소화되도록 조정이 끝난 상태이다.
• 함수는 res를 반환한다.

---

왜 이렇게 하면 num1 XOR res가 최소가 될까?

• XOR 연산은 서로 다른 비트가 맞부딪힐 때 1로 계산된다. 즉, 같은 위치에서 같은 비트면 0, 다른 비트면 1이 된다.
• 목표가 “num2와 같은 개수의 1비트를 가진다”는 제약 조건 아래, num1과 최대한 많은 비트를 동일하게 유지해야 XOR 값이 작아진다.
• 따라서 불필요한 1비트를 끄고, 부족한 1비트는 켜서 num2와 같은 1비트 개수를 맞추되, 가능한 한 num1의 기존 비트값을 많이 보존하게 된다.
• 루프를 0번째 비트부터 확인하기 때문에, 낮은 비트부터 조정하면서 결과적으로 num1 XOR res를 최소화할 수 있다.

이 로직을 정리하면,
1. num1과 num2의 1비트 개수를 비교한다.
2. 1비트가 너무 많으면( a > b ) 낮은 자리 비트부터 1을 0으로 바꾸고, 1비트가 부족하면( a < b ) 낮은 자리 비트부터 0을 1로 바꿔서 개수를 맞춘다.
3. 이렇게 하면 최소한의 비트만 수정하여 num1과의 XOR값을 최소화하고, 동시에 num2와 동일한 1비트 개수를 만족하는 값을 얻게 된다.

즉, 이 코드는 한 비트씩 살펴보면서, 불필요한 1비트를 제거하고 부족한 1비트를 채움으로써 num2의 1비트 개수를 맞추는 동시에 num1 XOR res값이 최소가 되도록 계산하는 과정이다.

내가 생각한 해결 방법과 같은 방식을 이용하지만, 문자열 메소드의 활용과 비트 연산의 미숙함 때문에 코드를 완성할 수 없었다.