비트

비트는 0이나 1의 값을 가질 수 있고, 각각은 참, 거짓 혹은 서로 배타적인 상태를 나타낸다.

단위

바이트

바이트는 비트가 여러 개 모인 것으로 원래는 크기가 명확히 정해져 있지는 않다. 그렇지만, 일반적으로 8bit가 1byte다.

비트 연산

&.|,^ 연산

두 수 A,B를 비트 연산 하는 경우, 가장 뒷 자리 부터 하나씩 연산을 수행하면 된다.

A = 27 B = 83</br> = 11011 = 1010011</br>

~ 연산

A = 83 = 1010011 ~A = 10101100 8bit A = 01010011 -> 10101100 8bit여서 젤 앞에 0이 붙는다.

~A = 11111111 11111111 11111111 10101100 32bit

자료형이 signed랑 unsinged에도 값이 달라진다.

shift 연산(«, »)

«

A « B (A를 왼쪽으로 Bbit만큼 민다.) = A * 2**B

• 1 « 0 = 1
• 1 « 1 = 2 (10)
• 1 « 2 = 4 (100)
• 1 « 3 = 8 (1000)
• 1 « 4 = 16 (10000)
• 3 « 3 = 24 (11000)
• 5 « 10 = 5120 (1010000000000)

»

A » B (A를 오른쪽으로 Bbit만큼 민다.) = A // 2**B

• 1 » 0 = 1
• 1 » 1 = 0 (0)
• 10 » 1 = 5 (101)
• 10 » 2 = 2 (10)
• 10 » 3 = 1 (1)
• 30 » 1 = 15 (1111)
• 1024 » 10 = 1 (1)

비트 마스크

True/False 로 구분하는 것이다. True이면 1놓고 False이면 0을 놓는 것이다.

• 570 = 2+(23)+(24)+(25)+(29)</br> = {1,3,4,5,9}</br> = 1000111010

포함 되어있는지 검사

0이 포함되어 있는지 궁금하면 0번째 비트를 1로 표현을 해주고 &연산을 하면 된다.

1000111010
&        1
-----------
         0

즉 x가 들어있는지 궁금함으로 x번째 비트만 1로 만들면 되니 쉬프트 연산을 하면된다.

그렇게 하면 판단 할 수 있는 이유는 and 연산은 둘중 하나라도 0이면 0 이기 때문이다. 둘다 1이여야만 나오기 때문에 위치를 알려준다.

• 0 포함 되어있는지 검사</br> 570 & (2**0) = 570 & (1 « 0) = 0
• 1 포함 되어있는지 검사</br> 570 & (2**1) = 570 & (1 « 1) = 2
• 2 포함 되어있는지 검사</br> 570 & (2**2) = 570 & (1 « 2) = 0
• 3 포함 되어있는지 검사</br> 570 & (2**3) = 570 & (1 « 3) = 8

특정 수 추가하기

• 1 추가하기</br> 570 | (2**1) = 570 | (1 « 1) = 570
• 2 추가하기</br> 570 | (2**2) = 570 | (1 « 2) = 574
• 3 추가하기</br> 570 | (2**3) = 570 | (1 « 3) = 570
• 4 추가하기</br> 570 | (2**4) = 570 | (1 « 4) = 570

특정 수 제거하기

~를 한다음에 &를 하면 원래 1 이었던 애는 0이 되고 1 이었던 애는 0 이된다. 그래서 1인 애가 0이 되어 제거가 됩니다.

1000111010
        1
1111111101   < 1을 ~후 >
1000111000   < 570과 &연산 후 >

• 1 제거하기</br> 570 & ~(2**1) = 570 & ~(1 « 1) = 568
• 2 제거하기</br> 570 & ~(2**2) = 570 & ~(1 « 2) = 570
• 3 제거하기</br> 562 & ~(2**3) = 562 & ~(1 « 3) = 562
• 4 제거하기</br> 562 & ~(2**4) = 562 & ~(1 « 4) = 546

전체 집합

(1 « N)-1 = 2^N -1

공집합

0

비트 마스크를 사용하는 사례

1. 모든 경우를 살표봐야 하는데 어떤 길이가 N인 것의 부분집합을 살펴보아야 할 (혹은 완전 탐색 시) 재귀호출 없이 해결할 수 있다.
2. 상태를 인덱스에 넣어야 하는 다이나믹이 있는, 그 때 사용된다.

보수

관련 설명은 따로 다른 포스팅에 해 놨따.

https://joosjuliet.github.io/2_s_complement/

관련 문제

https://www.acmicpc.net/problem/11723

내답

https://joosjuliet.github.io/11723/