Abstract

Core idea: Use bits to store information.

An integer number that takes up 4 Bytes, or 32 bits, on a 32-bit system.

Storing information on a bit with a number as index can save a lot of space.

Application scenarios

In the case of insufficient memory space, such as massive data, solve the following problems:

  1. Is there some number n in arr?

    Arr = true; arR = true; arR = true; arR = true;

  2. Is there a repeat number in the array ARR?

    Traversing arR sets the corresponding bit of the number to true. If a bit that has been set to true is encountered, the number of duplicates exists.

  3. Sort the non-repeating array arr?

    Iterate through the ARR to set the corresponding bit of the number to true, and finally print the index with the bit of true in sequence.

  4. Find the numbers that don’t repeat, okay?

    This can be achieved with the help of two bits, one occurrence is 01, the second occurrence is 10, and finally just print out those numbers of 01.

code

Swift system library has no BitSet type. The following code references BitSet · Swift Algorithm.

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

    private let N = 64 // This is the case on a 64-bit system
    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)
    }
    /// calculate 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 // The j bit is set to 1
    }
    
    public mutating func clear(_ i: Int) {
        let (j, m) = indexOf(i)
        words[j] & = ~m // All bits are set to 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) } }
    }

    /// flip 1->0, 0->1
    public mutating func flip(_ i: Int) -> Bool {
        let (j, m) = indexOf(i)
        words[j] ^ = m
        return (words[j] & m) ! = 0}}Copy the code

summary

The idea behind bitmaps is to use bits to store simple information, such as whether they exist or not.

Thank you

Understand the principle of BitMap algorithm – cloud + community – Tencent Cloud

Bit Set · Swift Algorithm