Swift tablica bitów na bajty tablicy (array Uint8)

Question

Mam tablicę z bitami:

var bits: [Bit] 

i jak mogę przekonwertować go bajtów tablicy:

var bytes: [UInt8] 

Na przykład mam 280 bitów i Powinienem mieć 35 UInt8 w tablicy bajtów. Mogę wymyślić rozwiązanie, w którym biorę 8bitów i sprawdzam, czy pierwsza jest prawdziwa, czy druga jest prawdą, a następnie sumuje wyniki i ma wartość. To bym zrobił dla każdego 8 bitów w mojej tablicy bitów. Ale myślę, że byłoby to złe rozwiązanie (działałoby, ale z niepotrzebnymi obliczeniami). Myślę, że może być szybsze rozwiązanie z pewnymi zmianami, ale jestem w tym zły, więc szukam pomocy. Dzięki

Answer 1

Możliwym rozwiązaniem jest wymienić wszystkie bity w tablicy i dla wszystkich „jeden” bity ustawić odpowiedni bit w tablicy 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 
} 

Główną ideą jest to, że dla danego index w tablicy bitów, index/8 jest odpowiednim indeksem w tablicy bajtów, i index % 8 jest pozycją bitu w bajcie. Możesz użyć index % 8 lub 7 - index % 8 jako wartość przesunięcia, w zależności od żądanej kolejności bitów .

przykład:

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

Alternatywnie można "inline" obliczenie dla każdej grupy 8 bitów. Musisz sprawdzić, które rozwiązanie działa lepiej w twojej sprawie .

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 
} 

Tutaj, dla uproszczenia, jeśli liczba bitów nie jest wielokrotnością liczby 8, nadmiarowe bity są ignorowane. Ten sam kod może być także napisany trochę „Swiftier” jako

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

---

Benchmarki: Oto teraz szybkie i-brudny aplikacja benchmarking (kod poniżej), porównując różne rozwiązania. Mierzy czas na konwersję 10 000 bitowych tablic o długości 256. Testy przeprowadzono na komputerze MacBook Pro 2,3 GHz Intel Core i7, i kodzie skompilowanym z konfiguracją "Release".

Wyniki szybkimi 1,1/Xcode 6.2 (6C131e):

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

Wyniki szybkimi 1,2/Xcode 6,3 (6D532l):

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

Kod:

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

Jeśli preferujesz podejście funkcjonalne, kosztem droższych obliczeń, wtedy możesz użyć reduce w kombinacji z enumerate.

Ten ostatni, biorąc pod uwagę sekwencję elementów, tworzy sekwencję krotek (index, element). Potrzebujemy indeksu, aby znać pozycje bitów.

reduce a nie jest wykorzystywany do zmniejszenia tablicę Bit do tablicy 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 
} 

zwrócony wynik jest tablicą UInt8.

Aktualizacja Zapomniałem wspomnieć, że jeśli chcesz przekonwertować do innego typu całkowitego, wystarczy zmienić IntegerType alias.

Answer 3

To zabawne pytanie. Patrzę na to jako dwa mniejsze problemy: (1) jak podzielić tablicę z Bit na tablicę z macierzami Bit, gdzie każda mniejsza tablica ma wartość jednego bajta i (2) jak przekonwertować te mniejsze tablice na jeden bajt każdy.

Aby rozwiązać pierwsze, można napisać funkcję grupy tablicą na plasterki o określonej wielkości:

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

Aby rozwiązać ten drugi może napisać funkcję, która przyjmuje każdy Slice<Bit> zwrócone od group(_:byCount:) i zamienia go na UInt8. Na każdym kroku przesuwa wartość w lewo o jeden bit, a następnie ustawia bit jedynek jeśli ten element jest .One:

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

Wreszcie, można nazwać każdy z nich po kolei, lub połączyć je, aby uzyskać wynik:

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

Niektóre fajne kod tutaj @ martin-r @antonio @ Nate gotować, ale również wydaje się być pewne kwestie poprawności odkryłem podczas konwersji tego kodu do Swift 3 do mojego użytku. Cechą tego zmienionego fragmentu:

• Xcode 8 Swift 3.0, a metę na placu zabaw
• Zawiera funkcję walidacji (wykomentowane)
• Has Bit Nazwa reprezentowania typu bit. (Typ bitowy został usunięty z Swift 3)
• Mimo że wciąż ma instrument czasowy, nie próbowałem naprawdę przetestować prędkości różnych metod. Wygląda na to, że musimy najpierw zapewnić poprawne wyniki.
• Tylko kodowanie Martin1 i Martin2. Inne metody pozostawione jako ćwiczenie dla czytelnika;).

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

Zresztą, tutaj jest mój kod silnie oparta na pracy innych. Mam nadzieję, że niektórzy uważają to za przydatne.

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