Swift массив бит в массив байт (Uint8 массив)

Question

У меня есть массив с битами:

var bits: [Bit] 

и как я могу преобразовать его в байты массива:

var bytes: [UInt8] 

Например, у меня есть 280 бит и У меня должно быть 35 UInt8 в массиве байтов. Я могу думать о решении, где я беру 8 бит и проверяю, является ли первое истинным, если второе верно и так, и суммируем результаты и имеют значение. Это я сделал бы для каждых 8 бит в моем битном массиве. Но я думаю, что это было бы плохим решением (это сработало бы, но с ненужными вычислениями). Я думаю, что может быть более быстрое решение с некоторыми изменениями и так, но я действительно плохо в этом, поэтому я ищу помощь. Благодаря

Answer 1

Возможное решение перечислить все биты в массиве и для всех «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] 

В качестве альтернативы, вы можете "встроенный" вычисление для каждой группы 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)) 
    } 
} 

---

контрольные показатели: Вот теперь быстрый и грязный приложение бенчмаркинг (код ниже), сравнивая различные решения. Он измеряет время преобразования 10 000 бит массивов длиной 256. Тесты были выполнены на MacBook Pro 2,3 ГГц 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($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

Если вы предпочитаете функциональный подход, ценой более дорогостоящего вычисления, тогда вы можете использовать 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.

Update Забыл упомянуть, что если вы хотите преобразовать в другой целочисленный тип, просто измените IntegerType псевдоним.

Answer 3

Это забавный вопрос. Я рассматриваю это как две более мелкие проблемы: (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($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] 
    } 
} 

решить второй, мы можем написать функцию, которая принимает каждый Slice<Bit> вернулся из group(_:byCount:) и преобразует его в 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] 

Answer 4

некоторые прохладно код здесь @ мартеновской-р @antonio @ Nate-повара, но также, кажется, некоторые вопросы корректности, которые я обнаружил в процессе преобразования этого кода в Swift 3 для моего использования. Особенность этого пересмотренного сниппета:

• Xcode 8, Swift 3,0, в перспективе в Playground
• Включает возможность проверки (закомментирована)
• Has Бит перечисления для представления типа Bit. (Тип бит был удален из Swift 3)
• Хотя это все еще имеет временную аппаратуру, я не пытался действительно проверять скорость различных методов. Кажется, мы должны сначала обеспечить правильные результаты.
• Только Martin1 и Martin2 закодированы. Другие методы, оставленные как упражнение для читателя;).

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