1554-C, *1800

Problem - 1554C - Codeforces

문제

• $n,\ m(1\leq n,\ m \leq 10^{9})$이 주어질때
  $S=\left \{ n \oplus 0,\ n \oplus 1,\ ...,\ n \oplus m \right \}$에 속하지 않는 음이아닌 최소 정수를 구하라
  
  

 

$O(tlog\ n)$

음이아닌 정수 $k$가 집합 $S$의 원소라면
$\exists x \in \mathbb{Z},\ 0\leq x \leq m \quad \text{s.t. } n\oplus x = k \Leftrightarrow n\oplus k = x$
따라서 $n \oplus k \geq m+1$인 최소 $k$가 구하려고 하는 값이다

i) $n \geq m+1 \rightarrow k = 0$
ii) $n < m+1$

n	1	0	1	0	1
m+1	1	1	0	1	0
k	0	1	0	0	0

예를 들어, 위와같이 $n,\ m+1$의 이진수 표현이 주어졌다고 하자
왼쪽 bit 부터 봤을 때 처음으로 $n$이 $m+1$보다 큰 비트를 기준으로
왼쪽은 $n\oplus m+1$한 비트를 k 값으로($\because n\oplus k \geq m+1$이 성립하게 하기 위함)
오른쪽은 0으로 채우면 된다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n, m;
 
int bit_cnt(int tar)
{
    if(tar == 0) return 1;
    int bit = 0;
    while(tar > 0){
        tar >>= 1;
        bit++;
    }
    return bit;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        if(n >= m+1) cout << 0 << endl;
        else{
            bitset<30> bit_n(n);
            bitset<30> bit_m1(m+1);
            int m_size = bit_cnt(m+1)-1;
 
            bool flag = false;
            for(int i = m_size; i >=0; i--){
                if(flag) bit_n[i] = 0;
                else{
                    if(bit_n[i] == 1 && bit_m1[i] == 0){
                        flag = true;
                        bit_n[i] = 0;
                    }
                    else bit_n[i] = bit_m1[i]^bit_n[i];
                }
            }
 
            cout << bit_n.to_ullong() << endl;
        }
    }
 
    return 0;
}cs