Swift 位数组到字节数组(UInt8 数组)

Swift Bit array to Bytes array (UInt8 array)

我有带位的数组:

var bits: [Bit]

以及如何将其转换为字节数组:

var bytes: [UInt8]

例如我有 280 位,我应该有 35 个 UInt8 字节数组。我可以想到解决方案,我采用 8 位并检查第一个是否为真,第二个是否为真等等并对结果求和并具有价值。我会为我的位数组中的每 8 位执行此操作。但我认为这将是一个糟糕的解决方案(它可以工作,但需要进行不必要的计算)。我认为可能会有更快的解决方案,但我在这方面真的很糟糕,所以我正在寻求帮助。谢谢

一个可能的解决方案是枚举数组中的所有位 并为所有 "One" 位设置 UInt8 中的相应位 数组:

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
}

主要思想是对于位数组中给定的indexindex / 8是字节数组中对应的索引, index % 8 是字节中的位位置。你可以 使用 index % 87 - index % 8 作为偏移量,具体取决于 所需的位顺序。

示例:

// 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]

或者,您可以"inline"计算每个组 的 8 位。您必须检查哪种解决方案性能更好 在你的情况下。

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
}

这里为了简单起见,如果位数不是8的倍数,则忽略多余的位数。同样的代码也可以写一点 "Swiftier" 作为

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: 现在这是一个快速而简单的基准测试应用程序(代码如下),比较了各种解决方案。 它测量转换 10,000 个长度为 256 的位数组的时间。 测试是在 MacBook Pro 2.3 GHz Intel Core i7 上完成的, 以及使用 "Release" 配置编译的代码。

结果 Swift 1.1/Xcode 6.2 (6C131e):

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

结果 Swift 1.2/Xcode 6.3 (6D532l):

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

代码:

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([=14=], groupCount, array.count) }

        // zip those together & map onto an array of slices of the input array
        return map(Zip2(startIndices, endIndices)) {
            array[[=14=].0 ..< [=14=].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())

如果您更喜欢函数式方法,但代价是计算成本更高,那么您可以将 reduceenumerate 结合使用。

后者,给定一个元素序列,创建一个 (index, element) 元组序列。我们需要索引来了解位的位置。

reduce 用于将 Bit 的数组缩减为 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
}

返回结果为UInt8.

的数组

更新 忘了说,如果你想转换成不同的整数类型,只需更改 IntegerType 别名即可。

这是个有趣的问题。我将其视为两个较小的问题:(1) 如何将 Bit 的数组拆分为 Bit 的数组,其中每个较小的数组是一个字节的位,以及 (2) 如何将那些较小的数组每个转换为一个字节。

为了解决第一个问题,我们可以编写一个函数,将数组分组为特定大小的切片:

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([=10=], groupCount, array.count) }

    // zip those together & map onto an array of slices of the input array
    return map(zip(startIndices, endIndices)) {
        array[[=10=].0 ..< [=10=].1]
    }
}

为了解决第二个问题,我们可以编写一个函数,将 group(_:byCount:) 返回的每个 Slice<Bit> 转换为 UInt8。在每一步它都将值左移一位,然后如果该元素是 .One:

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

最后,您可以依次调用它们中的每一个,或者将它们组合起来以获得结果:

// 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]

这里有一些很酷的代码@martin-r @antonio @nate-cook,但我在将这段代码转换为 Swift 3[= 时似乎也发现了一些正确性问题23=] 供我使用。此修改后的代码段的特点:

  • Xcode 8,Swift 3.0,在游乐场运行
  • 包括验证功能(已注释掉)
  • 有 Bit 枚举来表示 Bit 类型。 (位类型已从 Swift 3 中删除)
  • 虽然这仍然有计时工具,但我还没有尝试真正测试不同方法的速度。看来我们需要先确保结果正确。
  • 只有 Martin1 和 Martin2 编码。其他方法留作练习 reader ;).
Martin1: 0.112455010414124: hash 0
Martin2: 1.06640499830246: hash 0

无论如何,这是我的代码强烈基于其他人的工作。希望有人觉得这很有用。

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

对于swift 5

func convertBitsToBytes(bits : [Bit]) -> [UInt8] {
    let numBits = bits.count
    let numBytes = (numBits + 7)/8
    var bytes = [UInt8](unsafeUninitializedCapacity: numBytes) { (buffer, initializedCount) in
        
    }
    
    for (index, bit) in bits.enumerated() {
        if bit == .one {
            bytes[index / 8] += UInt8(1 << (7 - index % 8))
        }
    }
    return bytes
}