1. 비트 이동 및 조작

비트 이동은 특정 숫자의 이진 표현에서 원하는 위치의 값을 추출하거나 조작하는 데 유용합니다.

• k >> n & 1: k의 이진 표현에서 n번째 비트의 값을 얻습니다.
• n | 1: n을 최소한의 홀수로 변환합니다.
• n | 1 - 1: n을 최소한의 짝수로 변환합니다.

예제 코드는 아래와 같습니다:

#include <iostream>
using namespace std;

int getBit(long long x, int pos) {
    return (x >> pos) & 1;
}

int main() {
    long long x = 10; // 1010
    int n = 1;
    cout << "Position " << n << " bit is: " << getBit(x, n) << endl;
    return 0;
}

2. 배수와 이진 자릿수 조작

정수 x가 주어졌을 때, 다음 조건을 만족하는 y를 찾습니다:

• y는 x의 배수여야 합니다.
• x와 y는 같지 않아야 합니다.
• y의 이진 표현에서 x의 이진 표현이 부분 문자열로 포함되어야 합니다.
• x와 y의 이진 표현에서 '1'의 개수는 동일하지 않아야 합니다.

해결 방법으로는 x를 왼쪽으로 이동시키고 다시 x를 추가하는 방식입니다:

#include <iostream>
using namespace std;

int countBits(long long x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

int main() {
    long long x;
    cin >> x;
    int len = 0;
    long long temp = x;
    while (temp) {
        len++;
        temp >>= 1;
    }
    long long y = (x << len) + x;
    if (countBits(x) != countBits(y)) {
        cout << y << endl;
    }
    return 0;
}

3. 이진/삼진 변환 문제

문자열 a가 주어졌을 때, 그 값이 이진법과 삼진법에서 단 하나의 비트만 다를 경우를 찾습니다.

해결 방법은 각각의 자리에 대해 가능한 모든 값을 시도하고 교집합을 찾는 것입니다:

#include <iostream>
#include <unordered_set>
using namespace std;

int convert(string s, int base) {
    int res = 0;
    for(char c : s) {
        res = res * base + (c - '0');
    }
    return res;
}

int main() {
    string bin, trin;
    cin >> bin >> trin;

    unordered_set<int> s;
    for(int i = 0; i < bin.size(); ++i) {
        char original = bin[i];
        bin[i] = (bin[i] == '0') ? '1' : '0';
        s.insert(convert(bin, 2));
        bin[i] = original;
    }

    for(int i = 0; i < trin.size(); ++i) {
        char original = trin[i];
        for(int j = 0; j < 3; ++j) {
            if(trin[i] != '0' + j) {
                trin[i] = '0' + j;
                int val = convert(trin, 3);
                if(s.find(val) != s.end()) {
                    cout << val << endl;
                    return 0;
                }
            }
        }
        trin[i] = original;
    }
    return 0;
}

4. 상태 압축과 비트 연산

n개의 전구가 있고, 각 전구는 켜져 있거나 꺼져 있습니다. 시간이 지날 때마다 전구의 상태가 변경됩니다.

해결 방법은 상태를 이진 수로 표현하고, 상태 간의 변화를 비트 연산으로 계산합니다:

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1 << 16;
int p[MAXN];

int updateState(int state, int n) {
    int newState = 0;
    for(int i = 0; i < n; ++i) {
        int prev = ((i - 1 + n) % n);
        int cur = (state >> i) & 1;
        int left = (state >> prev) & 1;
        newState |= ((cur ^ left) << i);
    }
    return newState;
}

int main() {
    int n;
    long long m;
    cin >> n >> m;

    int initialState = 0;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        initialState |= (x << i);
    }

    memset(p, -1, sizeof(p));
    p[initialState] = 0;

    for(int step = 1;; ++step) {
        initialState = updateState(initialState, n);
        if(step == m) {
            for(int i = 0; i < n; ++i) {
                cout << ((initialState >> i) & 1);
            }
            cout << endl;
            break;
        }
        if(p[initialState] != -1) {
            int cycleLength = step - p[initialState];
            int remaining = (m - step) % cycleLength;
            while(remaining--) {
                initialState = updateState(initialState, n);
            }
            for(int i = 0; i < n; ++i) {
                cout << ((initialState >> i) & 1);
            }
            cout << endl;
            break;
        }
        p[initialState] = step;
    }
    return 0;
}