비트연산
비트연산을 사용해서 부분 집합을 표현하는 방법
비트연산 종류
•
&(and) , |(or), ~(not), ^(xor)
비트연산 방법
•
A = 27, B = 83 인 경우
•
A = 11011 , B = 1010011
◦
A & B = 19
◦
A | B = 91
◦
A ^ B = 72
비트연산의 시간복잡도
O(1) 내부에서 알아서 상수시간 안에 처리
•
not 연산은 자료형에 따라 달라짐
•
shift left (<<) , shift right(>>)
◦
shift left의 경우 0이 추가로 생기고
◦
shift right의 경우 낮은 자리 비트를 없애 버린다.
2^n → ( 1 << N )
(A+B)/2 → (A+B) >> 1
비트연산의 장점
정수로 집합을 나타낼 수 있다
•
{1,3,4,5,9} = 570 = 2+8+16+32+512 와 같이 원래는 배열을 이용했던 것을 정수 하나로 표현할 수 있다는 장점이 있다
비트마스크는 정수이다
•
정수라는 점이 가장 중요함 정수이기 때문에 하나만 넘기어 주면 시간과 공간을 절약함
필수
보통 N개로 이루어져 있으면 0~(N-1) 까지 정수로 이루어진 집합을 나타낼 때 사용
(1~N) 이면 공간이 2배 더 필요함
여러가지 연산
•
검사
◦
어떤 수가 포함되어 있는지는 &연산을 사용
•
추가
◦
추가연산의 경우 그 비트를 1로 바꾸어주면 된다 |연산 사용
•
제거
◦
제거하고 싶은 비트만 0으로 만들고 &연산
