[Codeforces] Cirno's Perfect Bitmasks Classroom

https://codeforces.com/contest/1688/problem/A

https://codeforces.com/contest/1688/problem/A

단순하게 패턴을 파악하면 되는 문제이다.

주어진 $x$와 AND 연산, XOR 연산에서 모두 0을 초과하는 값을 내는 최소의 양의 정수를 찾아야 한다.

 

그러면 AND 연산과 XOR 연산에서 각각 0을 초과할 수 있되 가장 작은 수를 만들 수 있는 패턴을 파악해보자.

 

AND 연산

$x$의 이진수를 표현했을 때, 1로 표시되는 자릿수 중 가장 작은 자릿수에서 1

 

XOR 연산

$x$의 이진수를 표현했을 때, 0으로 표시되는 자릿수 중 가장 작은 자릿수에서 1

$x$의 이진수를 표현했을 때, 1로 표시되는 자릿수 중에서 0

 

이 패턴들을 바탕으로 생각했을 때, 만약 $x$가 2의 거듭제곱수라면 하나의 자릿수만 1로 만들어서(즉 제곱수로 만들어서) 문제의 두 가지 조건을 모두 충족할 수 없었다.

왜냐하면 $x$가 2의 거듭제곱수라면 이진수에서 1은 한 번만 등장하기 때문이다. 만약 2의 거듭제곱수라면, $x$의 자릿수의 값이 0인 최소의 자릿수를 찾아서 AND 연산과 XOR 연산 조건을 충족하도록 두번의 비트 연산을 해야 한다.

 

2의 제곱수가 아니라면 AND 연산 조건을 충족하는 비트 연산을 신경쓰면서 $x$의 이진수를 표현했을 때, 1로 표시되는 자릿수 중 가장 작은 자릿수만 1로 표시하면 된다.

왜냐하면 자동으로 1의 값을 가지는 다른 자릿수에서 $y$는 0의 값을 가져서 XOR 연산 조건은 자동으로 충족되기 때문이다.

 

여기서 2의 거듭제곱수를 판별하는 함수를 기억해두면 좋을 것 같다.

// 2의 거듭제곱수 판별
bool twiceNum(int x) {
    return (x & (x - 1)) == 0;
}

2의 거듭제곱수의 경우에는 1이 하나만 있다. 그 수에서 1을 빼면 아래 자릿수는 모두 1로 채워진다.

그 두 수를 AND 연산을 수행하면 0의 값을 가진다.

 

2의 거듭제곱수가 아니라면 1이 2번 이상 등장하기 때문에 맨 최하위의 1의 자릿수 위는 동일하다.

AND 연산의 결과가 0이 아니게 된다.

#include <iostream>

using namespace std;

int lowest_cipher(int x) {
    int c = 0;
    while(true) {
        if(x & (1 << c)) {
            break;
        }
        c += 1;
    }
    return c;
}

int lowest_cipher2(int x) {
    int c = 0;
    while(true) {
        if(x ^ (1 << c)){
            break;
        }
        c += 1;
    }
    return c;
}

// 2의 제곱수 판별
bool twiceNum(int x) {
    return (x & (x - 1)) == 0;
}

int main() {
    int T;
    cin >> T;
    
    while(T--) {
        int x, answer = 0;
        cin >> x;
        int c = lowest_cipher(x);
        answer |= (1 << c);
        // 제곱 수 = 1의 개수가 하나
        if(twiceNum(x)) {
            int c2 = lowest_cipher2(x);
            answer |= (1 << c2);
        }
        cout << answer << '\n';
    }
}