비트 마스크

비트마스크란?

비트마스크란 컴퓨터의 언어인 이진수를 활용해 정수를 이진수 형태로 표현하여 비트 연산을 활용하는 방법을 의미하는 것입니다. 여기서 중요한 것은 이진수 입니다.

기본적인 비트 연산

여러번 정리 했지만, 스스로 쓰는 일은 없어서 복붙을 해보았습니다. 대신 주피터 노트북에서 한번 실습을 했습니다. 아는것과 쓸 줄 아는건 다릅니다. 저 말고 모두가 다 같이 비트연산자를 주피터 노트북에 써봅시다.(진지)

A	B	~A	A&B	A|B	A^B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

더보기

쉬프트 연산의 활용

갓 수학과 블로그님이 정리해준 자료입니다.

쉬프트 연산을 활용하여 몇몇 계산을 빠르게 수행할 수 있습니다.

• A * 2^B == A<<B

  A 를 2의 B 제곱만큼 곱해주는 연산입니다. A 를 왼쪽으로 1비트 이동할 때마다 2가 곱해지는 것과 동일하므로A << B으로 구현할 수 있습니다.

• A / 2^B == A>>B

  A 를 2의 B 제곱만큼 나눠주는 연산입니다. 위와 같은 원리로A >> B으로 구현할 수 있습니다.

• N%2 ==1 == N&1

  N 이 짝수인지 홀수인지 판별하기 위해서 2로 나눈 나머지를 구해 1과 비교하는 연산입니다. 결론부터 이야기하면N&1과 같이 구할 수 있습니다.

Check

S에i가 포함되어 있는지를 확인할 수 있습니다.

S & (1 << i) // 포함되어 있을 경우 2^i, 포함되어 있지 않을 경우, 0

Add

S에i를 추가할 수 있습니다.

S = S | (1 << i)

추가하기 위해서 단순히+, 덧셈으로도 구현할 수 있지만 이 경우, 이미 존재할 경우 올림이 되어 예상하지 않은 값이 결과로 나옵니다.

Remove

S에i를 제거할 수 있습니다.

S = S & ~(1 << i)

Toggle

S에i가 있으면 제거하고 없으면 추가해줍니다.

S = S ^ (1<< i)

All

S를 모두 1로 가득채워줍니다.

S = (1 << N) -1

Empty

S = 0

이 알고리즘은 ssungkang.tistory.com/entry/Algorithm-비트마스크?category=346622이 블로그를 참고해 정리되었음을 명시합니다.