Swift bit to Bytes array (UInt8 array)

Question

I have an array with bits:

var bits: [Bit] 

and how can I convert it to an array of bytes:

 var bytes: [UInt8] 

For example, I have 280 bits, and I should have 35 UInt8 in an array of bytes. I can think of a solution where I take 8 bits and check if the first is true, if the second is true and so, and summarize the results and make a difference. I would do this for every 8 bits in my bitmap. But I think that would be a bad decision (it would work, but with unnecessary calculations). I think that there may be a faster solution with some changes and so, but I'm really bad at it, so I'm looking for help. Thanks

Answer 1

A possible solution is to list all the bits in the array and for all the “One” bits sets 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 basic idea is that for a given index in a 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 a shift value, 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 "embed" the calculation for each group of 8 bits. You will need to check which solution works best 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 extra bits are ignored. The same code can be written a little "Faster" 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: Now it's a quick and dirty benchmarking (code below) comparing different solutions. It measures the time to convert 10,000 bits of arrays of length 256. Tests were performed on the 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

the 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 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

This is a fun question. I see this as two smaller problems: (1) how to split a Bit array into an array of Bit arrays, where each smaller array is equal to one byte of bits, and (2) how to convert these smaller arrays to one byte each.

To solve the first problem, we can write a function that groups an array into slices of a certain 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 returns each Slice<Bit> returned from group(_:byCount:) and converts it to UInt8 . At each step, it shifts the value remaining by one bit, and then sets the bit if this .One element .One :

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

Finally, you can call them one at a time or combine them to get the 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 calculation, you can use reduce in combination with enumerate .

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

reduce instead to reduce the Bit array to a UInt8 array

 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 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 I forgot to mention that if you want to convert to another integer type, just change the IntegerType alias.

Answer 4

Some cool code here is @ martin-r @antonio @ nate-cook, but there are also some correctness issues that I found while converting this code to Swift 3 for my use. Feature of this corrected fragment:

• Xcode 8, Swift 3.0 running on the playground
• Enables verification capability (commented out)
• Bit is used to represent the type of bit. (Bit type has been removed from Swift 3)
• Although this still has temporary hardware, I did not try to really check the speed of the various methods. It seems we should ensure the right results first.
• Only Martin1 and Martin2 codes. Other methods left as an exercise for the reader;).

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

Anyway, here is my code is very much based on the work of others. Hope some find this helpful.

 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()