n개의 비트로 구성된 고정 크기의 시퀀스다. 비트 배열(bit array) 또는 비트 벡터(bit vector)라고도 한다.
어떤 것이 참인지 거짓인지 저장할 때는 Bool을 사용한다. 모든 프로그래머가 이 사실을 알고 있다. 하지만 10,000개의 항목이 참인지 거짓인지 기억해야 한다면 어떻게 해야 할까?
10,000개의 불리언으로 이루어진 배열을 만들 수도 있지만, 더 강력한 방법으로 10,000개의 비트를 사용할 수도 있다. 이 방식은 훨씬 더 효율적이다. 10,000개의 비트는 64비트 CPU에서 160개 미만의 Int에 저장할 수 있기 때문이다.
개별 비트를 다루는 것은 다소 까다로울 수 있다. 이때 BitSet을 사용해 복잡한 작업을 숨길 수 있다.
비트 집합(BitSet)은 기본적으로 배열을 감싸는 래퍼이다. 이 배열은 개별 비트를 저장하지 않고 "워드"라고 불리는 더 큰 정수를 저장한다. BitSet의 주요 역할은 비트를 올바른 워드에 매핑하는 것이다.
public struct BitSet {
private(set) public var size: Int
private let N = 64
public typealias Word = UInt64
fileprivate(set) public var words: [Word]
public init(size: Int) {
precondition(size > 0)
self.size = size
// 크기를 64의 다음 배수로 올림
let n = (size + (N-1)) / N
words = [Word](repeating: 0, count: n)
}
N은 워드의 비트 크기를 나타낸다. 여기서는 64비트로 설정했는데, 이는 비트를 64비트 부호 없는 정수 목록에 저장하기 때문이다. (물론 BitSet을 32비트 워드를 사용하도록 변경하는 것도 간단하다.)
만약 다음과 같이 코드를 작성한다면,
var bits = BitSet(size: 140)BitSet은 세 개의 워드로 구성된 배열을 할당한다. 각 워드는 64비트를 가지므로, 세 개의 워드는 총 192비트를 저장할 수 있다. 여기서는 140비트만 사용하므로 약간의 공간이 낭비된다. (물론 전체 워드보다 적은 비트를 사용할 수는 없다.)
참고:
words배열의 첫 번째 항목은 최하위 워드(least-significant word)이다. 따라서 이 워드들은 배열에 리틀 엔디안 순서로 저장된다.
BitSet의 대부분의 연산은 비트의 인덱스를 매개변수로 받는다. 따라서 특정 비트가 포함된 단어를 찾는 방법이 필요하다.
private func indexOf(_ i: Int) -> (Int, Word) {
precondition(i >= 0)
precondition(i < size)
let o = i / N
let m = Word(i - o*N)
return (o, 1 << m)
}indexOf() 함수는 단어의 배열 인덱스와 해당 단어 내에서 비트의 위치를 정확히 나타내는 "마스크"를 반환한다.
예를 들어, indexOf(2)는 튜플 (0, 4)를 반환한다. 비트 2가 첫 번째 단어(인덱스 0)에 위치하기 때문이다. 마스크는 4이다. 이진수로 표현하면 마스크는 다음과 같다.
0010000000000000000000000000000000000000000000000000000000000000
이 1은 단어 내 두 번째 비트를 가리킨다.
참고: 모든 것은 리틀 엔디안 순서로 표시된다. 비트 자체도 마찬가지다. 비트 0은 왼쪽에, 비트 63은 오른쪽에 위치한다.
또 다른 예로, indexOf(127)은 튜플 (1, 9223372036854775808)을 반환한다. 이는 두 번째 단어의 마지막 비트이다. 마스크는 다음과 같다.
0000000000000000000000000000000000000000000000000000000000000001
마스크는 항상 64비트이다. 데이터를 한 번에 하나의 단어로 처리하기 때문이다.
특정 비트의 위치를 알게 되면, 해당 비트를 1로 설정하는 것은 간단하다:
public mutating func set(_ i: Int) {
let (j, m) = indexOf(i)
words[j] |= m
}이 코드는 단어 인덱스와 마스크를 찾은 후, 해당 단어와 마스크 간에 비트 OR 연산을 수행한다. 비트가 0이었다면 1로 바뀌고, 이미 설정되어 있었다면 그대로 유지된다.
비트를 0으로 초기화하는 것도 마찬가지로 간단하다:
public mutating func clear(_ i: Int) {
let (j, m) = indexOf(i)
words[j] &= ~m
}이번에는 비트 OR 대신 마스크의 역수와 비트 AND 연산을 수행한다. 예를 들어 마스크가 00100000...0라면, 역수는 11011111...1이 된다. 모든 비트가 1이 되며, 단지 원하는 비트만 0으로 바뀐다. & 연산의 특성상, 다른 비트는 그대로 유지되고 해당 비트만 0으로 변경된다.
특정 비트가 설정되었는지 확인하려면 역수를 사용하지 않고 비트 AND 연산을 수행한다:
public func isSet(_ i: Int) -> Bool {
let (j, m) = indexOf(i)
return (words[j] & m) != 0
}이 기능을 더 자연스럽게 표현하기 위해 서브스크립트 함수를 추가할 수 있다:
public subscript(i: Int) -> Bool {
get { return isSet(i) }
set { if newValue { set(i) } else { clear(i) } }
}이제 다음과 같은 코드를 작성할 수 있다:
var bits = BitSet(size: 140)
bits[2] = true
bits[99] = true
bits[128] = true
print(bits)이 코드는 140비트 BitSet이 모든 정보를 저장하는 데 사용하는 세 개의 단어를 출력한다:
0010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000010000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000비트를 다루는 또 다른 재미있는 작업은 비트를 뒤집는 것이다. 이는 0을 1로, 1을 0으로 바꾼다. 다음은 flip() 함수이다:
public mutating func flip(_ i: Int) -> Bool {
let (j, m) = indexOf(i)
words[j] ^= m
return (words[j] & m) != 0
}이 함수는 배타적 OR 연산자를 사용해 비트를 뒤집는다. 또한 함수는 비트의 새로운 값을 반환한다.
BitSet의 많은 함수들은 구현이 상대적으로 쉽다. 예를 들어, 모든 비트를 0으로 초기화하는 clearAll() 함수는 다음과 같다:
public mutating func clearAll() {
for i in 0..<words.count {
words[i] = 0
}
}모든 비트를 1로 설정하는 setAll() 함수도 있다. 하지만 이 함수는 미묘한 문제를 처리해야 한다.
public mutating func setAll() {
for i in 0..<words.count {
words[i] = allOnes
}
clearUnusedBits()
}먼저, 배열의 모든 워드에 1을 복사한다. 이제 배열은 다음과 같다:
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111하지만 이는 올바르지 않다. 마지막 워드의 대부분 비트를 사용하지 않으므로 해당 비트는 0으로 남겨야 한다:
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111110000000000000000000000000000000000000000000000000000192개의 1비트 대신 이제 140개의 1비트만 있다. 마지막 워드가 완전히 채워지지 않을 수 있다는 사실은 항상 이 마지막 워드를 특별하게 처리해야 함을 의미한다.
이 "남은" 비트를 0으로 설정하는 작업은 clearUnusedBits() 헬퍼 함수가 수행한다. BitSet의 크기가 N(즉, 64)의 배수가 아닌 경우, 사용하지 않는 비트를 지워야 한다. 이를 수행하지 않으면 크기가 다른 두 BitSet 간의 비트 연산이 잘못될 수 있다(예제가 이어짐).
이 작업은 고급 비트 조작을 사용하므로 주의 깊게 살펴보자:
private func lastWordMask() -> Word {
let diff = words.count*N - size // 1
if diff > 0 {
let mask = 1 << Word(63 - diff) // 2
return mask | (mask - 1) // 3
} else {
return ~Word()
}
}
private mutating func clearUnusedBits() {
words[words.count - 1] &= lastWordMask() // 4
}이 함수가 수행하는 작업을 단계별로 살펴보자:
diff는 "남은" 비트의 수다. 위 예제에서는 3*64 - 140 = 52이므로 52다.
아직 유효한 가장 높은 비트가 1이고 나머지는 모두 0인 마스크를 생성한다. 예제에서는 다음과 같다:
0000000000010000000000000000000000000000000000000000000000000000
1을 빼서 다음과 같이 만든다:
1111111111100000000000000000000000000000000000000000000000000000
그리고 높은 비트를 다시 추가해 다음을 얻는다:
1111111111110000000000000000000000000000000000000000000000000000
이제 이 워드에는 12개의 1비트가 있다. 140 - 2*64 = 12이기 때문이다.
이 작업이 중요한 예는 크기가 다른 두 BitSet을 결합할 때다. 설명을 위해 두 8비트 값의 비트 OR 연산을 살펴보자:
10001111 size=4
00100011 size=8
첫 번째 값은 처음 4비트만 사용한다. 두 번째 값은 8비트를 사용한다. 첫 번째 값은 실제로 10000000이어야 하지만 끝의 1비트를 지우지 않았다고 가정하자. 그러면 두 값의 비트 OR 연산 결과는 다음과 같다:
10001111
00100011
-------- OR
10101111
이는 잘못된 결과다. 두 개의 1비트가 여기에 있으면 안 되기 때문이다. 올바르게 수행하려면 다음과 같이 해야 한다:
10000000 사용하지 않는 비트를 먼저 0으로 설정!
00100011
-------- OR
10100011
| 연산자는 다음과 같이 구현된다:
public func |(lhs: BitSet, rhs: BitSet) -> BitSet {
var out = copyLargest(lhs, rhs)
let n = min(lhs.words.count, rhs.words.count)
for i in 0..<n {
out.words[i] = lhs.words[i] | rhs.words[i]
}
return out
}개별 비트가 아니라 전체 워드를 | 연산하는 것에 주목하자. 개별 비트를 연산하면 너무 느려진다! 또한 왼쪽과 오른쪽 BitSet의 비트 수가 다를 경우 추가 작업이 필요하다. 두 BitSet 중 더 큰 것을 out 변수에 복사한 후, 더 작은 BitSet의 워드와 결합한다.
예제:
var a = BitSet(size: 4)
a.setAll()
a[1] = false
a[2] = false
a[3] = false
print(a)
var b = BitSet(size: 8)
b[2] = true
b[6] = true
b[7] = true
print(b)
let c = a | b
print(c) // 1010001100000000...0비트 AND(&), XOR(^), 그리고 반전(~) 연산도 비슷한 방식으로 구현된다.
1로 설정된 비트의 개수를 세기 위해 전체 배열을 스캔할 수 있다. 이 방법은 O(n) 시간 복잡도를 가진다. 하지만 더 효율적인 방법이 존재한다:
public var cardinality: Int {
var count = 0
for var x in words {
while x != 0 {
let y = x & ~(x - 1) // 가장 낮은 1비트 찾기
x = x ^ y // 해당 비트 지우기
++count
}
}
return count
}x & ~(x - 1)을 사용하면 단 하나의 비트만 설정된 새로운 값을 얻는다. 이는 가장 낮은 위치의 1비트를 의미한다. 예를 들어, 다음 8비트 값을 살펴보자. (여기서는 최하위 비트를 왼쪽에 표시한다):
00101101
먼저 1을 빼면 다음과 같은 결과가 나온다:
11001101
그 다음 모든 비트를 반전시킨다:
00110010
이제 원래 값과 비트 AND 연산을 수행한다:
00101101
00110010
-------- AND
00100000
두 값이 공통으로 가지는 유일한 비트는 가장 낮은 위치의 1비트다. 그런 다음 원래 값에서 XOR 연산을 통해 해당 비트를 지운다:
00101101
00100000
-------- XOR
00001101
이 결과는 원래 값에서 가장 낮은 1비트가 제거된 상태다.
이 과정을 값이 모두 0이 될 때까지 반복한다. 시간 복잡도는 **O(s)**이며, 여기서 s는 1비트의 개수를 의미한다.
비트 시프트는 비트셋을 다룰 때 자주 사용하는 매우 유용한 기법이다. 다음은 오른쪽 시프트를 수행하는 함수다:
public func >> (lhs: BitSet, numBitsRight: Int) -> BitSet {
var out = lhs
let offset = numBitsRight / lhs.N
let shift = numBitsRight % lhs.N
for i in 0..<lhs.words.count {
out.words[i] = 0
if (i + offset < lhs.words.count) {
out.words[i] = lhs.words[i + offset] >> shift
}
if (i + offset + 1 < lhs.words.count) {
out.words[i] |= lhs.words[i + offset + 1] << (lhs.N - shift)
}
}
out.clearUnusedBits()
return out
}이 코드를 한 줄씩 살펴보자. 먼저 이 부분부터 시작한다:
for i in 0..<lhs.words.count {이 코드는 결과의 각 워드를 순회하며 올바른 비트를 할당한다는 전략을 보여준다.
루프 안에 있는 두 개의 if 문은 소스 숫자의 한 위치에서 비트를 가져오고, 두 번째 위치에서 비트를 가져와 비트 OR 연산을 수행한다. 여기서 핵심은 결과의 한 워드에 해당하는 비트가 입력에서 최대 두 개의 소스 워드에서 온다는 점이다. 따라서 남은 문제는 어떤 워드에서 비트를 가져올지 계산하는 것이다. 이를 위해 다음 두 값을 사용한다:
let offset = numBitsRight / lhs.N
let shift = numBitsRight % lhs.Noffset은 소스 워드에서 몇 단어 떨어진 위치에서 비트를 가져올지 나타낸다. shift는 해당 워드 내에서 몇 비트를 시프트할지 결정한다. 두 값 모두 워드 크기 lhs.N을 사용해 계산한다.
마지막으로 입력의 범위를 벗어나지 않도록 보호하는 코드가 있다. 다음 두 if 조건이 이를 담당한다:
if (i + offset < lhs.words.count) {그리고
if (i + offset + 1 < lhs.words.count) {예제를 통해 이해해 보자. 워드 길이가 8비트로 줄어들었다고 가정하고, 다음 숫자를 10비트 오른쪽으로 시프트한다고 해보자:
01000010 11000000 00011100 >> 10
숫자를 워드 단위로 나눠 표시했다. for 루프는 가장 낮은 유효 워드부터 가장 높은 유효 워드까지 순회한다. 따라서 인덱스 0에서는 가장 낮은 유효 워드를 구성할 비트를 찾아야 한다. offset과 shift 값을 계산해 보자:
offset = 10 / 8 = 1 (정수 나눗셈임을 기억하자)
shift = 10 % 8 = 2
offset이 1인 워드에서 비트를 가져온다:
11000000 >> 2 = 00110000
그리고 한 워드 더 떨어진 위치에서 나머지 비트를 가져온다:
01000010 << (8 - 2) = 10000000
이 두 값을 비트 OR 연산하면 가장 낮은 유효 워드가 완성된다:
00110000
10000000
-------- OR
10110000
두 번째 낮은 유효 워드에 대해 같은 과정을 반복하면 다음 값을 얻는다:
00010000
마지막 워드는 숫자의 끝을 벗어나므로 모든 비트가 0이 된다. 최종 결과는 다음과 같다:
00000000 00010000 10110000
Swift Algorithm Club의 Matthijs Hollemans가 작성