[백준 1322] X와 K (C++)

1322번: X와 K

 

X + Y = X | Y

 

위 식의 의미는 다음과 같다.

 

두 수를 2진수로 바꾸었을 때 x와 y가 가진 비트 '1'의 위치가

모두 서로 다르다는 뜻이다.

 

같은 말로 X의 비트가 0인 위치에만 1이 채워져 있는 수가

Y가 될 수 있는 수이다.

 

 

문제를 풀기 위해서는 위 아이디어를 다음과 같이 응용하면 된다.

 

7번째 Y 값을 찾고싶을 때

7은 2진수로 바꾸면 111 이다.

X를 5로 가정하면 X는 ..000101 이라고 생각할 수 있다.

여기서 비트 1의 위치는 보지않고 0인 위치를 숫자가 들어갈 수 있는 위치라고 생각하자.

따라서 7이라는 숫자가 들어갈 수 있는 비트의 위치가 정해졌고 이에 맞춰서 7번째 Y값을 찾으면 아래와 같다.

1

1

0

1

0

= 26

 

#include <iostream>
 
typedef long long ll;
 
using namespace std;
 
ll X, K;
 
void input(){
    cin >> X >> K;
}
 
void solve(){
    ll Y = 0;
    int kidx = 0;
    for(int i = 0; i < 65; i++){
        if((X >> i) & 1LL) continue; 
        if((K >> kidx) & 1LL){
            Y |= (1LL << i);
        }
        kidx++;
    }
    
    cout << Y;
}
 
int main(){
    input();
    solve();
    
    return 0;
}