en place aléatoire inversé bits sur un tableau

StackOverflow https://stackoverflow.com/questions/932079

  •  06-09-2019
  •  | 
  •  

Question

Pour une fonction FFT je dois ou permuter mélanger les éléments dans un tableau d'une manière inversée bits. C'est une tâche commune avec TFR parce que la plupart puissance de deux fonctions de taille FFT soit attendre ou retourner leurs données d'une manière inversée bits.

par exemple. supposer que la matrice comporte 256 éléments je voudrais échanger chaque élément avec son motif binaire inverse. Voici deux exemples (en binaire): 

Element 00000001b should be swapped with element 10000000b
Element 00010111b should be swapped with element 11101000b

et ainsi de suite.

Toute idée comment faire rapide et plus importante: en place?

Je l'ai déjà une fonction qui fait ce swap. Il est pas difficile d'écrire un. Comme il est une opération commune dans le DSP, j'ai le sentiment qu'il existe des moyens plus intelligents pour le faire que ma boucle très naiive.

langue en question est C, mais toute langue est très bien.

Était-ce utile?

La solution

Pour échanger en place avec une seule passe, itérer une fois par tous les éléments dans l'index. Effectuer un échange que si l'indice est moins que l'indice inversé - ce qui va sauter le double problème de swap et aussi palindrome cas (éléments 00000000b, 10000001b, 10100101b) qui inverse à la même valeur et pas de swap est nécessaire 

// 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]);
    }

Le bit_reverse () peut être en utilisant l'astuce de bits des opérations de Nathaneil. Le bit_reverse () sera appelée 256 fois mais le swap () sera appelé moins de 128 fois.

Autres conseils

Une façon rapide de le faire est d'échanger chaque bit adjacent, puis les champs 2 bits, etc. La façon rapide de faire est: 

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;

Bien que difficile à lire, si cela est quelque chose qui doit être optimisé, vous pouvez le faire de cette façon.

Ce code utilise une table de consultation pour inverser très rapidement les numéros 64 bits. Pour votre exemple en langage C, je aussi inclus des versions pour 32-, 16-, et les numéros 8 bits (ce qui suppose int est de 32 bits). Dans un langage orienté objet (C ++, C #, etc.), je viens de surcharger la fonction.

Je n'ai pas un outil pratique au moment du compilateur C donc, je l'espère, je ne rien manquer. 

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

Si vous pensez à ce qui se passe à l'index bitswapped, il est en cours de comptage de la même façon que l'indice non bitswapped est compté, juste avec les bits utilisés dans l'ordre inverse de comptage classique.

Au lieu de bitswapping l'indice à chaque fois dans la boucle, vous pouvez mettre en œuvre manuellement un équivalent « ++ » qui utilise des bits dans le mauvais ordre de faire une double indexation pour boucle. Je l'ai vérifié que gcc à O3 inline la fonction d'incrément, mais pour que ce soit plus vite alors bitswapping le numéro via une recherche à chaque fois, ce qui est pour le profileur dire.

Voici un programme de test d'illustration. 

#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;
}

En utilisant une table de consultation pré-construite pour faire la cartographie semble être la solution évidente. Je suppose que cela dépend de la taille des tableaux que vous allez traiter sont. Mais même si une mise en correspondance directe est impossible, je serais toujours aller pour une table de consultation, peut-être des modèles de taille d'octets que vous pouvez utiliser pour construire le modèle de texte de taille pour l'indice final.

L'approche suivante calcule l'index suivant inversé bits de la précédente comme dans la réponse de Charles Bailey, mais d'une manière plus optimisée. A noter que l'incrémentation d'un nombre retourne simplement une séquence de bits les moins significatifs, par exemple de 0111 à 1000. Ainsi, afin de calculer l'index suivant inversé bits, vous devez retourner une séquence de bits les plus significatifs. Si votre plate-forme cible a une instruction CTZ ( « count zéros »), cela peut être fait efficacement.

Exemple d'utilisation de __builtin_ctz de GCC: 

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

Sans une instruction CTZ, vous pouvez également utiliser la division entière: 

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

élément 00000001b doit être troqué   avec 10000000b élément

Je pense que dans la première ligne que vous voulez dire « Element 00000001b doit être échangé avec l'élément 11111110b »?

Au lieu de awapping 256 octets, vous pouvez transtyper le tableau (long long *) et échanger 32 « long long » valeurs à la place, qui devrait être beaucoup plus rapide sur les machines 64 bits (ou utiliser 64 valeurs longues sur une machine 32 bits) .

Ensuite, si vous exécutez naïvement à travers le réseau et d'échanger toutes les valeurs avec son complément que vous échanger tous les éléments deux fois, alors vous avez rien fait du tout :-) Donc, vous devez d'abord l'identité qui sont les compléments et les laisser sortir de la boucle.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top