Chodzi Ci może o
odwracanie bitowe?
Jeżeli tak, to zasada działania jest względnie prosta.
mamy próbki w tablicy o indeksach powiedzmy i = 0..n-1.
teraz bierzemy drugą taką tablicę (to tak dla uproszczenia, w rzeczywistości nie jest ona konieczna, bo można zrobić to na tej samej tablicy)
dla każdej próbki o indeksie i odwracamy kolejność bitów w zmiennej i, tzn. dla i=01100101 robimy i=10100110 i zapisujemy w tablicy jako element o takim indeksie.
i największym problemem jest włąśnie to odwrócenie kolejności bitów. metod jest conajmniej kilka.
Najprostsza, ale strasznie niewydajna to przetwarzanie po jednym bicie, w asemblerze jeszcze jako tako to wygląda, bo tam można operować bitem przeniesienia, ale w C... hmmm, już nie ma tak lekko, zwłąszcza, że raczej żaden kompilator tego odpowiednio nie zoptymalizuje.
Przykład strasznie paskudny:
int bitrev(int i, int n) { /* i - wartość do 'obrócenia', n - ilość bitów */
int z, o;
o = 0;
for(z = 0; z<n; z++)
if(i && 1<<z)
o |= 1<<(n-z-1);
return(o);
}
Druga opcja, to wygenerowanie odpowiedniej tabeli zawierającej 'odwrócone' wartości, wtedy zamiana miejscami pójdzie naprawdę szybko
Poza tym widziałem ten algorytm wykonany na wszelakiej moaści pętlach; nowe indeksy były przeliczane 'w locie', coś jak dodawanie binarne, tyle że z odwrotnie ustawionymi bitami.
Na przykład zwiększenie 'odwróconej' liczby o 1 (przykłąd z książki "Hackers Delight"):
unsigned x, m;
m = 0x80000000;
x = x ^ m;
if ((int)x >= 0) {
do {
m = m >> 1;
x = x ^ m;
} while (x < m);
}
Można też sukcesywnie dzielić liczbę (jej zapis bitowy) na połowy (żródło j.w.):
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
Jeżeli zamierzasz to implementować na komputerze i będziesz liczył wiele transformat tej samej wielkości pod rząd, to chyba najwydajniejsza będzie metoda z uprzednim wygenerowaniem tabelki.
No i chyba tyle. Mam nadzieję, że o to chodziło
