I wanted to write about bit-masks and bitwise operators for a while now as a reference for myself and to deepen my understanding of the topic. But I couldn’t finish it, because frankly it was just too boring.

I do a lot of Android programming at work recently and stumbled upon a class called SparseBooleanArray that was used in one tutorial to store selection states for items in a table. The documentation says it’s a more memory efficient way to store an array of boolean values than to use for example an ArrayList. And I thought I can make an interesting post by writing a similar thing in Swift using bit-masks.

Introduction

To store a Bool in Swift and in practically all other languages you have to allocate one byte, which is usually the least amount of memory you can request from the system. Which is unfortunately 8 times more than what you actually need to store a true/false value. This is no problem for single values but in a large collection of boolean values there is a real potential to save memory. The idea is now to store 8 consecutive boolean values in a single byte by setting single bits of it to 1 or 0 to represent the boolean value at this position.

First define a struct for the collection and give it a UInt8 array as its base storage.

struct SparseBooleanArray {  
    private var store: [UInt8] = []
    var count: Int { return store.count }
}

Insert values

Next define a method to set values on the collection. The problem with storing the boolean values in a bit-mask is that there is no way of specifying an undefined value, therefore there is no way to tell if a value at a given index was already initialized. To avoid this problem only appending and overwriting values is allowed. For this introduce a variable to keep track of the highest already initialized index and guard against accessing values outside this index.

struct SparseBooleanArray {  
    private var store: [UInt8] = []
    var count: Int { return store.count }
    private var highestIndex = -1

    mutating func set(_ value: Bool, at index: Int) {
        guard index - 1 <= highestIndex else {
            fatalError("Illegal index")
        }

        let byteIndex = index / 8
        let bitIndex = UInt8(index % 8)
        let mask = 1 << bitIndex

        highestIndex = max(index, highestIndex)

        // A new byte is needed to store further values
        if byteIndex == store.count {
            store.append(0x00)
        }

        if value {
            store[byteIndex] |= mask
        } else {
            store[byteIndex] &= ~mask
        }
    }
}

The interesting part here is the construction of mask and the used bitwise operators.
To set a new true value at a specific index construct a byte with just a 1 at this index and then perform a OR operation | to set the 1 but not lose any of the values already there.

  • Start with a 1 0000 0001
  • Shift it left to the given index e.g 3 1 << 3 := 0000 1000
  • Set the 1 to the existing byte using OR |
   0110 0010
OR 0000 1000  
------------
   0110 1010
        ^
Bit at index 3 is now set to 1  

To set a 0 at a given position inverse the previous., everywhere zeros except at our index and than use an AND operator & instead.

  • Start with a 1 0000 0001
  • Shift it left to the given index e.g. 3 1 << 3 := 0000 1000
  • Inverse the byte ~(1 << 3) := 1111 0111
  • Set the 0 to the existing byte using AND &
    0110 1010
AND 1111 0111  
-------------
    0110 0010
         ^
Bit at index 3 is now set to 0  

A good practice is to look if you can replace the inverse operator ~ with a XOR ^.

Getting values

Getting values is pretty straightforward now. First construct a mask like before with a single 1 at the given index. Then when combined with the AND operator & and the existing byte, the result is either non zero, when a 1 was set at the index or zero if no 1 was set at the index.

func get(_ index: Int) -> Bool {  
    guard index <= highestIndex else {
        fatalError("Illegal index")
    }

    let byteIndex = index / 8
    let bitIndex = UInt8(index % 8)
    let mask = 1 << bitIndex

    return (store[byteIndex] & mask) != 0
}

Conclusion

A little comparison between the memory usage of a normal boolean array and our SparseBooleanArray.

var sparseArray = SparseBooleanArray()  
var array: [Bool] = []

for i in 0..<100 {  
    sparseArray.set(true, at: i)
    array.append(true)
}

print("SparseBoolenArray uses \(MemoryLayout<UInt8>.size * sparseArray.count) Bytes of Memory")  
print("Array uses \(MemoryLayout<Bool>.size * array.count) Bytes of memory")

// >> SparseBooleanArray uses 13 Bytes of Memory
// >> Array uses 100 Bytes of Memory

Thinking about a followup post where I take the SparseBooleanArray implementation above and show how to make it conform to Swifts Collection protocol.