1322 X와 K

X+Y = X | Y인 Y중에 K번째인 것을 찾아야한다.

X + Y = X | Y를 만족하는 Y를 구하는 방법은 간단하다.

이진수로 표현했을 때 X가 1인 부분이 겹치지 않는 수가 Y다.

X가 5일 때 2진수로 표현하면 101인데 1~7번째 수를 늘어놓으면

00101

00010 : 1

01000 : 2

01010 : 3

10000 : 4

10010 : 5

11000 : 6

11010 : 7

이 된다. 이걸 구하기 위해 X가 1인 줄을 제외하고 보면

001

010

011

100

101

110

111

이 되므로 K를 2진수로 만든 후 X가 1인 부분은 건너뛰면서 입력해 주면 된다.

X와 K가 둘다 2e9까지이므로 답은 int범위를 벗어나는 것을 유념하자.

<코드>

#include <stdio.h>
 
bool c[65];
int n, k;
long long ans, p = 1;
 
int main() {
    scanf("%d%d", &n, &k);
    for (int ind = 0; n > 0; n /= 2) 
        c[ind++] = n % 2;
    for (int i = 0; i < 65 && k; i++, p *= 2) if (!c[i]) {
        if (k % 2) ans += p;
        k /= 2;
    }
    printf("%lld\n", ans);
    return 0;
}