Swift: Bit type with Generics

Note to myself: Some informations here may be outdated due to lated changes in Swift language.

It might be surprising that High Level language like Swift have dedicated Bit type. It’s enum actually. Integer actually.

enum Bit : Int, RandomAccessIndexType, Reflectable, IntegerArithmeticType {
    case Zero
    case One
    (...)
}

If I ever think about memory effecienty in Swift, Bit is not something that will reduce memory usage. To represent 1 bit it uses 32-bit (4 bytes) of memory… so… who cares right? right.

Bit as enum is kind of integer while I would see it rather as kind of Boolean value (true/false is so natural state for bit right?) and here surprise: Boolean is represented as single byte: 1 byte < 4 bytes - I don’t really get design decision behind Int vs Boolean for single Bit.

Bit as a base of everything is quite extensive actually. Aside from implementation of obvious protocols like BitwiseOperationsType (inherited from Int actually) I see IntegerArithmeticType (what?).

Ok, I give it a try. I should start adding some bits to each other. Below example result in Bit.One as expected:

Bit.addWithOverflow(Bit.One, Bit.Zero)

adding / subtracting / etc. two bits together cause crash (what?) It’s overflow (kinda because 4 bytes) but… hey, shouldn’t crash right ?

Bit.addWithOverflow(Bit.One, Bit.One)

looks like all IntegerArithmeticType functions crash when it comes to overflow.

and now the icing on the cake

let result = Bit.One + Bit.One // fatal error:

error: unexpectedly found nil while unwrapping an Optional value. what? so now it’s Boolean kinda type but with false represented by Integer represented by nil somewhere? Give me a break.

Subtracting is not even obvious to do (but hey, there is IntegerArithmeticType protocol implemented, so what the deal?)

let result = Bit.One - Bit.Zero // error

Ambiguous use of operator. what? ok ok, I know that if I specify that result is type of Bit then it is working but hey.

Generics

I’m into bytes with my CryptoSwift project. Sometimes I need some generic function, and most of the times I fail when it comes to bitwise operations with generic type. My Holy Graal is to write generic function that is generic for all kinds of Integer type (UInt, Int, Int64, UInt32, Int8, etc) - seems impossible.

But look at this example of generic function

func integerFromBitsArray<T: UnsignedIntegerType>(bits: [Bit]) -> T
{
    var bitPattern:T = 0
    for (idx,b) in enumerate(bits) {
        if (b == Bit.One) {
            let bit = T.from(UIntMax(1) << UIntMax(idx))
            bitPattern = bitPattern | bit
        }
    }
    return bitPattern
}

the 6th line is interesting one: do “shift to left” operation on UIntMax values but first cast to UIntMax, then do the operations. This line used to looked like this:

let bit = (UInt(1) << UInt(idx)) as T

and this crashed in runtime sometimes due to possible overflow.

Moreover it looks like this because “<<” operator can’t be used with Generic type. It’s not defined this way. Actually shifting operator is not defined for generic types at all, so I have to do some more work to make it happened. Like this (uhm, have to define operator for types, blah!)

func <<<T:SignedIntegerType>(lhs: T, rhs: Int) -> Int {
    let a = lhs as Int
    let b = rhs
    return a << b
}

func <<<T:UnsignedIntegerType>(lhs: T, rhs: Int) -> UInt {
    let a = lhs as UInt
    let b = rhs
    return a << b
}

It allows me to do things like this (do shift with generic integer type)

var bit = T.from(IntMax(1 << bitIdx))
if ((value & bit) == bit) {
    shiftedValue = shiftedValue | T(bit << shiftCount)
}

(note: easy to create infinite loop here but it’s still better than nothing).

In general I must say…. wish there would be simply generic type Integer with subclassess, rather than separate types, which lead to enormous copy&paste programming.

Cover image - Street Art in East Village, New York City

PS. Some code samples can be found in CryptoSwift project.

PS2. Check out another posts about Integers