비트마스크

알고리즘 풀다가 비트마스크라는 것을 처음알았다.

 

이진수를 이용해서 집합을 만든다고 이해하면 될 것 같다.

이해한 대로 설명하자면 

비트 하나하나를 집합(set)으로 쓸 수 있다는 것이다.

 

큰 장점은 비트 하나 하나가 집합 하나 하나기 때문에 메모리 사용량이 극도로 적어진다는 것이다.

 

ex)

10진수              2진수

 

 16                     1000

 17                     1001

 31                     1111   

 

즉 만약 length가 4인 집합을 만들고 싶다면 이렇게 4비트의 메모리만 있어도 된다.

여기서 0,1이 false, true값이다.

 

1. 

 

1 << 6

비트 마스크에서 1을 왼쪽으로 6번 올린 것을 뜻한다.

10진수 1은 이진수로 1이다.

즉 왼쪽으로 6번 올렸기 때문에 1000000이 되고 결과적으로 64가 된다. 

 

ex) 1 << 1 은 2이다.

 

2.

만약에 2번째 인덱스가 true인지 확인하고 싶다면

a = 6;
System.out.println((a & 2) == 2); // true

 

a를 2진수로 표현하면 110이다. 즉 1번째 idx는 false, 2,3 번째 idx는 true라고 볼 수 있다.

2가 도출되는 이유는 아래와 같다.

컴퓨터가 비트를 차례로 돌면서 110    010 에서 공통되는  2^1 부분만 1을 받아오기 때문이다. 일치하지 않으면 0을 받는다.

 

3.

 

수 추가

idx를 추가하고 싶다면

a = 30;
b = 1;
System.out.println(a|b); // 31

a 와 b는 다음과 같다

1110   0001

 

or 연산자이기 때문에 컴퓨터가 비트를 돌면서 1111로 합쳐줘서 31이 나온다.

하지만 다음의 경우는 다르다. 그래서 집합이라고 하는 것 같다.

 

a = 31;
b = 1;
System.out.println(a|b); // 31

a와 b는 다음과 같다.

1111 0001

어차피 합쳐져도 1111이기 때문에 31이 도출된다. 그래서 set과 같은 기능을 하게 된다.

 

다른 연산자도 있지만 솔직히 집합으로 쓰려면 이것만 알아도 될 것 같다.