Swift Bit array to Bytes array (UInt8 array)

Question

I have array with bits:

var bits: [Bit]

and how could I convert it to bytes array:

var bytes: [UInt8]

For example I have 280 bits and I should have 35 UInt8 in bytes array. I can think of solution where I take 8bits and check if first is true, if second is true and so and sum the results and have value. This I would do for every 8bits in my bits array. But I think this would be bad solution (it would work but with unnecessary calculations). I think there could be faster solution with some shifting and so but I am really bad in this so I am looking for help. Thanks

Answer 1

A possible solution is to enumerate all bits in the array and for all "One" bits set the corresponding bit in the UInt8 array:

func bitsToBytes(bits: [Bit]) -> [UInt8] {
    let numBits = bits.count
    let numBytes = (numBits + 7)/8
    var bytes = [UInt8](count : numBytes, repeatedValue : 0)

    for (index, bit) in enumerate(bits) {
        if bit == .One {
            bytes[index / 8] += 1 << (7 - index % 8)
        }
    }

    return bytes
}

The main idea is that for a given index in the bit array, index / 8 is the corresponding index in the byte array, and index % 8 is the bit position in the byte. You can use index % 8 or 7 - index % 8 as shift amount, depending on the desired bit order.

Example:

// 0110 0100  0000 1001
let bits : [Bit] = [.Zero, .One, .One, .Zero,  .Zero, .One, .Zero, .Zero,  .Zero, .Zero, .Zero, .Zero,  .One, .Zero, .Zero, .One]
let bytes = bitsToBytes(bits)
println(bytes) // [100, 9]

Alternatively, you can "inline" the calculation for each group of 8 bits. You'll have to check which solution performs better in your case.

func bitsToBytes(bits: [Bit]) -> [UInt8] {
    let numBits = bits.count
    let numBytes = numBits/8
    var bytes = [UInt8](count : numBytes, repeatedValue : 0)
    for pos in 0 ..< numBytes {
        let val = 128 * bits[8 * pos].toIntMax() + 
            64 * bits[8 * pos + 1].toIntMax() +
            32 * bits[8 * pos + 2].toIntMax() +
            16 * bits[8 * pos + 3].toIntMax() +
            8 * bits[8 * pos + 4].toIntMax() +
            4 * bits[8 * pos + 5].toIntMax() +
            2 * bits[8 * pos + 6].toIntMax() +
            1 * bits[8 * pos + 7].toIntMax()
        bytes[pos] = UInt8(val)
    }
    return bytes
}

Here, for simplicity, if the number of bits is not a multiple of 8, any excess bits are ignored. The same code can also be written a bit "Swiftier" as

func bitsToBytes(bits: [Bit]) -> [UInt8] {
    return map(0 ..< bits.count/8) {
        pos in
        let val = 128 * bits[8 * pos].toIntMax() + 
            64 * bits[8 * pos + 1].toIntMax() +
            32 * bits[8 * pos + 2].toIntMax() +
            16 * bits[8 * pos + 3].toIntMax() +
            8 * bits[8 * pos + 4].toIntMax() +
            4 * bits[8 * pos + 5].toIntMax() +
            2 * bits[8 * pos + 6].toIntMax() +
            1 * bits[8 * pos + 7].toIntMax()
        return (UInt8(val))
    }
}

---

Benchmarks: Here is now a quick-and-dirty benchmarking app (code below), comparing the various solutions. It measures the time to convert 10,000 bit arrays of length 256. The tests were done on a MacBook Pro 2,3 GHz Intel Core i7, and the code compiled with the "Release" configuration.

Results with Swift 1.1/Xcode 6.2 (6C131e):

Martin1: 0.0460730195045471
Martin2: 0.0280380249023438
Martin3: 0.0374950170516968
Antonio: 5.85363000631332
Nate   : 4.86936402320862

Results with Swift 1.2/Xcode 6.3 (6D532l):

Martin1: 0.0228430032730103
Martin2: 0.00573796033859253
Martin3: 0.00732702016830444
Antonio: 0.515677988529205
Nate   : 0.634827971458435

Code:

protocol BitsToBytesConverter {
    var ident : String { get }
    func bitsToBytes(bits: [Bit]) -> [UInt8]
}

