티스토리 뷰

알고리즘 관련/BOJ

BOJ)1322 X와K

JASON 자손9319 2017. 6. 5. 12:25

문제: icpc.me/1322


X가 정해져 있을 때 X+Y = X | Y 를 만족하는 Y는 


2진수에서의 연산을 생각한다면 X가 0인 비트에만 1이 채워져있는 수일 것이다.


고로 K번째로 큰 Y를 찾는다면 K를 이진수로 표현하였을 때 1이 채워진 순서를 X에서 0인 부분에 순서대로 채운 수가 된다.


이는 투 포인터로 구해줄 수 있다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll x, y, k;
int main() {
    scanf("%lld%lld"&x, &k);
    for (int i = 0, j = 0; j < 32; i++, j++) {
        while ((1LL << i) & x)
            i++;
        if ((1LL << j) & k)
            y += (1LL << i);
    }
    printf("%lld\n", y);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14590 KUBC League (Small)  (0) 2017.06.06
BOJ)13538 XOR 쿼리  (0) 2017.06.05
BOJ)1322 X와K  (0) 2017.06.05
BOJ)1837 암호제작  (2) 2017.06.05
BOJ)14577 일기예보  (0) 2017.06.04
BOJ)6850 Cows  (0) 2017.06.02
댓글
댓글쓰기 폼