핵심 아이디어

<aside> 💡

$X\leq 10^9$ 이므로 $X$를 $2$진수로 나타낸다면 최대 $30$비트를 갖게 된다.

이때 비트를 앞 부분 $15$개 뒷 부분 $15$개로 나눠 본다면 $1$을 더하거나 빼는 연산 밖에 없으므로 뒷부분 $15$개를 변경하는 것이 무조건 이득이다.

즉 최대 $2^{15}$를 더하거나 빼는 경우 안에 답이 있다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int x;

void solve()
{
    cin >> x;
    int ans = 1e+9;
    for(int i = 0; i<(1<<17); i++){
        int p = x+i;
        int m = x-i;
        int pt = 31-__builtin_clz(p);
        int mt = 31-__builtin_clz(m);
        
        bool pflag = true;
        bool mflag = true;
        for(int itv = 0; itv<31; itv++){
            if(itv<=pt){
                if( ((p&(1<<(pt-itv))) == 0) != ((p&(1<<(itv))) == 0) ) pflag = false;
            }
            if(m>=0 && itv<=mt){
                if( ((m&(1<<(mt-itv))) == 0) != ((m&(1<<(itv))) == 0) ) mflag = false;
            }
        }

        if(pflag || mflag){
            cout << i << "\\n";
            break;
        }
    }
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();
    return 0;
}