[1322] X와 K

https://www.acmicpc.net/problem/1322

범위 안보고 그냥 풀었다가 시간초과...ㅎㅎㅎㅎ...

K값이 20억까지인데 그렇다면 K의 시간으로는 해결할 수 없습니다.

X + Y = X | Y

+연산과 OR연산이 같을 조건은

생각해보면 금방 알 수 있습니다.

OR은

0 0 0

0 1 1

1 0 1

1 1 1

입니다.

그러므로 X를 비트로 바꿨을 때 0인 digit??을 1로 바꿔준다면 같아질 수 있습니다.

예를 들어 보겠습니다.

1001(9)라는 수가 있습니다.

이 이진수에 2 혹은 4 혹은 6 등등을 더하면 덧셈과 OR연산이 같아지는 것을 볼 수 있습니다.

2 -> 10

4 -> 100

6 -> 110

아 그렇다면 0인 부분(부분? 자리??)에서 K번째 수를 찾으면 된다는 이야기입니다.

위에서 예를들면 K = 1이면 2가 되고, 2라면 4가 됩니다. 3이라면 6이됩니다.

4라면 16이 되겠지요.

00000000000000000000001001이라는 수는 9인데 이 비트들에서 1을 제외하고 K번쨰 수 인 값을 찾으면 되는 것입니다.

주의할 것은 쉬프트 연산을 할 때 롱롱으로 캐스팅하는 것을 잊으면 안됩니다.(엄청 틀렸음..ㅠㅠ)

코드입니다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main() {
    long long x, k;
    cin >> x >> k;
 
    bool binX[64] = { 0, };
    bool binK[64] = { 0, };
 
    int i = 0;
 
    //2진수로 바꿔서 배열에 저장(2진수 리버스임)
    while (x || k) {
        binX[i] = x % 2;
        binK[i] = k % 2;
        x /= 2;
        k /= 2;
        i++;
    }
 
    int ki = 0;
    int xi = 0;
    long long ret = 0;
 
    while (ki < i) {
        //0인 비트를 해당 자리 수 만큼 쉬프트한다.
        if (binX[xi] == 0) {
            ret |= (1LL << xi) * binK[ki++];
        }
        xi++;
    }
    
    cout << ret;
    
    return 0;
}