Libor Zapletal - 1 year ago 203
Swift Question

# Swift Bit array to Bytes array (UInt8 array)

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

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())
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download