비트마스킹

이진수

0또는 1로 표현한 수의 체계로, “이진법”으로 표현하는 수이다.
일반적으로 다음과 같은 방법을 사용한다. (b: binary의 약자)
- 100101b
- 100101(2)
- 0b100101

이진수를 통한 Bool 배열의 표현

0 : 비트가 꺼져있다. (false)
1: 비트가 켜져있다. (true)

→ 이진수를 이용해 하나의 숫자를 기반으로 Bool 배열을 표현할 수 있다.

비트연산자

💡 +, -의 경우 비트연산자로 볼 수 없다.

덧셈
101 + 1 → 110 (2를 기반으로, 즉 2를 기수로 carry된다. )
뺄셈
10101 - 11 → 10010

| & | 비트 단위로 AND 연산

모두 true여야 true, 나머지는 false | | --- | --- | | | | 비트 단위로 OR 연산
하나라도 true라면 true | | ^ | 비트 단위로 XOR 연산
다르면 true, 같으면 false | | ~ (1의 보수 연산자) | 피연산자의 모든 비트 반전
one’s completion이라고 한다.
~value = -(value + 1) | | << (왼쪽 시프트) | 피연산자의 비트 열을 왼쪽으로 이동
비트를 왼쪽으로 한 칸 이동시킨다.
a << b = a * (2의 b승) | | >> (오른쪽 시프트) | 피연산자의 비트 열을 오른쪽으로 이동
비트를 오른쪽으로 한 칸 이동시킨다.
마지막 비트가 1이었다면, 사라진다.
a >> b = a ( 1/2의 b승) |

음수를 표현하는 방법 : 2의 보수법

비트연산자 활용방법 (암기)

idx 번째 비트 끄기

💡 idx만 0인 비트를 만들고, 기존 비트와 **& 연산**을 수행한다.

var s = 18
let idx = 1

s &= ~(1 << idx)
print(s)

**~(1 << idx)**
- 1 << idx : idx만 1인 비트
- ~(1<<idx) : idx만 0인 비트
& 연산
- 기존 비트 중 idx만 0이 된다.

idx 번째 비트 켜기

💡 idx번째만 1로 만들고, 기존 비트와 OR 연산을 수행한다.

var s = 18
let idx = 0

print (s | 1 << idx )

기존 비트와 OR 연산을 수행하면 idx 번째가 켜진 비트를 확인할 수 있다.

index 번째 비트 toggle 하기

💡 index 번째까지 시프트 연산을 수행하고, 기존 비트와 XOR 연산을 수행한다.

let idx = 1
var s = 18

print(s ^ (1 << idx))

index 번째까지 시프트 연산을 수행한다 → 해당 index만 1로 변한다.
기존 비트와 XOR 연산을 수행한다
- 기존에 1이었던 것들은 다르니까 그대로 1이 된다.
- index 번째는 1이 되었으므로 기존에 1이었다면 0이 됙, 기존에 0이었다면 값이 달라졌으므로 1이 된다.

켜져있는 최하위 비트의 인덱스 찾기

💡 최하위 켜져있는 비트 = 오른쪽부터 탐색하여 가장 먼저 켜져있는 곳

let s = 18
print(s & -s)

idx 비트가 켜져있는지 확인하기

💡 shift 연산으로 idx까지 이동하고, 기존 비트와 OR 연산을 수행한다. 결과가 0이라면 꺼져있고, 아니라면 켜져있는 것이다.

var s = 18
let idx = 1

print (s & (3 << idx))

크기가 N인 집합의 모든 비트를 켜기

💡 n만큼 shift 연산을 수행한 후 1을 뺀다.

var n = 4
print ( (1 << n)-1 )

1000 - 1 = 01111
- 1000 = 1 << 4

비트마스킹

사용하는 이유
- 특정 원소를 찾을 때, 자료구조마다 시간 복잡도가 다르다.
- 배열 : O(n) / sorted Array : O(logN) / Hash : O(1)
- Bool 배열보다 비트연산을 사용하면 더 빠르고 가볍게 조회할 수 있다.
Bool 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색, 수정 등의 작업을 하는 것이 비트마스킹이다.
- 101 = 1과 4의 합집합, {0, 2}로 표현할 수 있다.
- 111 = {0, 1, 2}
왜 비트마스킹이라고 할까?
- 컴퓨터 저장공간인 메모리에는 0이나 1이 저장된다.
- 해당 메모리 용량을 표현하는 단위 중 최소 단위를 비트라고 한다. (0 또는 1로 가진다)
- 해당 비트를 켜거나 꺼서 마스킹하기 때문에 비트마스킹이라고 한다.
- 참고 : 비트 : binary digit의 약어
한계
- 보통 n이 31 이하일 때에만 비트마스킹이 가능하다.
- 2의 30승이 10억이므로 그 이후의 경우의 수는 보통 시간복잡도가 초과된다.
- 즉, 2의 31승 → Int형 숫자의 한계까지 가능 한 것이다.

비트마스킹을 이용한 경우의 수

{ 사과, 딸기, 포도, 배 } 라는 집합의 모든 부분집합을 구하는 방법: 16가지

let list = ["사과", "딸기", "포도", "배"]

for i in 0..<(1 << list.count) { // 0..<16
    var result = ""
    for j in 0..<list.count { // 0..<4
        if i & (1 << j) != 0 { // j번째 비트가 포함됐다면
            result += list[j] + " "
        }
    }
    print(result)
}

비트마스킹을 활용한 매개변수 전달

let list = ["사과", "딸기", "포도", "배"]
let n = list.count

func go(_ num: Int) {
    var result = ""
    for i in 0 ..< 4 {
        if num & (1 << i) != 0 {
            result += list[i] + " "
        }
    }
    print(result)
}

for i in 0 ..< 4 {
    go( 1 | (1 << i) )
}

/*
사과 
사과 딸기 
사과 포도 
사과 배
*/

Previous복잡도 Next운영체제

Last updated 1 year ago