본문 바로가기

프로그래밍/알고리즘

비트마스크 사용법

8개의 비트를 사용하고자 한다.

int bitmask를 비트마스크 변수로 선언한다.

비트는 맨 오른쪽 비트가 0번 비트고 총 8개 비트면 0~7의 범위를 갖는다.

bitmask 변수의 우측 8개 비트만 사용한다는 것이다.

비트 상태가 0인것을 꺼져있다고 하고 1인것을 켜져있다고 한다.


이때 n번 비트가 켜진 상태는

시프트 연산 1<<n 으로 얻을 수 있다.

그리고 이것을 10진수로 나타내면



n

1<<n

dec

0

00000001

1

1

00000010

2

2

00000100

4

3

00001000

8

4

00010000

16

5

00100000

32

6

01000000

64

7

10000000

128

이런식이 된다.


이해를 돕기 위해 배열로 표현한다면

idx[8]={1,2,4,8,16,32,64,128}; 이 된다.

idx[n]==(1<<n) 이다. 연산자 우선순위에 유의한다




※int의 비트 수는 128개이고 그 중 우측 8개 비트만 사용하기 때문에 음수인 경우를 고려하지 않아도 되는것임을 유의.


비트 조회

n번 비트가 켜져있는지 조회하고자 하면

if(bitmask&idx[n]) 식으로 조회 할 수 있다.

n번째 비트가 켜져있으면 0보다 큰 값을 꺼져있으면 0을 얻을 수 있다.



비트 모두 켜기

즉 1111 1111의 상태로 만들고자 한다.

이 경우 10진수인 255를 바로 삽입하는 형태로 쓸 수도 있다.

bitmask=255;    ※int의 비트 수는 128개이고 그 중 우측 8개 비트만 사용하기 때문에 음수인 경우를 고려하지 않아도 되는것임을 유의.

시프트 연산으로 1111 1111를 만드는법은

1 0000 0000를 만들고 여기서 1을 빼주면 된다.

즉 bitmask=(1<<8)-1; 이런 식으로 모든 비트를 켤 수 있다.


비트 모두 끄기

bitmask=0;


n번 비트 켜기

bitmask|=idx[n];


n번 비트 끄기

bitmask&=~idx[n];


n번 비트 토글 (켜졌으면 끄고 꺼졌으면 킨다)

bitmask^=idx[n];



비트 마스크 끼리의 집합


합집합: (bitmask1|bitmask2)

교집합: (bitmask1&bitmask2)

차집합: (bitmask1&~bitmask2)    전자에서 후자를 뺀 집합을 뜻함

둘 중 하나에만 켜져있는 집합: (bitmask1^bitmask2)


켜져있는 비트 수 세기

컴파일러 내장 함수를 이용한다.

Visual C++에선 intrin.h 헤더 파일을 include하고 __popcnt 함수 사용.

gcc에선 바로 __builtin_popcount 함수 사용.



idx[n]을 1<<n으로 표현할때는 연산자 우선 순위에 유의한다

https://ko.wikipedia.org/wiki/C와_C++에서의_연산자#.EC.97.B0.EC.82.B0.EC.9E.90_.EC.9A.B0.EC.84.A0.EC.88.9C.EC.9C.84