종만북 비트마스크 연산자 기본예제, swift언어로 보기

안녕하세요. 종만북(알고리즘 문제해결전략 책) 비트마스킹 파트 초반에 나오는 비트마스크 피자집 기본예제를 swift언어로 풀어봤습니다. 상기할겸 기록으로 남겨봅니다. 맨 아래에는 코드도 공유드릴게요. 빠르게 시작해보겠습니다.
✓ 본 포스팅에서 index번째라는 것은 zero-based numbering 기준으로 index번째를 의미하는 점 참고해주세요.

---

1) 비트마스킹으로 모든 원소 채우기(꽉찬 집합 구하기)

첫번째 예제, 비트마스킹으로 20개의 원소 채우기, 꽉찬 집합 만들기입니다. 2진수에서 1은 해당 인덱스에 원소가 있음을, 0은 원소가 없을을 의미하고 시작합니다.

7행) 상수로 선언한 fulllPizza값은 이진수로 봤을때 20개의 1로 가득차게 상태가 됩니다.
원리를 보자면, 1을 20번 shift하면 이진수로 볼때 좌측 끝에 1 하나가 남고, 이후 우측은 20개의 0으로 채워지죠. 여기에 1을 빼면 맨 좌측에 위치하던 1은 0이 되고, 우측에 있던 20개의 0은 모두 1이 됩니다. 그 결과로 20개의 원소를 모두 채우는 형태인 꽉찬 집합을 표현할 수 있습니다. (11111111111111111111₍₂₎)

출력 결과는 위 화면을 참고하시면 됩니다.
✶ String(_: Int, radix: Int)를 사용하면 10진수를 2진수로 변환할 수 있어요.

---

2) 비트마스킹으로 특정 위치에 원소 추가하기

2번째 예제, 비트마스킹 특정 위치에 원소 추가하는 예제입니다. zero-based numbering 기준으로 index번째 위치에 원소를 추가하는 예제입니다. 초기 이진수, 1010010₍₂₎(10진수값 82)의 5번째에 원소를 추가하는 예제입니다.

1010010₍₂₎ | 100000₍₂₎(1 << index) 즉, or 연산을 통해서 5번째 위치에 1 원소가 추가됩니다.(1110010₍₂₎)

출력 결과는 위 로그와 같습니다.

---

3) 비트마스킹으로 특정 위치에 원소가 있는지 확인하기

세번째, 비트마스킹으로 특정 위치에 원소가 있는지 확인하는 방법입니다. toppings값은 십진수로 64, 이진수로는 "1000000₍₂₎"가 됩니다.

toppings의 특정 위치의 값이 존재하는지는 1을 index번 left shift 한 이진수와 &(AND) 연산을 하면 값이 존재하는지 확인할 수 있습니다.(index번째가 원소가 있는경우에 true, 없으면 false)

topping의 5, 6번째 원소 유무 출력결과는 위 로그와 같습니다.

---

4) 비트마스킹으로 특정 위치의 원소 추가 및 제거하기

4번째는 앞서 2번째 예제의 방법으로 OR연산 원소 추가를 한 후, 다시 원소를 제거하는 예제입니다.
34 ~ 36행) 초기 이진수 값은 1000100₍₂₎입니다.
38 ~ 41행) 4번째 위치에 원소를 추가합니다.
4번째 위치에만 1이 있는 이진수(10000₍₂₎)와 OR연산을 해서 1010100₍₂₎가 되었습니다.(toppinngs |= (1 << index)
43 ~ 47행) 이번에는 2번째 위치 원소를 제거합니다.
topping과 2번째 위치에 1이 있는 이진수의 ~ NOT연산 결과를 AND 연산합니다. (toppings &= ~(1 << index)) 해당 연산으로 index 위치는 한쪽이 무조건 0이 되므로 AND연산을 할 경우 무조건 0이 되고 이는 원소 제거를 의미합니다.
1010100₍₂₎ -> 1010000₍₂₎가 되었습니다.
위와 같이 특정 위치에만 1이 있는 이진수가 K라고 가정할때 K와의 OR연산으로 특정 위치의 원소를 추가하거나, K의 NOT연산 결과와의 AND연산으로 원소를 제거할 수 있었습니다. 출력 결과는 위 로그를 참고하세요.

---

5) 비트마스킹으로 특정 위치의 원소 toggle하기

5번째입니다. XOR연산을 통해 특정 위치의 원소값이 0이면 1로, 1이면 0으로 toggle할 수 있습니다.
XOR연산은 비교하는 대상이 한개만 1(true)일 경우에 1(true)이 됩니다. 이를 이용해서 index번째에만 1이고, 나머지 위치가 0인 이진수 K의 XOR연산으로 index번째의 값을 toggle할 수 있습니다.

