[알고리즘] 비트마스크란

컴퓨터의 언어는 기계어라고 불리는 이진수이다. 

이진수는 독일의 철학자 라이프니츠가 발명한 수 체계이다. 

컴퓨터가 이진수를 사용하는 이유는 무엇일까?

그 이유는 전기신호로 작동하는 컴퓨터에게 전기가 통할 때 (1), 전기가 통하지 않을 때(0) 2가지 신호를 나타낼 수 있는 이진수가 가장 효율적이기 때문이다.

예를 들어 단순히 생각해보면 이진수는 전선이 하나만 있으면 표현이 가능하다. 

하지만 십진수의 경우 0부터 9까지 숫자를 표현 해야하기 때문에 10개의 전선이 필요하다.

십진수 체계에서 하나의 전기신호만 보내면 되는 상황이면 나머지 9개의 전선은 낭비인 것이다.

그래서 필요에 따라 이진수를 여러번 사용하는게 가장 효율적이다.

비트(bit) 란?

 비트는 데이터를 나타내는 최소 단위로 이진수의 한자리인 0 또는 1 의 값을 가진다. 

비트라는 이름은 바이너리 디지트(binary digit)의 약자를 의미한다.

부호 없는 N비트 정수형 변수는 N자리의 이진수로 나타낼 수 있다.

이때 비트가 표현하는 값은  부터  까지이다. 

여기서 에 해당하는 비트값을 최상위 비트(Most Significant Bit) 라 하고,   에 해당하는 비트값을 최하위 비트(Least Significant Bit) 라고 한다.

예를 들어 부호없는 4비트 정수형은 네 자리 이진수로 표시할 수 있는 모든 정수를 나타낼 수 있다. 

( 아래 그림과 같이 4칸의 공간에 이진수 0 또는 1을 넣은 모든 경우의 수를 의미한다. )

이때 비트가 표현하는 값은  부터 이다.

그리고 여기서 에 해당 하는 비트값(1) 이 최상위 비트이고  에 해당하는 비트값(1)이 최하위 비트이다.

비트마스크란?

 비트마스크에 대해 알기위해 기본적으로 컴퓨터의 언어인 이진수와 비트에 대해 알아보았다.

비트마스크란 컴퓨터의 언어인 이진수를 사용하면 연산이 빠른점을 이용해 어떠한 정수를 이진수 형태로 표현하여 자료구조로써 사용하는 기법이다.

 

비트마스크의 장점

 1. 다른 자료 구조에 비해 수행 시간이 더 빠르다. 

 2. 비크 연산자를 사용하여 코드가 더 간결해 진다. 

 3. 비트마스크를 사용하여 더 작은 메모리를 사용할 수 있다.

비트 연산

 비트 연산은 이진수에 대해 비트 단위로 적용되는 연산을 의미한다.

비트 연산자 ( java 기준 )

 1. AND 연산자( & ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트가 모두 1이면 결과도 1 이고 나머지는 0 을 반환

예) 101 & 100 = 100

 

 2. OR 연산자( | ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트 중 하나라도 1이면 결과가 1 이고 나머지는 0 을 반환

예) 101 | 100 = 101

 3. XOR 연산자 ( ^ ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트가 서로 다르면 1 , 같으면 0을 반환

예) 101^100 = 010

 4. NOT 연산자 ( ~ ) : 정수 하나의 각 비트를  1 이면 0 , 0 이면 1 로 바꾸는 연산

예) ~101 = 010

 5. 쉬프트 연산자 ( a << b ) : 정수 a 를 왼쪽으로 b 비트 만큼  이동

예) 0000101 << 3 = 0101000

 6. 쉬프트 연산자 ( a >> b ) : 정수 a 를 오른쪽으로 b 비트 만큼 이동

예) 111000 >> 3 = 000111

 7. 쉬프트 연산자 ( a >>> b ) : 정수 a를 오른쪽으로 b 비트 만큼 이동 한뒤 왼쪽에는 모두 0 으로 채움

예) 11110000 >>> 3 = 00011110

비트마스크를 이용한 집합 

 비트마스크의 연산을 이용하면 비트마스크를 이용한 집합을 구현할 수 있다. 

기본적으로 0 을 공집합으로 여기고, 꽉찬 집합 ( 비트가 모두 1 인 집합) 을 구할 수 있다.

또한 집합에 원소를 추가하거나 삭제, 번경을 할 수 있으며 두 집합에 대해 연산도 가능하다.

집합의 크기 또한 구할 수 있는데 예를 들어 32비트 부호없는 정수를 a 에서 켜진 비트 (1) 의 수를 구할 수 있다. 구하는 방법은 언어 또는 컴파일러 별로 최적화되어 구현되어 있기 때문에 사용할 수 있다.

 1. gcc/g++ : __builtin_popcount(a)

 2. Visual C++ : __popcnt(a)

 3. java : Integer.bitCount(a)