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
}
主要思想是对于位数组中给定的index，
index / 8是字节数组中对应的索引，
index % 8 是字节中的位位置。你可以
使用 index % 8 或 7 - 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())
如果您更喜欢函数式方法，但代价是计算成本更高，那么您可以将 reduce 与 enumerate 结合使用。
后者，给定一个元素序列，创建一个 (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
}
我有带位的数组：
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
}
主要思想是对于位数组中给定的index，
index / 8是字节数组中对应的索引，
index % 8 是字节中的位位置。你可以
使用 index % 8 或 7 - 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())
如果您更喜欢函数式方法，但代价是计算成本更高，那么您可以将 reduce 与 enumerate 结合使用。
后者，给定一个元素序列，创建一个 (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
}