2429. Minimize XOR

https://leetcode.com/problems/minimize-xor/description/

 

이번 문제는 비트연산을 하는 문제이다.

사실 일상에서나 어떤 문제를 해결할 때도 비트연산을 활용하는 경우는 거의 없기 때문에 존재 조차 까먹고있었다.

문제는 다음과 같다

두 개의 양의 정수 num1과 num2가 주어졌을 때, 다음과 같은 양의 정수 x를 구하세요.

x는 num2와 같은 수의 설정된 비트를 가지고 있고 값 x XOR num1이 최소가 됩니다.
XOR은 비트 단위 XOR 연산입니다. 정수 x를 반환합니다.
테스트 케이스는 x가 고유하게 결정되도록 생성됩니다.
정수의 설정된 비트 수는 이진 표현에서 1의 수입니다.

예제 1:
입력: num1 = 3, num2 = 5
출력: 3
설명: num1과 num2의 이진 표현은 각각 0011과 0101입니다.
        정수 3은 num2와 같은 수의 설정된 비트를 가지고 있고 값 3 XOR 3 = 0이 최소가 됩니다.

예 2:
입력: num1 = 1, num2 = 12
출력: 3
설명: num1과 num2의 이진 표현은 각각 0001과 1100입니다.
        정수 3은 num2와 동일한 수의 세트 비트를 가지고 있으며 값 3 XOR 1 = 2는 최소입니다.

제약 조건: 1 <= num1, num2 <= 10⁹

 

문제에서 2개의 정수값이 주어지고 여기서 num1,num2의 값을 각각 2진수로 바꿨을때,

 

1. 동일한 비트값을 가져야 한다 (1의 개수가 같아야한다)

2. 가장 최소값이어야 한다

 

이 두가지 조건을 만족하는 정수를 반환하면 되는 문제이다.

 

처음 이 문제를 봤을때 떠오른 생각은

 

1. 먼저 10진수를 2진수로 변환한다.

2. 두 수의 SetBit가 동일하면 답은 num1이고,

    1의 개수가 두 수 모두 동일하면 num1이 최소값이 된다.

...

 

이런식으로 생각을 이어나가다가 뭔가 아니라고 생각해서 이번엔 토론창을 한번 봤다.

거기서 아주 중요한 힌트가 있었는데,

Unset rightmost bit
x&(x−1)
Set rightmost unset bit
x∣(x+1)

 

처음 봤을때 이게 무슨소리인가 했는데 &과 |을 단일로 쓰면 비트연산이 된다는 사실을 완전히 잊고 있었다.

 

이 문제를 풀때 기본적으로 알고있어야 하는 사실은 다음과 같다

A	B	AND ( & )	OR ( | )	XOR ( ^ )	NOT ( ~ )
0	0	0	0	0	0
0	1	0	1	1
1	0	0	1	1	1
1	1	1	1	0

 

- AND : 비트가 모두 같을때 True

- OR   : 하나라도 같으면 True

- XOR : 비트가 같지 않으면 True

- NOT : 해당 비트의 반대값

 

다시 원점으로 돌아와서 저 공식을 다시 보면

 

• x&(x−1) : 가장 오른쪽 비트를 0으로 변경

예제)
원래값         :  5 & ( 5-1)
비트로 치환 :  5(101) & 4(100)

AND 연산
  101
&100
---------
 100

• x∣(x+1): 가장 오른쪽 비트를 1로 변경

예제)
원래값         :  12 & ( 12+1)
비트로 치환 :  12(1100) & 13(1101)

OR 연산
  1100
| 1101
---------
  1101

 

이렇게 볼수있다.

이 공식을 활용하면 우리가 원하는 만큼 비트값을 조절할 수 있게 된다.

아래는 정답 코드다.

class Solution {
    public int minimizeXor(int num1, int num2) {
        while(Integer.bitCount(num1) != Integer.bitCount(num2)) {
            if(Integer.bitCount(num1) > Integer.bitCount(num2)) {
                num1 = num1&(num1-1);
            } else {
                num1 = num1|(num1+1);
            }
        }
        return num1;
    }
}

 

Java에서는 Integer.bitCount(n) 메서드를 제공하여 이를 활용해 비트 값을 확인할 수 있다.

이를 활용해서 num1과 num2가 같아질 때 까지 반복하며 비트수를 조절하고 반환하는 코드이다.

 

런타임은 0 ms, 메모리는 40,33Mb가 나왔다.

 

이번 문제를 통해서 비트 계산에 대한 기초중에 기초를 배운것 같다.