비트마스킹 간단 정리하기

• 지난 게시글에서도 언급했지만, 비트마스킹을 개념적으로는 알고 있는데 아직 활용 예나 실 구현에서 망설이고 헷갈리는 모습을 보이길래 한 번 정리해두면 좋겠다는 생각이 들었다.
• 자바스크립트 기준으로 비트마스킹에 대해 정리하고, 나중에 참고할 수 있도록 자주 사용되는 일례를 기록해두기로.

---

비트마스킹이란?

 

• 데이터를 비트, 즉 2진수의 형태로 표현하는 것을 의미한다.
• 집합이나 배열, 부분집합 등을 표현할 때 활용할 수 있다.
  ex) 5개의 원소를 갖는 집합의 부분집합은 아래와 같이 표현할 수 있다.

const arr = [1, 2, 3, 4, 5];
/*
	{1, 3, 5} 를 원소로 갖는 부분 집합 -> 10101
	{2} 를 원소로 갖는 부분 집합 -> 10000
*/

 

 

왜 사용할까?

• 빠르다. 기본적으로 비트 연산을 수행하기 때문에, 수행 시간이 다른 경우에 비해 짧아지게 된다.
• 메모리 사용량이 적다. 우리가 사용하는 배열이나 집합은 자료형의 크기만큼의 공간을 할당해야 하기 때문에 크기가 커질수록 메모리를 크게 잡아먹게 된다. 그러나 비트마스킹은 모든 데이터를 이진수로 이루어진 정수로 표현하기 때문에 배열이나 집합과 비교하면 훨씬 더 적은 메모리를 사용한다.

⇒ 위와 같은 점들을 들어, 알고리즘 문제 풀이에도 시간 단축 및 메모리 절약을 위해 활발히 쓰이고 있다.

 

 

기본 연산

아래의 연산들은 모두 자바스크립트 기준으로 작성되어있다.

 

& (AND 연산)

두 피연산자의 각 자릿수가 모두 1일 경우에만 1을 반환한다.

const a = 21; // 10101
const b = 8; // 01000
const c = 16; // 10000

console.log(a & b); // 두 수간 자릿수가 모두 1인 경우가 없으므로 0 반환
console.log(a & c); // 가장 왼쪽 자릿수가 1이므로, 이진수 10000 = 16을 반환

 

 

• 주로 집합 등에서 특정 원소가 있는지 아닌지를 확인하는데 쓰인다.

/*
  임의의 원소 5개를 갖는 집합 set이 있고
  set의 부분집합 aSet이 있다고 가정할 때,
  3번째 원소가 있는지 없는지 확인하고자 한다면
*/

console.log(aSet & 4); // 4 => 100

 

 

| (OR 연산)

두 피연산자의 각 자릿수가 하나라도 1일 경우에만 1을 반환한다.

const a = 21; // 10101
const b = 8; // 01000

console.log(a | b); // 11101 => 29 반환

 

 

• 따라서 특정 비트를 1로 바꾸거나, 집합 등에서 특정 원소를 추가할 때 사용한다.

/*
  임의의 원소 5개를 갖는 집합 set이 있고
  공집합 aSet이 있다고 가정할 때,
  3번째 원소를 추가하고자 한다면
*/
let aSet = 0;
aSet &= 4; // 4 => 100

 

 

^ (XOR 연산)

두 피연산자의 각 자릿수가 다를 때만 1을 반환한다.

따라서 특정 비트를 반전시킬 때 사용한다. 반전시키고자 하는 비트가 위치한 자리의 비트만 1인 수와 함께 연산하면 된다.

// a의 2번째 비트만 반전시키는 경우
let a = 31; // 11111
a ^= 8; // 8 => 01000

 

 

~ (NOT 연산)

피연산자의 모든 비트를 반전시킬 때 사용한다.

const a = 21; // 10101
console.log(~a); // 01010 => 12를 반환

 

 

<<, >> (시프트 연산)

비트를 연산자가 가리키는 방향으로 이동시킨다.

• << : 비트를 ‘왼쪽으로’ 이동시킨다. 이동시키고 남은 자리에는 0을 채운다.
• >> : 비트를 ‘오른쪽으로’ 이동시킨다. 이동시키고 남은 자리에는 이동 전 가장 왼쪽에 있던 비트(부호 비트)를 채운다.
  → 이는 비트 연산 이후에도 음수/양수의 부호를 유지하기 위함이다.
  → 비슷한 연산으로 >>> 가 있는데, 비트를 오른쪽으로 이동시키는 것은 똑같으나 이동시키고 남은 자리에 무조건 0을 채운다는 점이 다르다.

 

+) 활용 일례?

사실 비트마스킹을 자주 써서 익숙한 상태라면 바로바로 작성할 수 있는 부분인데 나는 아직인지 헷갈릴 때가 있다. 그때 금방금방 떠올릴 수 있게끔 몇 가지 사용했던 일례를 기록한다. 나중에 추가가 될 수도?

• N개의 원소를 갖는 집합 혹은 배열: (1 << N) - 1
• N번째 비트가 1인지 아닌지 확인

const set = /* ... */;

if (x & (1 << N)) {} // n번째 비트가 1이면 true