本帖最后由 Ding 于 2016-11-4 13:37 编辑

可以先看看《探索之旅:位运算》,用里边那个小问题热热身。


数据结构:BitSet

数据结构:BitSet - 敏捷大拇指 - 数据结构:BitSet




位集(bit set)

位集是固定长度的序列,用来存储n个位(bit),也叫bit array、bit vector。

众猿媛所周知,我们用一个Bool变量存储true或false。但,如果要存储10000个true或false呢?

你可来个10000长度的数组,但也可考虑深入底层用10000个位代替。在空间上那将紧凑得多,10000位的空间相当于64位CPU上160个Int所占的空。

在位的层面上做菜有些棘手, 所以我们定义 BitSet 来封装那些脏活儿。

开始吧:

我们的位集是对数组的简单包装。该数组并不是存储一个个的位,而是大得多的整数,我们称“字”("word"),如果觉得突兀,你可以先回顾下字节、计算机的字长等概念。BitSet的主要工作就是把位们映射到正确的字上。
[Swift] 纯文本查看 复制代码
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
        
        // Round up the count to the next multiple of 64.
        let n = (size + (N-1)) / N
        words = [Word](repeating: 0, count: n)
    }
}
N就是字的大小,我们定义一个字的大小为64位,这样我们就可以在数组里存储64位无符号整型(UInt64)了。(也可以改成32位的字,这很方便。)

如果你写:
[Swift] 纯文本查看 复制代码
var bits = BitSet(size: 140)

将会生成一个3个字的数组。每个字有64个位,所以3个字可以容纳192个位。我们仅用140个,这样浪费了一丢丢空间。(当然,我们永远不会用半个字或0.8个字这样的空间。)

注:数组里的第一个字是最重要的,这些字以小端的顺序存在数组里。

定位这些位

BitSet的大多数操作都需要某个位的位置作参数,所以提取一个方法来确定某个位在哪个字里及在该字的那个位置会很有用。
[Swift] 纯文本查看 复制代码
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()函数返回了位所在的字在数组中的索引,以及位在该字里的伪值(mask)。字的索引简单,关键是这个伪值。用例子来说明。

例如, indexOf(2) 返回元组 (0, 4) 因为第2个位在第一个字里(索引是0)。伪值是4,怎么回事? 让我们从二进制的角度看看:
[Swift] 纯文本查看 复制代码
0010000000000000000000000000000000000000000000000000000000000000

1就在这个字的第2位(从左往右,0,1,2,...)
除了字是小端顺序,每个字里的这些位也是,所以伪值反过来看,就是
[Swift] 纯文本查看 复制代码
0000000000000000000000000000000000000000000000000000000000000100

正是十进制的4。

另一个例子:indexOf(127),返回元组(1, 9223372036854775808)。它在第二个字(索引1),二进制的伪值是
[Swift] 纯文本查看 复制代码
0000000000000000000000000000000000000000000000000000000000000001

注意到伪值总是64位,因为我们每次都是在一个字里找数据的。

位的设置

现在我们已经知道怎么定位一个位,将某个位置为1就简单了:
[Swift] 纯文本查看 复制代码
public mutating func set(_ i: Int) {
    let (j, m) = indexOf(i)
    words[j] |= m
}

先找到i位所在字的索引和伪值,然后在那来个或运算,如果那一位是0,就变成1;如果已经设置了,还将是1。

将某个位设置成0同样简单:
[Swift] 纯文本查看 复制代码
public mutating func clear(_ i: Int) {
    let (j, m) = indexOf(i)
    words[j] &= ~m
}

不是或,这次我们用与操作位的伪值的反。这样,如果伪值是00100000...0, 它的反就是11011111...1,除了我们想置为0的那位,所有位都是1。再与一下,其他位都保留了,单单这个位成了0。

检查某一位是否是1我们同样可以用与运算,但这次不取反。
[Swift] 纯文本查看 复制代码
public func isSet(_ i: Int) -> Bool {
    let (j, m) = indexOf(i)
    return (words[j] & m) != 0
}


我们可以添加subscript函数让这些用起来更自然:
[Swift] 纯文本查看 复制代码
public subscript(i: Int) -> Bool {
    get { return isSet(i) }
    set { if newValue { set(i) } else { clear(i) } }
}

现在可以这样使用了:
[Swift] 纯文本查看 复制代码
var bits = BitSet(size: 140)
bits[2] = true
bits[99] = true
bits[128] = true
print(bits)

这会打印3个字,即140个位的BitSet用来存储的空间:
[Swift] 纯文本查看 复制代码
0010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000010000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000

对这些位还有一些有趣的操作。

下边这个会把0变成1,1变成0。flip()函数:
[Swift] 纯文本查看 复制代码
public mutating func flip(_ i: Int) -> Bool {
    let (j, m) = indexOf(i)
    words[j] ^= m
    return (words[j] & m) != 0
}

