[강의] 1월 20일 수업정리

오늘은 비트마스크에 대한 수업을 들었다.

 

1. 비트 마스크 

정의 :

• 비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용해, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.
• 비트마스크를 통해 집합을 정수로 나타낼 수 있으며, 비트 1이면 켜져있다. 0이면 꺼져있다 라고 말한다.
• 단, 이때 집합에 저장할 수 있는 수의 범위가 정해져 있어야 한다. 따라서 보통 0부터 N - 1까지 N개의 정수로 이루어진 집합을 나태낼 때 사용한다.
• 즉, 2진수 기준으로 1은 구멍, 0은 벽으로 생각했을 때 특정 마스크를 씌웠을 때 원하는 값만 볼수 있게끔 하는 것이 비트 마스크이다. [ 통과 되는 부분 : 1, 통과 되지 않는 부분 : 0 ]
• 1bytes == 8bit == 11111111( 8bit 2진수 ) ==  255 ( 10진수 ) == ff ( 16진수 )
• 16진수를 넣는 방법은 16진수 앞에 "0x ~ "를 넣으면 된다. 

장점 :

• 빠른 수행시간 : 원소의 수가 많지 않을 때 사용되며, bit연산이기 때문에 시간복잡도 O(1)에 구현되는 것이 많다
• 작은 메모리 사용량 : 만약 bit가 10개인 경우, 각 bit당 두 가지의 경우를 가지기 때문에 2^10가지의 경우를 10bit 이진수 하나로 표현 가능하기에 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 데이터를 미리 계산하여 저장해 둘 수 있으므로 캐시 효율이 좋다
• 간결한 코드 : 다양한 집합 연사자들을 반복문 없이 한 줄에 쓸 수 있어 반복문, 조건문을 이용한 코드보다 훨씬 간결하게 코드를 작성할 수 있다.

비트 마스크의 연산 :

1. S에 X가 있는지검사  : S & (1 << x);
2. S에 X를 추가  : S | (1 << x);
3. S에 X를 삭제  : S & ~(1 << x);
4.  S에 X를 토글 : S ^ (1 << x);

#include <iostream>

int main() {

    int nData = 540;

    printf("%08X\n", nData);        // 16진수로 출력 (21C)
    printf("%08X\n", 0xFF);         // 0xFF (8비트 모두 1, 10진수 255)
    printf("%08X\n", nData & 0xFF); // AND 연산 결과 (28)
}

 

2. 문제. 원하는 비트의 값 출력

#include <iostream>

int main()
{
  int nData = 65567587; // 0000 0011 1110 1000 0111 1011 0110 0011  

 // 시프트 한 이유 : 자리수를 맞추기 위해서 -> 값을 밀어야지 정확한 값이 나옴 
 // 1번 : 상위 2바이트
 printf("%d\n", (nData & 0xffff0000) >> 16); // 0000 0011 1110 1000 0000 0000 0000 0000

 // 2번 : 세 번째 1바이트 추출
 printf("%d\n", (nData & 0x0000ff00) >> 8); // 0000 0000 0000 0000 0111 1011 0000 0000

 // 3번 : 마지막 1바이트 추출
 printf("%d\n", nData & 0x000000ff); // 0000 0000 0000 0000 0000 0000 0110 0011
}

 

3. enum을 이용한 비트 마스크 활용법 

삼국지를 예를 들어서 특기가 있다고 가정 했을 때, 한개가 아닌 여러개의 특기를 가지고 있다면 이때 비트연산으로 해결하는 경우도 존재
enum을 사용하여 고유 id를 지정 한 후, 여러개를 채크하는 경우 비트 마스크를 사용함 

#include <iostream>

enum E_WEAPON // 4바이트에 마스킹을 하는것이다.
{
E_SWORD = 0x00000001, // 1
E_SPEAR = 0x00000002, // 2
E_AXE = 0x00000004, // 4
E_DAGGER = 0x00000008, // 8
E_HAMMER = 0x00000010, // 16
E_BOW = 0x00000020, // 32
};

// enum을 사용하여 고유 id를 지정 , 즉 여러개를 채크하는 경우 비트 마스크를 사용함 
int main()
{
int nWeapon{};

// or를 사용하여 넣음 
nWeapon = E_AXE | E_DAGGER;

// 확인을 할때 비트 마스크를 이용
if (nWeapon & E_AXE)
printf("도끼 사용가능\n");

if (nWeapon & E_DAGGER)
printf("단검 사용가능\n");

nWeapon |= E_SPEAR;
if (nWeapon & E_SPEAR)
printf("창 사용가능\n");
}