비트연산(Bitwise operation), 비트마스크(Bitmask)

아래와 같이 정리하려고 한다. 

1. 비트
2. 비트연산자
3. 비트마스크
4. 할 수 있는 것 정리

먼저 연산을 보기위해서 코드를 첨부한다.

#include<cstdio>
#include<string>
#define pb(a) print_bit(a)
using namespace std;
 
void print_bit(int input) {
    string ret;
    for (int i = 0; i < 32; i++) {
        ret.push_back((input & 1) + '0');
        input = input >> 1;        
    }
    reverse(ret.begin(), ret.end());
    for (auto p : ret) {
        printf("%c", p);
    }
    puts("");
}
 
int main() {
    signed int s_int = 0;
    unsigned int u_int = 0;
    string bar = string(80, '-');
    for (int i = 0; i < 32; i++) {
        int check = (1 << i);
        if(i!=31) s_int |= check;
        u_int |= check;
    }
 
    printf("signed int = %i\n", s_int);
    pb(s_int);
    printf("unsigned int = %ui\n", u_int);
    pb(u_int);
    pb(~u_int);
    pb(u_int | s_int);
    pb(u_int & s_int);
    pb(u_int ^ s_int);
    pb(u_int << 4);
    pb(u_int >> 4);
    printf("%s\n", bar.c_str());
 
    puts("30-set");
    pb((1 << 30) - 1);
    pb(0);
    puts("32-set");
    int full = (1 << 32) - 1;
    pb(full);    
    printf("%s\n", bar.c_str());
 
    puts("set");
    int a_set = 24125;
    int b_set = 982132176;
    pb(a_set);
    pb(b_set);
    puts("sum of sets");
    pb(a_set | b_set);
    puts("intersection");
    pb(a_set & b_set);
    puts("difference of sets : a-b");
    pb(a_set & (full^b_set));
    
    puts("difference of sets : b-a");
    pb(b_set & (full^a_set));
 
    printf("%s\n", bar.c_str());
    puts("p & -p");
    pb(8 & -8);
    printf("%s\n", bar.c_str());
    return 0;
}

out :

signed int = 2147483647

01111111111111111111111111111111

unsigned int = 4294967295i

11111111111111111111111111111111

00000000000000000000000000000000

11111111111111111111111111111111

01111111111111111111111111111111

10000000000000000000000000000000

11111111111111111111111111110000

00001111111111111111111111111111

--------------------------------------------------------------------------------

30-set

00111111111111111111111111111111

00000000000000000000000000000000

32-set

11111111111111111111111111111111

--------------------------------------------------------------------------------

set

00000000000000000101111000111101

00111010100010100010010111010000

sum of sets

00111010100010100111111111111101

intersection

00000000000000000000010000010000

difference of sets : a-b

00000000000000000101101000101101

difference of sets : b-a

00111010100010100010000111000000

--------------------------------------------------------------------------------

p & -p

00000000000000000000000000001000

--------------------------------------------------------------------------------

1) 비트

비트란 이진수를 의미하고, 0과 1로 표현 할 수 있다. 

1비트는 2가지 정보를 나타낼 수 있다.

예로, 

int형을 보게되면 4바이트로 이는 32비트를 표현할 수 있다. (1바이트 = 8비트)

만약 32비트가 모두 1인 경우라면 아래와 같이 표현이 되는 것이다.

1111 1111 1111 1111 1111 1111 1111 1111

2) 비트연산자

op A

~ NOT : 값을 반전시킴 (비트값반전)

not 연산은 자료형에 따라 결과가 다르다.

A op B

op

| OR : 피연산자들의 비트값들이 둘 다 0 인 경우 0, 나머지는 1

& AND : 피연산자들의 비트값들이 둘 다 1 인 경우 1 , 나머지는 0

^ XOR : 피연산자들의 비트값들이 서로 다른 경우만 1, 나머지는 0

(a) << (b) : L-shift 

우측에 추가되는 비트는 0 이 들어온다.

ex)

1 << 0 : (1)     2^0 

1 << 1 : (10)   2^1 

1 << 2 : (100) 2^2 

3 << 1 : (110) 

7 << 2 : (11100)

(a) >> (b) : R-shift

왼측에 추가되는 비트는 0 이 들어온다.

ex)

2 >> 0 : (10) 2

2 >> 1 : (1)  1

3) 비트마스크

각 비트에 정보를 저장하고 싶다. 만약 열쇠가 종류 별로 있을 때 

열쇠의 종류가 많지 않은 경우라면 

첫번째 열쇠는 비트의 0번째 위치 1 << 0 에 저장하고, 

두번째 열쇠는 비트의 1번째 위치 1 << 1 에 저장하고...

....

위와 같은 경우로 열쇠를 OR(|) 으로 가지게 할 수 있다. 

그리고 현재 열쇠를 가지고 있는 지 유무는 AND(&)로 체크할 수 있다.

https://www.acmicpc.net/problem/1194

위 링크 문제는 열쇠를 비트마스크로 풀이 할 수 있다.

4) 할 수 있는 것 정리

또, 합집합 교집합 차집합 을 표현 할 수 있다.

전체 집합은 (1 << N) - 1 , 공집합은 0 

최하위비트를 구하는 경우도 있다. 

팬윅트리에서 최하위비트를 구할 때 사용된다.

p & -p 

로 구할 수 있다.