비트마스트 알고리즘 개념 및 기본

개념

모든 수는 이진법인 비트로 나타낼 수 있다.

일반적으로 1은 true이고 0은 false이다

이는 알고리즘에서 중요한 역할을 하는데

그 이유는 다중으로 true인 경우 하나의 숫자로 나타낼 수 있기 때문이다.

이진법은 다음과 같이 표현할 수 있다.

1	000001
2	000010
4	000100
8	001000
16	010000
32	100000
...	....

예를 들어, 이진법 001100 은 3번째, 4번째가 true인데 십진수로 나타내면 12로 하나의 수로 나타낼 수 있다.

비트 연산자는 다음과 같다.

출처https://ko.wikipedia.org/wiki/C%EC%99%80_C%2B%2B%EC%9D%98_%EC%97%B0%EC%82%B0%EC%9E%90#.EC.97.B0.EC.82.B0.EC.9E.90_.EC.9A.B0.EC.84.A0.EC.88.9C.EC.9C.84

활용

알고리즘에서 자주 쓰는 부분은 key|=1<<n, key&(1<<n)이다.

이것이 의미하는 바는,

*key|=1<<n

알고리즘에서 변수 key에 각각의 인덱스에서 어떤 인덱스가 true인지 false인지 확인하고 싶을때 사용

 1<<n은 십진수인 n을 이진법으로 표현하고 이를 key값에 or로 저장한다.

그러면 기존의 key에 저장된 true와 false값을 유지하고 신규 데이터를 업데이트한다

*key&(1<<n)

주로 if문에서 사용하는 방법으로,

if((key&(1<<n))으로 사용하면 모두가 알다시피, key에 저장된 true중에 n이 가리키는 곳이 true일 경우를 의미한다.

이 두가지만 알면 일반적인 알고리즘에서 자주 사용 할 수있다.