uninterlace Bits von 16-Bit-Wert

Question

Ich habe einen 16-Bit-Wert mit Bits "interlaced".

Ich möchte ein Array von 8 Elemente erhalten (Werte von 0 bis 3), die die Bits in dieser Reihenfolge gespeichert werden:

• item 0: Bits 7 und 15
• Punkt 1: Bits 6 und 14
• Punkt 2: Bits 5 und 13
• ...
• Punkt 7: Bits 0 und 8

Dies ist eine triviale Lösung:

function uninterlace(n) {
  return [((n>>7)&1)|((n>>14)&2), // bits 7 and 15
          ((n>>6)&1)|((n>>13)&2), // bits 6 and 14
          ((n>>5)&1)|((n>>12)&2), // bits 5 and 13
          ((n>>4)&1)|((n>>11)&2), // bits 4 and 12
          ((n>>3)&1)|((n>>10)&2), // bits 3 and 11
          ((n>>2)&1)|((n>> 9)&2), // bits 2 and 10
          ((n>>1)&1)|((n>> 8)&2), // bits 1 and 9
          ((n>>0)&1)|((n>> 7)&2)];// bits 0 and 8
}

Hat jemand weiß besser (schneller) Weg, dies zu tun?

Edit:

Weitere Informationen:

• Erstellen Sie eine vorberechnete Tabelle ist keine Option.
• Kann nicht Assembler oder CPU-spezifische Optimierungen verwenden

Answer 1

Ok, jetzt mit drei Operationen pro Stück (getestet und funktioniert).

Dies ist eine Variation von Novelocrat Antwort. Es verwendet variable Masken und Dias.

function uninterlace(n) {     
     return [((n & 0x8080) + 0x3FFF) >> 14,
             ((n & 0x4040) + 0x1FFF) >> 13,
             ((n & 0x2020) + 0x0FFF) >> 12,
             ((n & 0x1010) + 0x07FF) >> 11,
             ((n & 0x0808) + 0x03FF) >> 10,
             ((n & 0x0404) + 0x01FF) >> 9,
             ((n & 0x0202) + 0x00FF) >> 8,
             ((n & 0x0101) + 0x007F) >> 7];
}

Answer 2

Schneller als eine handgeschriebene entrollten Schleife? Ich bezweifle es.

Der Code weniger repetitiven gemacht werden, um eine for-Schleife durch die Verwendung, aber das wäre es nicht schneller laufen zu lassen.

Answer 3

def uninterlace(n) {
    mask = 0x0101 // 0b0000_0001_0000_0001
    slide = 0x7f  // 0b0111_1111
    return [(((n >> 0) & mask) + slide) >> 7,
            (((n >> 1) & mask) + slide) >> 7,
            (((n >> 2) & mask) + slide) >> 7,
            (((n >> 3) & mask) + slide) >> 7,
            (((n >> 4) & mask) + slide) >> 7,
            (((n >> 5) & mask) + slide) >> 7,
            (((n >> 6) & mask) + slide) >> 7,
            (((n >> 7) & mask) + slide) >> 7]
}

Dies ist nur vier Operationen pro Eintrag, statt 5. Der Trick ist, die verschobene Wert bei der Wiederverwendung. Die Zugabe von slide bewegt sich die entsprechenden Bits benachbart zueinander sind, und die Verschiebung um 7 stellt sie in der Position niedriger Ordnung. Die Verwendung von + könnte eine Schwäche sein.

Eine größere Schwäche könnte sein, dass jede Operation der Eingabe muss vollständig in Folge durchgeführt werden, der eine Latenz von 4 Befehlen Erstellen von einem Prozessor Pipeline eintritt, um es zu verlassen. Diese können vollständig pipeline, würde aber immer noch eine gewisse Verzögerung haben. Die Frage der Version macht einig Instruction-Level Parallelität und könnte möglicherweise eine Latenz von pro Eintrag nur 3 Anweisungen hat, ausreichend Ausführungsressourcen gegeben.

Es könnte möglich sein, mehrere Extraktionen in weniger Operationen zu kombinieren, aber ich habe nicht einen Weg, es zu tun noch nicht gesehen. Die Verschränkung ist in der Tat, dass eine Herausforderung.

Edit: a. Zwei Pässe Ansatz, um die niedrigen und hohe Bits symmetrisch zu behandeln, mit verschachteltem 0'en, verschiebt sie voneinander durch eine aus und oder das Ergebnis könnte viel schneller und skalierbarer zu mehr bitstrings sein

Herausgegeben die slide pro Pedro Kommentar zu korrigieren. Leider Ihre Zeit auf meiner armen Basis-Konvertierung Fähigkeiten zu übernehmen. Es wurde ursprünglich 0xef, die den 0-Bit an der falschen Stelle setzt.

Answer 4

Wie wärs mit einer kleinen vorberechneten Tabelle von 128 Einträgen mal 2?

int[128] b1 = { 2, 3, 3, .. 3};
int[128] b0 = { 0, 1, 1, .. 1};

function uninterlace(n) {
  return [(n & 0x8000) ? b1 : b0)[n & 0x80],
          (n & 0x4000) ? b1 : b0)[n & 0x40],
          (n & 0x2000) ? b1 : b0)[n & 0x20],
          (n & 0x1000) ? b1 : b0)[n & 0x10],
          (n & 0x0800) ? b1 : b0)[n & 0x08],
          (n & 0x0400) ? b1 : b0)[n & 0x04],
          (n & 0x0200) ? b1 : b0)[n & 0x02],
          (n & 0x0100) ? b1 : b0)[n & 0x01]
         ];
}

Dies verwendet Bit Maskierung und Nachschlagen in einer Tabelle anstelle von Verschiebungen und Additionen und könnte schneller sein.