[LeetCode] 2429. Minimize XOR

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

leetcode - Minimize XOR

문제 유형: 비트마스킹, 그리디

문제 난이도: Medium

 

문제

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.

 

두 양수 num1과 num1가 주어진다. 다음의 조건을 만족하는 양의정수 x를 골라라:

• x는 num2와 같은 이진표현에서의 1의개수를 가진다.
• x XOR 1이 최소값이다.

XOR은 bitwise XOR연산이다.

정수 x를 반환하라.

 

풀이

이진 표현에서의 1의 개수는 __builtin_popcount()로 쉽고 빠르게 구할 수 있다.

integer의 MSB부터 num1과 대응되는 부분부터 채우면서 남은 1의 개수를 줄인다.

그 이후, 여분의 1들을 붙여야 하는데, 최소값을 만들어야 하므로, LSB부터 이번엔 채워준다.

LSB부터 num1과 대응되지 않는 비트부분을 포함시킨다.

 

최종 x를 반환해주면 된다.

 

코드

C++

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int count = __builtin_popcount(num2);

        int res = 0;
        for(int i = 31; i >= 0 && count > 0; --i) {
            if(num1 & (1 << i)) {
                res |= (1 << i);
                count--;
            }
        }

        for(int i = 0; i < 32 && count > 0; ++i) {
            if(!(res & (1 << i))) {
                res |= (1 << i);
                count--;
            }
        }

        return res;
    }
};