这里又用了一个位操作,异或。函数返回了该位的新值。

忽略没用上的位们

BitSet的许多方法都很容易实现。例如:clearAll(), 把所有的位置为0:
[Swift] 纯文本查看 复制代码
public mutating func clearAll() {
    for i in 0..<words.count {
        words = 0
    }
}

同样来个方法 setAll() 来将所有位置为 1。 不过,有个微妙的地方要处理。
[Swift] 纯文本查看 复制代码
public mutating func setAll() {
    for i in 0..<words.count {
        words = allOnes
    }
    clearUnusedBits()
}

首先,我们把数组里所有的字置为1,数组现在是:
[Swift] 纯文本查看 复制代码
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111

但,这个不对... 因为尾部有些位我们并没有用,它们需要置为0:
[Swift] 纯文本查看 复制代码
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111110000000000000000000000000000000000000000000000000000

只需要140个位而不是192个。事实是最后的那个字没有被用完,这意味着我们总是要特别对待最后这个字。

把这些空闲分子置为0就是工具方法clearUnusedBits()做的事。如果BitSet的大小(size)不能被N(这里是64)整除,就需要清理掉那些没有用上的位。如果不清理,两个不同大小的BitSet交互起来就会出问题(后边有例子)。

下边这个函数用了些高阶的位操作,须格外注意:
[Swift] 纯文本查看 复制代码
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
}

它做了什么,一步步来:

1) diff 指那些没有用上的位的个数。上边的例子里是52( 3*64 - 140 = 52)。

2) 创建一个除了最高位其余全是0的伪值,在例子里,应该是:
[Swift] 纯文本查看 复制代码
0000000000010000000000000000000000000000000000000000000000000000

3) 减去1使它变成:
[Swift] 纯文本查看 复制代码
1111111111100000000000000000000000000000000000000000000000000000

再把最高位的1加回来得到:
[Swift] 纯文本查看 复制代码
1111111111110000000000000000000000000000000000000000000000000000

现在有12个置为1的位了(140 - 2*64 = 12)。

4) 最后,用与操作,使得用得上的位保留,而没用上的那些位都是0。

把剩余分子置为0,对于两个大小不同的BitSet的交互很重要。为了说明这一点,我们看看两个BitSet:
[Swift] 纯文本查看 复制代码
10001111 size=4
00100011 size=8

第一个只用了前4位;第二个用了全部8位。第一个应该是指10000000,但我们先假装忘了清理后边的那些1。对这俩做按位或运算:
[Swift] 纯文本查看 复制代码
10001111
00100011
-------- OR
10101111

这个真错了,因为有两个1不该出现在这。正确的做法是:
[Swift] 纯文本查看 复制代码
10000000 //unused bits set to 0 first!
00100011
-------- OR
10100011


操作符函数|定义如下:
[Swift] 纯文本查看 复制代码
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 = lhs.words | rhs.words
    }
    return out
}

注意到我们或的是所有字而不是仅仅那些用了的位,这有点慢! 我们需要做点额外的工作,如果left-hand 这个位集 和 right-hand 这个位集有不一样多的位: 先用out变量记住两个里边较大的,然后以较小的位集的字的个数做上限遍历left-hand和right-hand。

例子:
[Swift] 纯文本查看 复制代码
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


与(&)、异或(^)、取反(~)函数的实现类似。

计数所有置为1的位

要数一下位集里的1有多少个,我们可以遍历整个数组,这是O(n)复杂度的操作。实际上有个更聪明的办法:
[Swift] 纯文本查看 复制代码
public var cardinality: Int {
    var count = 0
    for var x in words {
        while x != 0 {
            let y = x & ~(x - 1) // find lowest 1-bit
            x = x ^ y // and erase it
            ++count
        }
    }
    return count
}
当你写了 x & ~(x - 1), 将得到最前边的那个1被置为0的新值。比如x是这个值:
[Swift] 纯文本查看 复制代码
00101101

先减去1得到:
[Swift] 纯文本查看 复制代码
11001101

按位取反:
[Swift] 纯文本查看 复制代码
00110010

跟原来的值按位与:
[Swift] 纯文本查看 复制代码
00101101
00110010
-------- AND
00100000

它们唯一公有的是最前边(或者说最重要)的那个1。

再用这个值和原值按位异或:
[Swift] 纯文本查看 复制代码
00101101
00100000
-------- XOR
00001101

这就是原来的值,只是最前边一位1被擦除了。

重复去掉最前边的1,直到全部变成0。这个操作的时间复杂度是O(s),s就是x里含有的1的个数。



附上GitHub源码地址:BitSet.swift
原作者: Matthijs Hollemans