> For the complete documentation index, see [llms.txt](https://sois-organization.gitbook.io/today-i-learned/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sois-organization.gitbook.io/today-i-learned/undefined-1/undefined-3.md).

# 비트마스킹

### 비트마스킹

#### 이진수

* 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의 보수법

![image](https://user-images.githubusercontent.com/68676844/218310733-f250e817-ae37-4713-aad4-f2379f4ae5e7.png)

***

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

#### idx 번째 비트 끄기

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

```swift
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 연산을 수행한다.

```swift
var s = 18
let idx = 0

print (s | 1 << idx )
```

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

#### index 번째 비트 toggle 하기

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

```swift
let idx = 1
var s = 18

print(s ^ (1 << idx))
```

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

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

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

```swift
let s = 18
print(s & -s)
```

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

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

```swift
var s = 18
let idx = 1

print (s & (3 << idx))
```

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

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

```swift
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가지

```swift
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)
}
```

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

```swift
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) )
}

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