BitArray and BitSet API Review
Hey everyone! This is an overview of the API for the BitArray and BitSet data structures for the Swift Collections package. This project was done as a GSoC (Google Summer of Code) project for which you can find the original Swift Forums post here. This is the resulting API of the project. Please have a look! I'll appreciate any feedback you have!
Introduction
The BitArrayModule contains two data structures in its initial release, the BitArray and the BitSet, that allow for boolean values to be stored using less memory while also allowing for certain faster operations.
Motivation
Since a Bool has two values (true and false) in its domain, it only needs one bit of memory to represent its value. However, as a variable cannot be stored in a space smaller than one byte in memory, a Bool ends up using 8 times more memory than it would need. For a single value, this is hardly an issue, but for a larger Array<Bool>, this makes room for memory optimization. Additionally, if Bools were stored as bits, this could result in faster operations like that of bitwise AND, as chunks of values could likely be manipulated at once instead of iterating and operating over every single one.
Hence, creating a data structure that makes more efficient use of memory could also result in optimized performance.
Proposed Solution
As it isn't exactly feasible to create a variable that gets stored into a bit, the primary solution would be to have the Bools represented as the bits of an unsigned integer in a data structure called a BitArray
For example, the number 182 in binary is 10110110. Each 1 and 0 in the binary representation can represent a true and false value respectively. This allows us to store the values into an Array<UInt> as opposed to an Array<Bool>, making use of all of the bits, requiring up to 8 times less memory, but whose API would function much like an Array<BooL>.
Additionally, since every element in the storage is technically holding 8 or more boolean values, performance on common operations such as bitwise AND are much faster, as multiple boolean values can be manipulated by manipulating a single integer value in the array.
Such a data structure would also be a great storage solution to the Set<Int> version of a BitArray, whose integer values are to represent the indices of the true values in an Array<Bool>, called a BitSet. This set representation utilizing the BitArray would allow for the memory and speed optimization, but with an API functioning as a Set<Int>.
let bitArray: BitArray = [true, true, false, true, true] // a BitArray implementation that functions like an Array<Bool>
let bitSet: BitSet = [0, 1, 3, 4] // an equivalent set version of the BitArray, functioning as a Set<Int>
Detailed Design
BitArray
The BitArray mimics the API of an Array<Bool>, but maintains the Bools within the bits of an unsigned integer with its own unique bitwise operations.
var bitArray: BitArray = [true, false, true, false] // stored little-endian within an integer as 00000101, or 5
let secondBitArray: BitArray = [true, false, false, false]
// works much like an Array<Bool>
bitArray.removeLast()
bitArray.reversed()
let isEqual: Bool = (bitArray == secondBitArray) // false
bitArray.append(isEqual)
print(Array(bitArray)) // prints "[true, false, true, false, false]"
// also has its own unique bitwise operations
bitArray.formBitwiseAnd(secondBitArray)
bitArray ^= secondBitArray
let invertedBitArray = ~bitArray
Definition
struct BitArray: ExpressibleByArrayLiteral, RandomAccessCollection, MutableCollection, Equatable, Codable {
subscript(position: Int) -> Bool
}
BitArray-specific initializer APIs
BitArray, like an Array<Bool>, is a RandomAccessCollection with integer indices. However, BitArray does not conform to RangeReplaceableCollection because there didn't seem to be any use cases. However, some relevant parts of RangeReplaceableCollection were implemented without conforming.
/// Creates a new collection containing the specified number of a single, repeated `Bool`
///
/// The following example creates a BitArray initialized with 5 true values
///
/// let fiveTrues = BitArray(repeating: true, count: 5)
/// print(fiveTrues)
/// // Prints "BitArray(storage: [31], excess: 5)"
/// print(Array(fiveTrues))
/// // Prints "[true, true, true, true, true]"
///
/// - Parameters:
/// - repeatedValue: The `Bool` to repeat.
/// - count: The number of times to repeat the value passed in the
/// `repeating` parameter. `count` must be zero or greater.
public init(repeating repeatedValue: Bool, count: Int)
It also has an initializer that initializes from the BitSet
/// Creates a new BitArray using a BitSet, where the indices in the BitSet become the true values in the BitArray. The resulting BitArray often contains many padded false values at the end from empty bits that fill up the word
///
/// The following example creates a BitArray initialized by a BitSet
/// let bitSet: BitSet = [0, 1, 3, 5]
/// let bitArray = BitArray(bitSet)
/// print(bitArray)
/// // Prints "BitArray(storage: [43], excess: 0)"
/// print(Array(bitArray))
/// // Prints "[true, true, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]"
///
/// - Parameters:
/// - bitSet: An initialized BitSet
public init(_ bitSet: BitSet)
BitArray bitwise Operation APIs
The BitArray offers bitwise operation methods, both mutating and non-mutating, and both in the form of overloaded operators and function calls.
Bitwise OR operation
The bitwise or operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.
/// mutates self by setting the value in each index to true if either self or the passed in BitArray -- or both -- have a true value in that respective index.
///
/// The following example mutates a BitArray to be OR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseOr(secondBitArray)
/// print(Array(bitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseOr(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- or both -- have a true value in that respective index.
///
/// The following example mutates the lhs to be OR'd with the rhs
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray |= secondBitArray
/// print(Array(bitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func |= (lhs: inout BitArray, rhs: BitArray)
/// creates and returns a new BitArray by setting the value in each index of the new BitArray to true if either self or the passed in BitArray -- or both -- have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the OR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseOr(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the XOR'd result of `self` and `other`
func bitwiseOr(_ other: BitArray) -> BitArray
/// overloaded operator that creates and returns a new BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- or both -- have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the OR'd result of the lhs and rhs
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray | secondBitArray
/// print(Array(newBitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the XOR'd result of the lhs and rhs
static func | (lhs: BitArray, rhs: BitArray) -> BitArray
Bitwise AND operation
The bitwise AND operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.
/// mutates self by setting the value in each index to true if both self and the passed in BitArray have a true value in that respective index.
///
/// The following example mutates a BitArray to be AND'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseAnd(secondBitArray)
/// print(Array(bitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseAnd(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if both the lhs BitArray and the rhs BitArray have a true value in that respective index.
///
/// The following example mutates the lhs to be AND'd with the rhs
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray &= secondBitArray
/// print(Array(bitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func &= (lhs: inout BitArray, rhs: BitArray)
/// creates and returns a new BitArray by setting the value in each index of the new BitArray to true if both self and the passed in BitArray have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the AND'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseAnd(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the AND'd result of `self` and `other`
func bitwiseAnd(_ other: BitArray) -> BitArray
/// overloaded operator that creates and returns a new BitArray by setting the value in each index of the new BitArray to true if both the lhs BitArray and the rhs BitArray have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the AND'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray & secondBitArray
/// print(Array(newBitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the AND'd result of the lhs and rhs
static func & (lhs: BitArray, rhs: BitArray) -> BitArray
Bitwise XOR operation
The bitwise xor operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.
/// mutates self by setting the value in each index to true if either self or the passed in BitArray -- but not both -- have a true value in that respective index.
///
/// The following example mutates self to be XOR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseXor(secondBitArray)
/// print(Array(bitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseXor(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- but not both -- have a true value in that respective index.
///
/// The following example mutates a BitArray to be XOR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray ^= secondBitArray
/// print(Array(bitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func ^= (lhs: inout BitArray, rhs: BitArray)
/// creates a new BitArray by setting the value in each index of the new BitArray to true if either self or the passed in BitArray -- but not both -- have a true value in that respective index.
///
/// The following example creates a new a BitArray that is the XOR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseOr(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the XOR'd result of `self` and `other`
func bitwiseXor(_ other: BitArray) -> BitArray
/// creates a new BitArray by setting the value in each index of the new BitArray to true if either lhs BitArray or the rhs BitArray -- but not both -- have a true value in that respective index.
///
/// The following example creates a new a BitArray that is the XOR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray ^ secondBitArray
/// print(Array(newBitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the XOR'd result of the lhs and rhs
static func ^ (lhs: BitArray, rhs: BitArray) -> BitArray
Bitwise NOT operation
The bitwise not operation is non-mutating and can be done with a function call or by using an overloaded operator.
/// creates a new BitArray by setting each value in the new BitArray to the opposite value of that in self
///
/// The following example creates a new a BitArray that is the inverse of self
/// let bitArray: BitArray = [true, false, true, false]
/// let newBitArray = bitArray.bitwiseNot()
/// print(Array(newBitArray))
/// Prints "[false, true, false, true]"
///
/// - Returns: The BitArray that contains the inverse or opposite values of that in self
func bitwiseNot() -> BitArray
/// The bitwise NOT operator (`~`) is a prefix operator that returns a value in which all the Bools of its argument are flipped
///
/// The following example creates a new a BitArray to be NOT'd with another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let newBitArray = ~bitArray
/// print(Array(newBitArray))
/// Prints "[false, true, false, true]"
///
/// - Returns: The `BitArray` that contains the inverse or opposite values of that in `self`
static prefix func ~ (_ bitArray: BitArray) -> BitArray
BitArray-specific function APIs
There are two functions that RangeReplaceableCollections have that BitArray has as well, even though it does not conform to the RangeReplaceableCollection protocol.
They are the removeFirst(...) and removeLast(...) functions that remove a range of values.
/// Removes the first several values in the beginning of the BitArray
/// self must not be empty
///
/// The following example removes the first 3 elements of a BitArray
/// var bitArray: BitArray = [true, false, true, false, true]
/// bitArray.removeFirst(3)
/// print(Array(bitArray))
/// Prints "[false, true]"
///
/// - Parameters:
/// - k: an integer that represents the number of values desired to be removed from the beginning.
///`k` must be a positive number, and less than the `count` value of `self`
mutating func removeFirst(_ k: Int)
/// Removes the last several values in the end of the BitArray
///
/// The following example removes the last 3 elements of a BitArray
/// var bitArray: BitArray = [true, false, true, false, false, true]
/// bitArray.removeLast(3)
/// print(Array(bitArray))
/// Prints "[true, false, true]"
///
/// - Parameters:
/// - k: an integer that represents the number of values desired to be removed from the beginning.
///`k` must be a positive number, and less than the `count` value of self
mutating func removeLast(_ k: Int)
Additionally, there are two functions that indicate where the first and last true values are located in the BitArray
/// Returns the index of the first true value in the BitArray.
/// If there are no true values in the BitArray, the function returns nil
///
/// Examples:
/// let bitArray: BitArray = [false, true, false, true]
/// let firstTrue: Int? = bitArray.firstTrue()
/// print(firstTrue)
/// Prints "2"
///
/// let allFalseBitArray: BitArray = [false, false, false]
/// let firstTrue: Int? = allFalseBitArray.firstTrue()
/// print(firstTrue)
/// Prints "nil"
///
/// - Returns: An optional integer value of the index where the first true was found.
/// If there are no true values in the BitArray, the function returns `nil`
func firstTrue() -> Int?
/// Returns the index of the last true value in the BitArray.
/// If there are no true values in the BitArray, the function returns nil
///
/// Examples:
/// let bitArray: BitArray = [false, true, false, true]
/// let lastTrue: Int? = bitArray.lastTrue()
/// print(lastTrue)
/// Prints "2"
///
/// let allFalseBitArray: BitArray = [false, false, false]
/// let lastTrue: Int? = allFalseBitArray.lastTrue()
/// print(lastTrue)
/// Prints "nil"
///
/// - Returns: An optional integer value of the index where the last true was found
/// If there are no true values in the BitArray, the function returns `nil`
func lastTrue() -> Int?
BitSet
BitSet is like BitArray, except a true value in its underlying storage represents an integer at the respective offset (a false value represents the absence of an integer at the respective offset). In fact, its storage is a BitArray. The API, however, works much like a Set<Int>, although BitSet does not actually conform to any Set<Int> protocols.
var bitSet: BitSet= [0, 5, 8, 6]
// Some set operations that work on BitSet
bitSet.formUnion(BitSet([2, 4, 6]))
bitSet.insert(3)
Definition
struct BitSet: ExpressibleByArrayLiteral, BidirectionalCollection, {
struct Index: Comparable, Hashable {...}
subscript(position: Index) -> Int
}
BitSet has an opaque (non-integer) index. Advancing the index forward (or backward) is O(n) because BitSet searches the underlying storage for the next (or previous) true bit.
BitSet's Set-Like APIs
Although BitSet doesn't conform to SetAlgebra, it makes use of many of the same functions. BitSet doesn't directly conform mainly because there are some unnecessary features and functions that come with SetAlgebra that BitSet does better off without.
Insert
/// Inserts a new member into the set
/// The following examples insert a 2 into a set that already has a 2 and a set that doesn't, respectively
/// var bitSetWithTwo: BitSet = [0, 2, 4, 5]
/// var didInsert: Bool = bitSetWithTwo.insert(2)
/// print(didInsert)
/// // Prints "false"
/// print(Array(bitSetWithTwo))
/// // Prints "[0, 2, 4, 5]"
///
/// var bitSetWithoutTwo: BitSet = [0, 3, 4, 6]
/// didInsert = bitSetWithoutTwo.insert(2)
/// print(didInsert)
/// // Prints "true"
/// print(Array(bitSetWithoutTwo))
/// // Prints "[0, 2, 3, 4, 6]"
///
/// - Parameter newMember: An element to insert into the set
/// - Returns: `true` if `newMember` was not contained in the
/// set. If an element equal to `newMember` was already contained in the
/// set, the method returns `false`. Returned value is discarded without giving a warning if unused
@discardableResult
mutating func insert(_ newMember: Int) -> Bool
Remove
/// Removes a member from the set
/// The following examples remove a 2 from a set that has a 2 and a set that doesn't, respectively
/// var bitSetWithTwo: BitSet = [0, 2, 4, 5]
/// var didRemove: Bool = bitSetWithTwo.remove(2)
/// print(didRemove)
/// // Prints "true"
/// print(Array(bitSetWithTwo))
/// // Prints "[0, 4, 5]"
///
/// var bitSetWithoutTwo: BitSet = [0, 3, 4, 6]
/// didRemove = bitSetWithoutTwo.remove(2)
/// print(didRemove)
/// // Prints "false"
/// print(Array(bitSetWithoutTwo))
/// // Prints "[0, 3, 4, 6]"
///
/// - Parameter member: An element to remove from the set.
/// - Returns: `true` if `member` was contained in the
/// set. If an element equal to `member` was not already contained in the
/// set, the method returns `false`. Returned value is discarded without giving a warning if unused
@discardableResult
mutating func remove(_ member: Int) -> Bool
Contains
/// Checks whether the set contains a value or not
///
/// Example:
/// let bitSet: BitSet = [0, 2, 5, 6, 7]
/// let doesContain: Bool = bitSet.contains(0)
/// print(doesContain) // prints "true"
/// doesContain = bitSet.contains(8)
/// print(doesContain) // prints "false"
///
/// - Parameter member: An element to look for in the set.
/// - Returns: `true` if `member` exists in the set; otherwise returns `false`.
func contains(_ member: Int) -> Bool
Union
/// mutates self to be the resulting union of itself and another set
/// The union is the set of values that exist in either or both sets
///
/// The following example takes a set and transforms it into the union of itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formUnion(secondBitSet)
/// print(Array(firstBitSet)) // prints "[0, 2, 3, 4, 5, 6]"
///
/// - Parameter other: Another BitSet. `other` must be finite
mutating func formUnion(_ other: BitSet)
/// creates a new BitSet that is the resulting union of itself and another set
/// The union is the set of values that exist in either or both sets
///
/// The following example creates a set that is the union of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.union(secondBitSet)
/// print(Array(resultSet)) // prints "[0, 2, 3, 4, 5, 6]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are in this set or `other` or both.
func union(_ other: BitSet) -> BitSet
Intersection
/// mutates self to be the resulting intersection of itself and another set
/// The intersection is the set of values that exist both sets
///
/// The following example takes a set and transforms it into the intersection of itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formIntersection(secondBitSet)
/// print(Array(firstBitSet)) // prints "[2, 5]"
///
/// - Parameter other: Another BitSet
mutating func formIntersection(_ other: BitSet)
/// creates a new BitSet that is the resulting intersection of itself and another set
/// The intersection is the set of values that exist both sets
///
/// The following example creates a set that is the union of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.intersection(secondBitSet)
/// print(Array(resultSet)) // prints "[2, 5]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are both in this set and `other`.
func intersection(_ other: BitSet) -> BitSet
Symmetric Difference
/// mutates self to be the resulting symmetric difference of itself and another set
/// The symmetric difference is the set of values that exist one set or the other, but not both
///
/// The following example takes a set and mutates it into the symmetric difference between itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formSymmetricDifference(secondBitSet)
/// print(Array(firstBitSet)) // prints "[0, 3, 4, 6]"
///
/// - Parameter other: Another BitSet
mutating func formSymmetricDifference(_ other: BitSet)
/// creates a new BitSet that is the resulting symmetric difference of itself and another set
/// The symmetric difference is the set of values that exist one set or the other, but not both
///
/// The following example creates a set that is the symmetric difference of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.symmetricDifference(secondBitSet)
/// print(Array(resultSet)) // prints "[0, 3, 4, 6]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are in either this set or the other set, but not both
func symmetricDifference(_ other: BitSet) -> BitSet
BitSet initializer from BitArray
A BitSet can conveniently be initialized from a BitArray. The BitArray simply becomes it's storage. If there are excessive false values at the end of the BitArray storage, they are removed as BitSet does not keep track of false values.
// Initializes a BitSet from a BitArray
init(_ bitArray: BitArray)
Considerations
Computed startIndex Property
The startIndex for the BitArray is traditionally a stored property of constant time. However, for the BitSet, as it needs to traverse and find the first true value in its BitArray storage type, is a computed property. Although this might not be ideal, when benchmarked, the operation is hardly slow at all. Consider this linear view of a benchmark comparing the BitSet's startIndex lookup compared to that of the Set<Int>:
Their runtimes hardly differ, and oftentimes the BitSet performs better than the Set<Int>. There may be a few worse-case scenarios where the BitSet's startIndex lookup is worse, but I felt it wasn't significant enough to go for the more complicated approach.
Lack of Conformance to RangeReplaceableCollection
Even though Array<Bool> conforms to RangeReplaceableCollection, I choose not to conform to it for BitArray. This is because use cases for the replaceSubrange(...) method seems to be a rarity (and actually couldn't think of any). Additionally, such a method would likely be costly in performance; as the conformance takes the replaceSubrange(...) implementation and utilizes it for all RangeReplaceableCollection methods, it could potentially make several other methods unnecessarily slow as well. Hence, as a conformance to RangeReplaceableCollection requires an implementation of replaceSubrange(...), the conformance seemed unnecessary. Instead, I added implementations of certain methods that might be useful.
Lack of Conformance to SetAlgebra
As BitSet is essentially a Set<Int> in its API. Therefore, not conforming to SetAlgebra is naturally an interesting choice. Instead, useful methods from SetAlbegra were implemented.
For example, for the insert(...) method:
// SetAlgebra method
@discardableResult
mutating func insert( _ newMember: __owned Element) -> (inserted: Bool, memberAfterInsert: Element)
// BitSet method
@discardableResult
mutating func insert(_ newMember: Int) -> Bool
The insert method in SetAlgebra returns virtually useless information for a BitSet, resulting in the method doing more work than necessary.
Additionally, SetAlgebra requires an implementation of the update(...) method, that, not only returns more information than necessary, but has practically the same purpose as insert(...), making it practically useless, as well as confusing for an API.
mutating func update(with newMember: __owned Element) -> Element?
Hence, instead of implementing all of these practically useless or overworking methods, some useful methods were cherry picked from SetAlgebra and implemented manually without the conformance.
Some Neat Performance Benchmarks
As explained in the Proposed Solution section, a primary objective in implementing these data structures was to speed up typical operations (bitwise operations for the BitArray and set operations for the BitSet). As Array<Bool> does not have any bitwise operations, having them for BitArray is already a plus, and there isn't much to compare it to within the realm of Swift. However, for the BitSet, it is possible to test how much faster the BitSet set operations are compared to the Set<Int>. I was very happy to see the performance charts of the BitSet operations compared to that of Set<Int>, and am very excited to share them with you all as well! Check it out!
BitSet Union VS Set<Int> Union
BitSet Intersection VS Set<Int> Intersection
BitSet Symmetric Difference VS Set<Int> Symmetric Difference
Very pleasing to the eye if you ask me 
End Remarks
Thank you for reviewing this API! Please feel free to leave feedback and suggestions! I;m very grateful for the great time I had with the Swift Standard Library on my GSoC project!
A special thanks to my primary mentor @David_Smith, as well as my other great mentors @lorentey and @kylemacomber. Also a special thanks to some Twitter friends who were willing to look over my draft for errors @ ziti and @ nasimuddin01
However, isn't