算法练习-BitMap整数算法

摘要

核心思想：使用 bits 来存储信息。

一个整型数字，在 32 位系统上，需要占用 4 Bytes，即 32 bits。

若以数字作为 index，在 bit 上存储信息，则可以大大节省空间。

应用场景

在内存空间不足情况，比如海量数据，解决以下问题：

1. 判断数组 arr 中是否存在某个数 n？

   遍历 arr 将数字对应的 bit 设置为 true，判断 num 对应的 bit 是否为 true 即可。

2. 数组 arr 中是否存在重复数？

   遍历 arr 将数字对应的 bit 设置为 true，若遇到已为 true 的 bit，说明存在重复数。

3. 对不重复的数组 arr 进行排序？

   遍历 arr 将数字对应的 bit 设置为 true，最后按顺序将 bit 为 true 的 index 打印出来即可。

4. 找出不重复的数？

   可借助 2 个 bit 来实现，出现一次为 01，出现第二次为 10，最后只把 01 的那些数打印出来即可。

代码

Swift 系统库没有 BitSet 类型，以下代码引用了 Bit Set · Swift Algorithm。

fileprivate struct BitSet {
    private(set) public var size: Int

    private let N = 64 // 这里是在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)
    }
    /// 将 index 计算出来
    private func indexOf(_ i: Int) -> (Int, Word) {
        precondition(i >= 0)
        precondition(i < size)
        let o = i / N
        let m = Word(i - o*N) // 其实就是 i % N
        return (o, 1 << m)
    }
    
    public mutating func set(_ i: Int) {
        let (j, m) = indexOf(i)
        words[j] |= m // 会将 j 位设置为 1
    }
    
    public mutating func clear(_ i: Int) {
        let (j, m) = indexOf(i)
        words[j] &= ~m // 会将所有位设置为 0
    }
    
    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) } }
    }

    /// 翻转 1->0, 0->1
    public mutating func flip(_ i: Int) -> Bool {
        let (j, m) = indexOf(i)
        words[j] ^= m
        return (words[j] & m) != 0
    }
}
复制代码

小结

BitMap 核心思想是使用 bit 来保存简单信息，比如说是否存在。

感谢

理解 BitMap 算法的原理 – 云 + 社区 – 腾讯云

Bit Set · Swift Algorithm