kingsubin

비트 연산 (Bitwise operation)

• & (and)
• | (or)
• ~ (not)
• ^ (xor)

 

not 연산의 경우에는 자료형에 따라 결과가 달라진다.

A = 83 = 0101,0011(2)

~A = 1010,1100(2) / 8비트 자료형인 경우

~A = 1111,1111 1111,1111 1111,1111 10101,100(2) / 32비트 자료형인 경우

 

Shift Operators

1. shift left (<<)

- A << B (A를 왼쪽으로 B만큼 민다)

1 << 0 = 1

1 << 1 = 10(2) = 2

1 << 2 = 100(2) = 4

1 << 3 = 1000(2) = 8

3 << 3 = 11000(2) = 24

5 << 10 = 1010000000000(2) = 5120

 

2. shift right (>>)

- A >> B (A를 오른쪽으로 B만큼 민다)

1 >> 0 = 1

1 >> 1 = 0(2) = 1

10 >> 1 = 101(2) = 5

10 >> 2 = 10(2) = 2

10 >> 3 = 1(2) = 1

30 >> 1 = 1111(2) = 15

1024 >> 10 = 1(2) = 10

 

A << B 는 A * 2^B 와 같다.

A >> B 는 A / 2^B 와 같다.

(A+B) / 2 는 (A+B) >> 1 로 쓸 수 있다.

 

비트 연산을 사용할 때는 연산자 우선 순위를 생각해야 한다.

#Q :1 << N -1

 

1. (1 << N) - 1 

2. 1 << (N -1)

 

#A : 1 << (N - 1)

 

비트마스크

- 정수의 이진수 표현을 자료구조로 쓰는 기법

 

비트마스크의 장점

1. 수행 시간이 빠르다.
   1. bit 연산이기 때문에 O(1)에 대부분 구현됨. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르다.
   2. 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다.
2. 코드가 짧다.
3. 메모리 사용량이 더 적다.
   1. ex) bit 가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 2^10 가지의 경우를 10bit 이진수 하나로 표현이 가능하다.
   2. 이처럼 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 있다. (DP 에서 유용)

 

 

정수로 집합을 나타낼 수 있다.

{1, 3, 4, 5, 9} => 0101110001 => 2^1 + 2^3 + 2^4 + 2^5 + 2^9

 

• 보통 0부터 N-1 까지 정수로 이루어진 집합을 나타낼 때 사용한다.
• 0부터 N-1까지로 변형해서 사용하는 것이 더 좋다.

 

1. 포함되어 있는지
2. 추가하기
3. 제거하기
4. 토글하기

 

- 전체집합 (1 << N) - 1

- 공집합 0

 

현재 집합이 S 일때

i 를 검사 (and)

- S & (1 << i)

 

i 를 추가 (or)

- S | (1 << i) 

 

i 를 제거 (not)

- S & ~(1 << i)

 

i 를 토글 (xor)

- S ^ (1 << i)

 

 

- 물론 배열을 사용하는 것이 더욱 편리하지만, 비트마스크를 사용하는 이유는 집합을 배열의 인덱스로 표현할 수 있기 때문이다.

- 상태 다이나믹을 할 때 자주 사용하게 된다.

 

https://wogud6792.tistory.com/63

 

---

# 연습문제 BOJ

11723 :: 집합

1182 :: 부분수열의 합

14889 :: 스타트와 링크

14391 :: 종이 조각

---

※ 출처

wogud6792.tistory.com/63