class MR1 : BitsToBytesConverter {

    let ident = "Martin1"
    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        let numBits = bits.count
        let numBytes = (numBits + 7)/8
        var bytes = [UInt8](count : numBytes, repeatedValue : 0)

        for (index, bit) in enumerate(bits) {
            if bit == .One {
                bytes[index / 8] += UInt8(1 << (7 - index % 8))
            }
        }

        return bytes
    }
}

class MR2 : BitsToBytesConverter {

    let ident = "Martin2"

    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        let numBits = bits.count
        let numBytes = numBits/8
        var bytes = [UInt8](count : numBytes, repeatedValue : 0)
        for pos in 0 ..< numBytes {
            let val = 128 * bits[8 * pos].toIntMax() + 
                64 * bits[8 * pos + 1].toIntMax() +
                32 * bits[8 * pos + 2].toIntMax() +
                16 * bits[8 * pos + 3].toIntMax() +
                8 * bits[8 * pos + 4].toIntMax() +
                4 * bits[8 * pos + 5].toIntMax() +
                2 * bits[8 * pos + 6].toIntMax() +
                1 * bits[8 * pos + 7].toIntMax()
            bytes[pos] = UInt8(val)
        }
        return bytes
    }
}

class MR3 : BitsToBytesConverter {

    let ident = "Martin3"

    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        return map(0 ..< bits.count/8) {
            pos in
            let val = 128 * bits[8 * pos].toIntMax() + 
                64 * bits[8 * pos + 1].toIntMax() +
                32 * bits[8 * pos + 2].toIntMax() +
                16 * bits[8 * pos + 3].toIntMax() +
                8 * bits[8 * pos + 4].toIntMax() +
                4 * bits[8 * pos + 5].toIntMax() +
                2 * bits[8 * pos + 6].toIntMax() +
                1 * bits[8 * pos + 7].toIntMax()
            return (UInt8(val))
        }
    }
}

class AB : BitsToBytesConverter {

    let ident = "Antonio"

    typealias IntegerType = UInt8

    func bitsToBytes(bits: [Bit]) -> [UInt8] {

        let initial = [IntegerType]()

        return reduce(enumerate(bits), initial) { array, element in
            // The size in bits of a UInt8
            let size = sizeof(IntegerType) * 8

            // Create a mutable copy of the array returned at the previous iteration
            var next = array

            // If it's the first iteration, or an iteration divisible by the size of UInt8, 
            // append a new element to the array
            if element.index % size == 0 {
                next.append(0x00)
            }

            // Shift all bits of the last element to the left
            next[next.count - 1] <<= 1

            // If the current bit is one, add 1 to the rightmost bit
            // Using a logical OR
            if element.element == .One {
                next[next.count - 1] |= 0x01
            }

            return next
        }
    }
}

class NC : BitsToBytesConverter {

    let ident = "Nate   "

    func group<T>(array: [T], byCount groupCount: Int) -> [Slice<T>] {
        // get a list of the start indices
        let startIndices = stride(from: 0, to: array.count, by: groupCount)
        // add `groupCount` to each to get the end indices
        let endIndices = lazy(startIndices).map { advance($0, groupCount, array.count) }

        // zip those together & map onto an array of slices of the input array
        return map(Zip2(startIndices, endIndices)) {
            array[$0.0 ..< $0.1]
        }
    }

    func bitsToByte(bits: Slice<Bit>) -> UInt8 {
        return bits.reduce(0) { accumulated, current in
            accumulated << 1 | (current == .One ? 1 : 0)
        }
    }

    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        return group(bits, byCount: 8).map(bitsToByte)
    }
}


let numBits = 256 // Bits per bit array
let numBitArrays = 10000 // Number of bit arrays

func randomBits() -> [Bit] {
    return map(0 ..< numBits) { _  in
        Bit(rawValue: Int(arc4random_uniform(2)))!
    }
}

func randomBitsArray() -> [[Bit]] {
    return map(0 ..< numBitArrays) { _ in
        randomBits()
    }
}

let bitsArray = randomBitsArray()

func test(conv : BitsToBytesConverter) {
    let x = conv.bitsToBytes([])
    let startTime = NSDate()
    for bits in bitsArray {
        let bytes = conv.bitsToBytes(bits)
    }
    let duration = -startTime.timeIntervalSinceNow
    println("\(conv.ident): \(duration)")
}

