Utilities

3.7 Bit Operations

개념

정수를 비트로 표현하기

정수의 이진 표현에서 각 자리는 00 또는 11입니다. 오른쪽 끝을 0번째 비트라고 하며, kk번째 비트의 값은 2k2^k입니다. 여러 항목의 선택 여부를 한 정수의 비트들에 저장할 수 있습니다.

연산기호의미
AND&두 비트가 모두 1이면 1
OR|하나 이상 1이면 1
XOR^두 비트가 다르면 1
NOT~각 비트를 반전
왼쪽 이동<<비트를 왼쪽으로 이동
오른쪽 이동>>비트를 오른쪽으로 이동

예를 들어 5=10125=101_2, 3=01123=011_2이면 AND는 11, OR는 77, XOR는 66입니다.

특정 비트 확인·변경

음이 아닌 정수 x의 k번째 비트에 다음 연산을 적용합니다.

동작C++JavaPython
1인 비트 마스크1 << k1 << k1 << k
비트 값 확인(x >> k) & 1(x >> k) & 1(x >> k) & 1
비트를 1로 설정x | (1 << k)x | (1 << k)x | (1 << k)
비트를 0으로 설정x & ~(1 << k)x & ~(1 << k)x & ~(1 << k)
비트 반전x ^ (1 << k)x ^ (1 << k)x ^ (1 << k)

C++과 Java에서는 비트를 옮기는 칸 수가 자료형의 비트 수보다 작아야 하며, 계산 결과가 자료형의 범위 안에 들어가는지도 확인합니다. Python의 ~x는 -x-1이므로 하위 KK비트만 반전하려면 x ^ ((1 << K) - 1)을 사용합니다. 이 식은 원래 값이 0≤x<2K0\le x<2^K일 때 해당 범위의 비트를 반전합니다.

복잡도

예제의 고정된 정수 범위를 기준으로 합니다.

연산시간복잡도공간복잡도
비트 확인·설정·제거·반전O(1)O(1)추가 O(1)O(1)

예제

문제

정수 XX의 KK번째 비트를 확인하고, 해당 비트를 각각 설정·제거·반전한 결과를 구하여라. 각 연산은 원래 XX에 적용한다.

입력

첫째 줄에 정수 XX와 비트 번호 KK가 공백을 사이에 두고 주어진다. 0≤X≤2550\le X\le255; 0≤K≤70\le K\le7이다. 비트 번호는 오른쪽 끝에서 00부터 센다.

출력

원래 비트 값, 11로 설정한 결과, 00으로 설정한 결과, 반전한 결과를 공백으로 구분하여 출력한다.

예제 입력

5 1

예제 출력

0 7 5 7

예제 코드

C++20

#include <iostream>

using namespace std;

int main() {
    int x, k, mask, bit, on, off, flip;

    cin >> x >> k;
    mask = 1 << k;

    bit = (x >> k) & 1;
    on = x | mask;
    off = x & ~mask;
    flip = x ^ mask;

    cout << bit << ' ' << on << ' ' << off << ' ' << flip << '\n';
}