In-Place-Bit-umgekehrt Shuffle auf einem Array
https://stackoverflow.com/questions/932079
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Für eine FFT-Funktion Ich brauche die Elemente innerhalb eines Arrays in einem wenig umgekehrten Weg permutieren oder zu mischen. Das ist eine gemeinsame Aufgabe mit FFTs, weil die meisten Zweierpotenz Größe FFT-Funktionen entweder erwarten oder zurückkehren, um ihre Daten in einem Bit umgekehrten Weg.
z. davon ausgehen, dass das Array 256 Elemente hat Ich mag würde jedes Element tauschen mit ihm ist die Bit-Muster umgekehrt. Hier sind zwei Beispiele (binär):
Element 00000001b should be swapped with element 10000000b
Element 00010111b should be swapped with element 11101000b
und so weiter.
Jede Idee, wie diese schnell und wichtiger zu tun: in-place?
Ich habe bereits eine Funktion, die diese Swap tut. Es ist nicht schwer zu schreiben. Da es sich um eine solche gemeinsame Operation in DSP habe ich das Gefühl, dass es mehr clevere Möglichkeiten, es als meine sehr naiive Schleife zu tun sind.
Sprache in Frage C, aber jede Sprache ist in Ordnung.
Lösung
mit einem einzigen Durchgang anstelle vertauschen, iterieren einmal durch alle Elemente in Index zu erhöhen. Führen Sie eine Swap nur dann, wenn der Index weniger als der umgekehrten Index - dies wird die Doppel Swap Problem überspringen und auch Palindrom Fälle (Elemente 00000000B, 10000001b, 10100101b), die invers zu dem gleichen Wert und kein Swap erforderlich ist
// Let data[256] be your element array
for (i=0; i<256; i++)
j = bit_reverse(i);
if (i < j)
{
swap(data[i],data[j]);
}
Die bit_reverse () kann mit Nathaneil des Bit-Operationen Trick sein. Die bit_reverse () wird 256 Mal aufgerufen werden, aber die swap () wird weniger als 128 mal aufgerufen werden.
Andere Tipps
Eine schnelle Möglichkeit, dies zu tun, ist jedes benachbartes einzelnes Bit, dann 2-Bit-Felder etc. tauschen Der schnelle Weg, dies zu tun ist:
x = (x & 0x55) << 1 | (x & 0xAA) >> 1; //swaps bits
x = (x & 0x33) << 2 | (x & 0xCC) >> 2; //swapss 2-bit fields
x = (x & 0x0F) << 4 | (x & 0xF0) >> 4;
Während schwer zu lesen, wenn dies ist etwas, das optimiert werden muss, Sie mögen es auf diese Art und Weise tun.
Dieser Code verwendet eine Nachschlagtabelle 64-Bit-Zahlen sehr schnell zu umkehren. Für Ihre C-Sprache Beispiel Ich habe auch Versionen für 32-, 16- und 8-Bit-Zahlen (übernimmt int 32 Bit). In einer objektorientierten Sprache (C ++, C #, usw.), hätte ich überlastet nur die Funktion.
Ich habe keine C-Compiler praktisch im Moment so hat, hoffentlich, ich habe nichts verpassen.
unsigned char ReverseBits[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};
unsigned long Reverse64Bits(unsigned long number)
{
unsigned long result;
result =
(ReverseBits[ number & 0xff] << 56) |
(ReverseBits[(number >> 8) & 0xff] << 48) |
(ReverseBits[(number >> 16) & 0xff] << 40) |
(ReverseBits[(number >> 24) & 0xff] << 32) |
(ReverseBits[(number >> 32) & 0xff] << 24) |
(ReverseBits[(number >> 40) & 0xff] << 16) |
(ReverseBits[(number >> 48) & 0xff] << 8) |
(ReverseBits[(number >> 56) & 0xff]);
return result;
}
unsigned int Reverse32Bits(unsigned int number)
{
unsigned int result;
result =
(ReverseBits[ number & 0xff] << 24) |
(ReverseBits[(number >> 8) & 0xff] << 16) |
(ReverseBits[(number >> 16) & 0xff] << 8) |
(ReverseBits[(number >> 24) & 0xff]);
return result;
}
unsigned short Reverse16Bits(unsigned short number)
{
unsigned short result;
result =
(ReverseBits[ number & 0xff] << 8) |
(ReverseBits[(number >> 8) & 0xff]);
return result;
}
unsigned char Reverse8Bits(unsigned char number)
{
unsigned char result;
result = (ReverseBits[number]);
return result;
}
Wenn Sie darüber nachdenken, was mit dem bitswapped Index geschieht, es wird auf die gleiche Weise gezählt, dass der Nicht-bitswapped Index gezählt wird, nur mit den Bits von herkömmlichen Zählen in umgekehrter Reihenfolge verwendet werden.
Anstatt den Index jedes Mal durch die Schleife bitswapping Sie manuell implementieren können ‚++‘ gleichwertig, die Bits in der falschen Reihenfolge verwendet eine Doppel indiziert für Schleife zu tun. Ich habe festgestellt, dass gcc bei O3 inlines die Inkrementfunktion, sondern darüber, ob es schneller dann jedes Mal die Nummer über eine Lookup bitswapping, das ist der Profiler zu sagen.
Hier ist ein veranschaulichender Prüfprogramm.
#include <stdio.h>
void RevBitIncr( int *n, int bit )
{
do
{
bit >>= 1;
*n ^= bit;
} while( (*n & bit) == 0 && bit != 1 );
}
int main(void)
{
int max = 0x100;
int i, j;
for( i = 0, j = 0; i != max; ++i, RevBitIncr( &j, max ) )
{
if( i < j )
printf( "%02x <-> %02x\n", i, j );
}
return 0;
}
Mit einer vorgefertigten Lookup-Tabelle der Zuordnung zu tun scheint die offensichtliche Lösung. Ich denke, es hängt davon ab, wie groß die Arrays Sie werden zu tun sind. Aber auch wenn eine direkte Zuordnung nicht möglich ist, würde ich immer noch für eine Lookup-Tabelle gehen, vielleicht von Byte-Größe Mustern, die Sie verwenden können, das Wort großen Muster für den endgültige Index zu erstellen.
Der folgende Ansatz berechnet den nächsten Bit-Index umgekehrt von dem vorherigen wie in Charles Bailey Antwort, aber in einer Art und Weise optimierte. Beachten Sie, dass eine Anzahl Flips einfach eine Sequenz von am wenigsten signifikanten Bits, beispielsweise von 0111 Inkrementieren 1000. Also, um den nächsten Bit-Index umgekehrt zu berechnen, haben Sie eine Folge von höchstwertigen Bits kippen. Wenn Ihre Zielplattform eine CTZ ( „count nachgestellte Nullen“) Anweisung hat, kann dies effizient durchgeführt werden.
Beispiel GCC __builtin_ctz mit:
void brswap(double *a, unsigned n) {
for (unsigned i = 0, j = 0; i < n; i++) {
if (i < j) {
double tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
// Length of the mask.
unsigned len = __builtin_ctz(i + 1) + 1;
// XOR with mask.
j ^= n - (n >> len);
}
}
Ohne CTZ Anweisung, können Sie auch Integer-Division verwenden:
void brswap(double *a, unsigned n) {
for (unsigned i = 0, j = 0; i < n; i++) {
if (i < j) {
double tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
// Compute a mask of LSBs.
unsigned mask = i ^ (i + 1);
// Using division to bit-reverse a single bit.
unsigned rev = n / (mask + 1);
// XOR with mask.
j ^= n - rev;
}
}
Element 00000001b soll getauscht werden mit Element 10000000b
Ich glaube, Sie bedeuten in der ersten Zeile "Element 00000001b sollte mit dem Element 11111110b getauscht werden"?
Statt awapping 256 Bytes Sie das Array werfen könnte (long long *) und tauschen 32 „long long“ Werte statt, die auf 64-Bit-Maschinen viel schneller sein sollte (oder 64 Long-Werte auf einem 32-Bit-Computer verwenden) .
Zweitens, wenn Sie naiv durch das Array und Swap alle Werte mit seinem Komplement laufen, als Sie alle Elemente zweimal tauschen werden, so dass man gar nichts :-) getan hat So Sie zuerst Identität haben, die die Ergänzungen sind und lassen sie aus der Schleife.
