на месте бит с обращенным битом в массиве - PullRequest
Новая
       12

на месте бит с обращенным битом в массиве

7 голосов
/ 31 мая 2009

Для функции БПФ мне нужно переставить или перестановить элементы в массиве битовым способом. Это обычная задача для БПФ, потому что большинство мощных функций БПФ двух размеров либо ожидают, либо возвращают свои данные в обращенном порядке.

например. Предположим, что в массиве 256 элементов, которые я бы хотел поменять местами с каждым бит-шаблоном Вот два примера (в двоичном виде): 

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

и т. Д.

Есть идеи, как сделать это быстрее и важнее: на месте?

У меня уже есть функция, которая делает этот обмен. Это не сложно написать. Поскольку это такая распространенная операция в DSP, у меня есть ощущение, что есть более умные способы сделать это, чем мой очень наивный цикл.

Речь идет о языке C, но с любым языком все в порядке.

Ответы [ 7 ]

11 голосов
/ 31 мая 2009

Чтобы поменять местами за один проход, повторите один раз по всем элементам в увеличивающемся индексе. Выполняйте обмен только в том случае, если индекс меньше, чем обратный индекс - это позволит пропустить проблему двойного обмена, а также случаи палиндрома (элементы 00000000b, 10000001b, 10100101b), обратные к тому же значению и обмен не требуется. 

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

bit_reverse () может использовать трюк Натанила с битовыми операциями. Bit_reverse () будет вызываться 256 раз, но swap () будет вызываться менее 128 раз.

9 голосов
/ 31 мая 2009

Быстрый способ сделать это - поменять местами каждый соседний бит, затем 2-битные поля и т. Д. Быстрый способ сделать это: 

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;

Несмотря на то, что это трудно читать, если это то, что нужно оптимизировать, вы можете сделать это следующим образом.

7 голосов
/ 31 мая 2009

Этот код использует справочную таблицу для очень быстрого обращения 64-битных чисел. Для вашего примера на языке C я также включил версии для 32-, 16- и 8-битных чисел (предполагается, что int равен 32 битам). На объектно-ориентированном языке (C ++, C # и т. Д.) Я бы просто перегрузил функцию.

У меня сейчас нет под рукой C-компилятора, так что, надеюсь, я ничего не пропустил. 

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;
}
4 голосов
/ 31 мая 2009

Если вы думаете о том, что происходит с индексом побитовой битности, он подсчитывается таким же образом, как и индекс без битсвопа, только с битами, используемыми в порядке, обратном обычному подсчету.

Вместо того, чтобы индексировать битами индекс каждый раз через цикл, вы можете вручную реализовать эквивалент '++', который использует биты в неправильном порядке, чтобы выполнить двойной индекс для цикла. Я проверил, что gcc в O3 включает функцию приращения, но относительно того, будет ли он быстрее, чем битовая очистка числа через поиск каждый раз, это должен сказать профилировщик.

Вот примерная тестовая программа. 

#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;
}
1 голос
/ 10 ноября 2016

Следующий подход вычисляет следующий битовый индекс из предыдущего, как в ответе Чарльза Бэйли, но более оптимизированным способом. Обратите внимание, что увеличение числа просто переворачивает последовательность младших битов, например, от 0111 до 1000. Таким образом, чтобы вычислить следующий перевернутый битовый индекс, вы должны перевернуть последовательность старших значащих битов. Если на вашей целевой платформе есть инструкция CTZ («отсчитывать конечные нули»), это можно сделать эффективно.

Пример использования GCC __builtin_ctz: 

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

Без инструкции CTZ вы также можете использовать целочисленное деление: 

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;
    }
}
1 голос
/ 31 мая 2009

Использование готовой таблицы поиска для сопоставления представляется очевидным решением. Я думаю, это зависит от того, насколько большими будут массивы, с которыми вы будете иметь дело. Но даже если прямое сопоставление невозможно, я бы по-прежнему использовал справочную таблицу, возможно, из шаблонов с байтовым размером, которые можно использовать для построения шаблона с размером слова для конечного индекса.

0 голосов
/ 31 мая 2009

Элемент 00000001b должен быть заменен с элементом 10000000b

Я думаю, что вы имеете в виду "Элемент 00000001b должен быть заменен на элемент 11111110b" в первой строке?

Вместо того, чтобы тратить 256 байтов, вы можете привести массив к (long long *) и поменять местами 32 "long long" значения, что должно быть намного быстрее на 64-битных машинах (или использовать 64 длинные значения на 32-битной машине) .

Во-вторых, если вы наивно пробежитесь по массиву и поменяете местами все значения с его дополнением, вы дважды поменяете местами все элементы, так что вы вообще ничего не сделали :-) Итак, сначала вы должны определить, какие дополнения, и не включать их в свой цикл.

...