test(MR1())
test(MR2())
test(MR3())
test(AB())
test(NC())

Answer 2

That's a fun question. I look at this as two smaller problems: (1) how to split an array of Bit into an array of Bit arrays, where each smaller array is one byte's worth of bits, and (2) how to convert those smaller arrays into one byte each.

To solve the first, we can write a function that groups an array into slices of a particular size:

func group<T>(array: [T], byCount groupCount: Int) -> [Slice<T>] {
    // get a list of the start indices
    let startIndices = stride(from: 0, to: s.count, by: groupCount)
    // add `groupCount` to each to get the end indices
    let endIndices = lazy(startIndices).map { advance($0, groupCount, array.count) }

    // zip those together & map onto an array of slices of the input array
    return map(zip(startIndices, endIndices)) {
        array[$0.0 ..< $0.1]
    }
}

To solve the second, we can write a function that takes each Slice<Bit> returned from group(_:byCount:) and converts it into a UInt8. At each step it shifts the value left by one bit, then sets the ones bit if that element is .One:

func bitsToByte(bits: Slice<Bit>) -> UInt8 {
    return bits.reduce(0) { accumulated, current in
        accumulated << 1 | (current == .One ? 1 : 0)
    }
}

Finally, you can call each of these in turn, or combine them to get your result:

// 1111 1111  1000 0000  0000 0001  0101 0101
let bits : [Bit] = [.One, .One, .One, .One, .One, .One, .One, .One,
    .One, .Zero,  .Zero, .Zero, .Zero, .Zero, .Zero, .Zero,
    .Zero,  .Zero, .Zero, .Zero, .Zero, .Zero, .Zero, .One,
    .Zero, .One, .Zero, .One, .Zero, .One, .Zero, .One]
let bytes = group(bits, byCount: 8).map(bitsToByte)
// [255, 128, 1, 85]

Answer 3

If you prefer a functional approach, at the cost of a more expensive computation, then you could use reduce in combination with enumerate.

The latter, given a sequence of elements, creates a sequence of (index, element) tuples. We need the index to know the bit positions.

reduce instead is used to reduce an array of Bit into an array of UInt8

typealias IntegerType = UInt8

let initial = [IntegerType]()

let result = reduce(enumerate(bits), initial) { array, element in
    // The size in bits of a UInt8
    let size = sizeof(IntegerType) * 8

    // Create a mutable copy of the array returned at the previous iteration
    var next = array

    // If it's the first iteration, or an iteration divisible by the size of UInt8, 
    // append a new element to the array
    if element.index % size == 0 {
        next.append(0x00)
    }

    // Shift all bits of the last element to the left
    next[next.count - 1] <<= 1

    // If the current bit is one, add 1 to the rightmost bit
    // Using a logical OR
    if element.element == .One {
        next[next.count - 1] |= 0x01
    }

    return next
}

The returned result is an array of UInt8.

Update Forgot to mention that if you want to convert to a different integer type, just change the IntegerType alias.

Answer 4

Some cool code here @martin-r @antonio @nate-cook, but there also seems to be some correctness issues that I discovered while converting this code to Swift 3 for my use. Feature of this revised snippet:

• Xcode 8, Swift 3.0, as run in a Playground
• Includes validation capability (commented out)
• Has Bit enum to represent Bit type. (Bit type was removed from Swift 3)
• Although this is still has the timing instrumentation, I have not tried to really test the speeds of the different methods. Seems we need to ensure correct results first.
• Only Martin1 and Martin2 coded. Other methods left as exercise for reader ;).

Martin1: 0.112455010414124: hash 0
Martin2: 1.06640499830246: hash 0

Anyway, here is my code strongly based the work of others. Hope some find this useful.

import Foundation

enum Bit { case zero, one
    func asInt() -> Int {
        return (self == .one) ? 1 : 0
    }
}

protocol BitsToBytesConverter {
    var ident : String { get }
    func bitsToBytes(bits: [Bit]) -> [UInt8]
}

class MR1 : BitsToBytesConverter {

    let ident = "Martin1"

    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        assert(bits.count % 8 == 0, "Bit array size must be multiple of 8")