위 코드의 경우, index번째의 XOR연산을 3번 반복하며, 연산 이후 결과를 출력하고 있습니다. 초기 2진수 1010000₍₂₎에서 5번째 자리 원소를 toggle하면서 1110000₍₂₎ -> 1010000₍₂₎ -> 1110000₍₂₎ -> ... 와 같이 toggle이 되는 모습입니다.

출력결과는 위 로그와 같습니다.

---

6) swift 비트마스킹 합집합, 교집합, 차집합, XOR집합 연산

6번째 대표적인 비트연산 사용방법입니다. 다른 언어와 동일한 방식으로 비트연산자를 사용해서 비트연산을 할 수 있습니다. A, B는 각각 십진수로 45, 55입니다. A, B를 이진수로 변환하면
- A : 101101₍₂₎
- B : 110111₍₂₎
가 됩니다. 이에 대해서 위와 같이 비트연산자를 사용해서 집합연산이 가능합니다.

비트연산 출력결과는 위 로그를 참고하세요.

---

오늘은 종만북 비트마스크 파트의 극 초반 맛보기 부분을 swift언어로 풀어서 정리해봤습니다. swift언어로도 다른 언어와 동일하게 비트연산, 비트마스킹을 할 수 있었습니다. 이후에도 포스팅 할만한게 생기면 올려보겠습니다. 즐거운 코딩하시길 바랍니다.

✶ 피드백 댓글 환영합니다! 그럼 ㅂㅇ~
+ 아.. 전체 소스코드 아래에 공유합니다. ㅅㄱㅇ

import Foundation

print("1) 비트마스킹 20개의 원소 채우기")
// 이진수 1을 좌측으로 20번 shift -> 100000000000000000000가 됩니다.
// 011111111111111111111
let fullPizza: Int = (1 << 20) - 1
var bitString = String(fullPizza, radix: 2)

print("10진수 결과 : \(fullPizza)")
print("2진수 결과 : \(bitString)", terminator: "\n\n")

print("2) 비트마스킹 index번째 위치에 원소 추가하기")
var toppings: Int = 82
var index = 5 // zero-based numbering 기준, index번째에 원소 추가
print("원소 추가 전 10진수 결과 : \(toppings)")
print("원소 추가 전 2진수 결과 : \(String(toppings, radix: 2))")
toppings |= (1 << index)
print("\(index)번째 원소 추가 후 10진수 결과 : \(toppings)")
print("\(index)번째 원소 추가 후 2진수 결과 : \(String(toppings, radix: 2))", terminator: "\n\n")

print("3) 특정 위치에 원소가 존재하는지 체크하기")
toppings = 64
print("toppings 2진수 결과 : \(String(toppings, radix: 2))")
// index == 5
[index, index+1].forEach { idx in
    // idx번째 원소가 있는지 체크하기
    print("In \(idx)th place...",
          ((toppings & (1 << idx)) != 0) ? " there's element" : " there's nothing",
          separator: "\n", terminator: "\n\n")
}

print("4) 특정 위치의 원소 추가/제거하기")
toppings = 68
print("초기 10진수 결과 : \(toppings)")
print("초기 2진수 결과 : \(String(toppings, radix: 2))")

index = 4
toppings |= (1 << index)
print("\(index)번째 원소 추가 후 10진수 결과 : \(toppings)")
print("\(index)번째 원소 추가 후 2진수 결과 : \(String(toppings, radix: 2))")

// index번째 원소 제거하기
index = 2
toppings &= ~(1 << index)
print("\(index)번째 원소 제거 후 10진수 결과 : \(toppings)")
print("\(index)번쨰 원소 제거 후 2진수 결과 : \(String(toppings, radix: 2))", terminator: "\n\n")

print("5) index번째 원소 toggle하기")
toppings = 80
index = 5
print("원소 toggle 전 10진수 결과 : \(toppings)")
print("원소 toggle 전 2진수 결과 : \(String(toppings, radix: 2))")

// index번째 원소 3번 반복 toggle하기
print((0..<3).enumerated().reduce(into: [String]()) { result, tuple in
    toppings ^= (1 << index)
    result.append("\(tuple.offset + 1)번째 토글 후 2진수 결과 : \(String(toppings, radix: 2))")
}.joined(separator: "\n"), terminator: "\n\n")

print("6) 비트마스크 합집합, 교집합, 차집합, XOR연산(둘 중 하나에만 원소가 있는 집합)")
let A = 45
print("A 이진수 값 \(String(A, radix: 2))")
let B = 55
print("B 이진수 값 \(String(B, radix: 2))")

// 6-1) 합집합
print("A와 B의 합집합 \(String(A | B, radix: 2))")
// 6-2) 교집합
print("A와 B의 교집합 \(String(A & B, radix: 2))")
// 6-3) 차집합
print("A와 B의 차집합 \(String(A & ~B, radix: 2))")
// 6-4) XOR연산(둘 중 하나에만 원소가 있는 집합)
print("A와 B의 XOR집합 \(String(A ^ B, radix: 2))")