[알고리즘] 비트연산자, 비트마스킹

https://blog.naver.com/kks227/220787042377

비트마스킹(Bit Masking)

카카오 모의 코딩테스트 탈탈 털린 후 정리하면서 쓰는 포스팅!

배움의 길은 멀고도 험하다..

 

아무튼 전부터 공부해봐야지 맘먹고 있던 비트마스킹

아직 많은 알고리즘들을 공부해보지 않아서 비트마스킹의 쓰임새에 대해 다 알 순 없지만,

순열, 조합 등의 문제에 쓰면 좋을 것 같다(일단 내가 아는 범위 내에선)

 

1,0 값을 가지는 N사이즈 배열이 필요할 때,

배열 대신에 N비트의 정수를 사용해 각 비트에 값을 저장한다는게 컨셉이다.

 

평소에는 그냥 배열로 써도 크게 상관없겠으나

저 배열을 재귀함수 매개변수로 넘겨준다는 생각을 하면 끔찍하므로..ㅠ_ㅠ

비트마스킹을 이용하면 좋을 듯 하다!

---

 

간단하게 정리해보는 비트연산자

1. 시프트 연산자: <<, >>

<<, >> 요놈들이 시프트 연산자이다.

1 << 3

이런 식이 있으면, 왼쪽 피연산자의 비트(00000001)를 연산자 방향으로 오른쪽 피연산자만큼 이동시킨다

=> 결과값은 00001000

2. NOT 연산자: ~

비트 0은 1로, 1은 영으로 만들어준다

1000 => 0001

3. AND 연산자: &

두 비트가 모두 1일때만 1이 된다.

4. OR 연산자: |

두 비트 중 하나만 1이면 1이 된다.

5. XOR 연산자: ^

두 비트의 값이 다를 때에만 1이 된다(0,1 또는 1,0)