[Algorithm] 비트마스크

비트 마스크란?

비트마스크란 컴퓨터의 언어인 이진수를 활용하여 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법입니다.

 

기본적인 비트 연산

기본적인 비트연산들을 표로 정리해보았습니다.

A	B	~A	A&B	A|B	A^B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

not 연산을 할 경우 주의해야할 점이 자료형에 따라서 결과가 달라집니다.

A = 83 = 1010011(2) 에 대하여

• 8비트 자료형의 경우

  ~A = 10101100(2)

• 32비트 자료형인 경우

  ~A = 11111111 11111111 11111111 10101100(2)

 

쉬프트 연산

쉬프트 연산은 다음과 같이 부등호 2개로 표현하며 A<<B , A 를 왼쪽으로 B비트만큼 민다는 의미입니다.

a = 1; // 1(2)
a = a << 2; //100(2)

 

쉬프트 연산의 활용

쉬프트 연산을 활용하여 몇몇 계산을 빠르게 수행할 수 있습니다.

• A * 2^B

  A 를 2의 B 제곱만큼 곱해주는 연산입니다. A 를 왼쪽으로 1비트 이동할 때마다 2가 곱해지는 것과 동일하므로 A << B 으로 구현할 수 있습니다.

• A / 2^B

  A 를 2의 B 제곱만큼 나눠주는 연산입니다. 위와 같은 원리로 A >> B 으로 구현할 수 있습니다.

• N%2 ==1

  N 이 짝수인지 홀수인지 판별하기 위해서 2로 나눈 나머지를 구해 1과 비교하는 연산입니다. 결론부터 이야기하면 N&1 과 같이 구할 수 있습니다.

  N 이 짝수일 경우에는 이진수로 표현했을 때, _ _ _ _ … 0 과 같이 맨 뒤가 0으로 표현이 됩니다. 이를 1과 and 연산 하게 되면 0이 나오고, N이 홀수일 경우에는 이진수로 표현했을 때, _ _ _ _ … 1 과 같이 맨 뒤가 1으로 표현이 됩니다. 이를 1과 and 연산 하게 되면 1이 나오게 됩니다.

 

비트마스크 연산

비트마스크를 활용하기 위해서 몇 가지 핵심적인 연산들이 있습니다. 집합을 S 라 하고, 변수를 i 라고 하겠습니다.

Check

S 에 i 가 포함되어 있는지를 확인할 수 있습니다.

S & (1 << i)
// 포함되어 있을 경우 2^i, 포함되어 있지 않을 경우, 0

Add

S 에 i 를 추가할 수 있습니다.

S = S |(1 << i)

추가하기 위해서 단순히 + , 덧셈으로도 구현할 수 있지만 이 경우, 이미 존재할 경우 올림이 되어 예상하지 않은 값이 결과로 나옵니다.

Remove

S 에 i 를 제거할 수 있습니다.

S = S & ~(1 << i)

Toggle

S 에 i 가 있으면 제거하고 없으면 추가해줍니다.

S = S ^ (1<< i)

All

S 를 모두 1로 가득채워줍니다.

S = (1 << N) -1

Empty

S = 0