KimSeogyu.github.io
비트 연산 활용
종류
| 비트 연산자 | 설명 |
|---|---|
| & | 대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산) |
| | | 대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비트 OR 연산) |
| ^ | 대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산) |
| ~ | 비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산, 1의 보수) |
| << | 명시된 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산) |
| >> | 부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산) |
| >>> | 지정한 수만큼 비트를 전부 오른쪽으로 이동시키며, 새로운 비트는 전부 0이 됨. |
종류 별 예시
비트마스크
| 연산 | 사용 예시 |
| i번째 요소 조회하기 | ``` // 10 & (1 << 2) // 1010 & 0100 // => 0000 // 결과값의 idx=3 요소는 i번째 요소의 존재여부를 나타낸다 n & (1 << i); ``` |
| 변경(삽입) | ``` // 10 | (1 << 2) // 1010 | 0100 // => 1110 // 결과값의 idx=2 요소를 1로 만들었다 n | (1 << i) ``` |
| 삭제 | ``` // 15 & ~(1 << 2) // 1111 & ~0100 // 1111 & 1011 // => 1011 // 결과값의 idx=2 요소를 0으로 만들었다 n & ~(1 << i) ``` |
| 공집합 | ``` int result = 0; ``` |
| 꽉 찬 집합 | ``` // A개의 원소를 가진 집합의 종류 // 점화식으로는 (2**n) - 1 int result = ((1 << A) - 1); ``` |
| 최소 원소 찾기 | ``` int firstBit = b & -b; ``` |
| 최소 원소 지우기 | ``` int removed = origin & (origin-1); ``` |
| 부분 집합 순회 | ``` 집합 A의 부분집합 순회 for (int i = A;; i = ((i - 1) & A)) { ... } ``` |