[C++] UVa 10718 : Bit Mask

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1659 

Online Judge

 

N | M 의 계산 값이 최대가 되는 L과 U 사이의 M을 찾는 문제이다.

답이 여러개 있을 경우에 최소의 M을 반환한다고 한다.

 

# Unsigned integer로 제일 왼쪽 부호 또한 숫자를 나타낸다.

N의 most significant bit 부터 검사해서 해당 비트가 0이면 M에서 범위 안에 속할 시 같은 위치의 bit는 1이다.

해당 비트가 1이면 마찬가지로 범위 안에 속할 시 0으로 매칭시켜주면 된다.

 

0을 추가하고 싶을 때는 L을, 1을 추가하고싶을 때는 U만 확인하여 범위를 확인한 후 매칭한다.

 

N	L	U	M
1100100	0110010	0111100	0
1100100	0110010	0111100	01
1100100	0110010	0111100	011
1100100	0110010	0111100	0111
1100100	0110010	0111100	01110
1100100	0110010	0111100	011101
1100100	0110010	0111100	0111011

 

이런 식으로 최상위 비트부터 진행하여 문제를 해결한다.

시간 복잡도 : O(32)  ==> 비트 연산이기 때문에

 

#include <stdio.h>
using namespace std;
int main() {
    long long N, L, R, ans, l, r;
    while(scanf("%lld %lld %lld", &N, &L, &R) == 3) {
        ans = 0;
        long long i;
        for(i = 31; i >= 0; i--) {
            if(N&(1LL<<i)) {
                r = ans + (1LL<<i);
                if(r <= L)
                ans += 1LL<<i;
            } else {
                l = ans + (1LL<<i);
                if(l <= R)
                ans += 1LL<<i;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

 

 

시험좀 끝내줘...