        let numBytes = 1 + (bits.count - 1) / 8
        var bytes = [UInt8](repeating: 0, count: numBytes)

        for (index, bit) in bits.enumerated() {
            if bit == .one {
                bytes[index / 8] += UInt8(1 << (7 - index % 8))
            }
        }
        return bytes
    }
}

class MR2 : BitsToBytesConverter {

    let ident = "Martin2"

    func bitsToBytes(bits: [Bit]) -> [UInt8] {
        assert(bits.count % 8 == 0, "Bit array size must be multiple of 8")

        let numBytes = 1 + (bits.count - 1) / 8

        var bytes = [UInt8](repeating : 0, count : numBytes)
        for pos in 0 ..< numBytes {
            let val = 128 * bits[8 * pos].asInt() +
                64 * bits[8 * pos + 1].asInt() +
                32 * bits[8 * pos + 2].asInt() +
                16 * bits[8 * pos + 3].asInt() +
                8 * bits[8 * pos + 4].asInt() +
                4 * bits[8 * pos + 5].asInt() +
                2 * bits[8 * pos + 6].asInt() +
                1 * bits[8 * pos + 7].asInt()
            bytes[pos] = UInt8(val)
        }
        return bytes
    }
}

func format(bits: [Bit]) -> String {
    return bits.reduce("") { (current, next) in
        return current.appending((next == .one) ? "1" : "0")
    }
}
func randomBits(ofLength: Int) -> [Bit] {
    return (0 ..< ofLength).map() { _  in
        Int(arc4random_uniform(2)) == 1 ? .one : .zero
    }
}
func isValid(conv: BitsToBytesConverter, input: [Bit], expected: [UInt8]) -> Bool {
    let actual = conv.bitsToBytes(bits: input)
    var bIsValid = (actual.count == expected.count)
    if bIsValid {
        for index in 0 ..< expected.count {
            if actual[index] != expected[index] {
                bIsValid = false
                break
            }
        }
    }
    return bIsValid
}
func validateAll() {
    let input0: [Bit] = [.one, .zero, .one, .zero, .one, .zero, .one, .zero]
    let expected0: [UInt8] = [170]

    let input1: [Bit] = (0..<8).map { _ in .zero }
    let expected1: [UInt8] = [0]

    let input2: [Bit] = (0..<8).map { _ in .one }
    let expected2: [UInt8] = [255]

    let input3 = input1 + input2
    let expected3 = expected1 + expected2

    let input4 = input2 + input1
    let expected4 = expected2 + expected1

    let inputs = [input0, input1, input2, input3, input4]
    let expecteds = [expected0, expected1, expected2, expected3, expected4]

    let convs: [BitsToBytesConverter] = [MR1(), MR2()]

    for inIndex in 0 ..< inputs.count {
        let input = inputs[inIndex]
        let expected = expecteds[inIndex]

        let formattedBits = format(bits: input)
        print("Checking: \(formattedBits) -> \(expected)")

        for conv in convs {
            let bIsValid = isValid(conv: conv, input: input, expected: expected)
            print("\(conv.ident) valid = \(bIsValid)")
        }
    }
}
func timeTest(conv : BitsToBytesConverter, bitsArray: [[Bit]]) {
    // Prime compilation, caching, ...
    let _ = conv.bitsToBytes(bits: bitsArray[0])

    let startTime = NSDate()
    var hash = 0

    for bits in bitsArray {
        let _ = conv.bitsToBytes(bits: bits)

        // Hash to compare results across methods
        //let result = conv.bitsToBytes(bits: bits)
        //let bString = format(bits: bits)
        //print("Bits: \(bString): Bytes: \(result)")
        //hash = result.reduce(0) { (previous, next) in
        //    return previous + next.hashValue
        //}
    }
    let duration = -startTime.timeIntervalSinceNow
    print("\(conv.ident): \(duration): hash \(hash)")
}
func testAll() {
    let numBits = 128 // Bits per bit array
    let numBitArrays = 100 // Number of bit arrays

    let testValues = (0 ..< numBitArrays).map() { _ in
        randomBits(ofLength: numBits)
    }
    timeTest(conv: MR1(), bitsArray: testValues)
    timeTest(conv: MR2(), bitsArray: testValues)
}
//validateAll()
testAll()