Binärzahl spiegeln

Hallo liebes Forum,

ich muss für ein Projekt eine binärzahl Spiegel(iterative Fast Fourier Transformation).
Allerdings mache ich das nur aus performanten Gründen, also statt aller Vertauschungen die ich bei einer FFT mache würde ich die Stellen direkt berechnen und muss daher den Platz bestimmen ( der gerade die gespiegelte Binärzahl ist ). Kennt einer von euch vielleicht einen Weg?

Beispiel: 1010 -> 0101

exa

Christoph

Was sind die Rahmenbedingungen?

Wenn die Zahlen nicht zu groß und der Speicher nicht zu klein ist, ist eine Lookup-Table eine sehr schnelle Methode.

Am Ende brauch ich ne Funktion, der ich einen Wert gebe. Die Funktion muss mir dann den Wert für die Richtige stelle liefern. Ich übergebe also eine Dimension 2^1 oder 2^2 oder 2^n.. und die Zahl Bsp 4. Die Funktion muss anhand der Dimension die Stelligkeit berechnen( also 4 bit usw.) und danach die Zahl für 4 bit binär darstellen und spiegeln.

z.b. 2^4 -> [0000, ..., 1111] und dann jede Zahl in der mitte Spiegeln. Ausserdem muss sie es schaffen bei ungerader Stellenanzahl die Mittelstelle fix zu lassen. Für beliebige Eingabe der Dimension.. es muss also auch für 2^20 gehen.

Ich können es in einen String parsen, spiegeln und zurückparsen. Aber da ist zu viel Rechenaufwand.

Exa

Ben04

Verstehe immer noch nicht was du willst. Was soll die Funktion jetzt genau tuen?

das was du brauchst sieht bei mir so aus ..

int bitMirror(int j_cpy) {
int msb;
_asm
	{
	bsf eax,N
	mov msb,eax
	}
int reversed_pos = 0;

for (int k=0;k<msb;k++)
    {
    reversed_pos <<= 1;
    if (j_cpy & 1)
        reversed_pos += 1;
        j_cpy >>= 1;
        }
    }
return reversed_pos;
}

msb ist das most significant bit ... ich habs nur für ia32 prozessoren gebraucht und per asm ist es einfach einfacher ... kann man aber auch einfach anderes berechnen

pale dog

sucht auf dieser seite: http://graphics.stanford.edu/~seander/bithacks.html
nach 'Reversing bit sequences'

Exavier schrieb:

Hallo liebes Forum,

ich muss für ein Projekt eine binärzahl Spiegel(iterative Fast Fourier Transformation).

exa

in den numerical recepies ist die funktion auch drin (in der nähe der fft...)

vielen dank für die antworten..ich wühle mich mal durch

Für die Leute, die mein Problem noch nicht verstanden haben. Ich habe es mal schnell in ner jpg gezeichnet, was ich für den ersten Schritt in der FFT tun muss.

FFT-Vertauschungen

Zuerst wird der Vektor neu angeordnet, indem man ein paar Vertauschungen vornimmt. Und meine Idee war, dass man weniger Vertauschungen brauch, wenn man bereits weiss, wie die Anordnung nach der letzten Vertauschung ist. und um genau das zu berechnen muss man "nur" den Binärwert spiegeln.

BTW: Gibt es einen mathematischen Weg für die Spiegelung wenn man davon ausgeht, dass man nur n Bit hat?

Exa