Intereting Posts
Как защитить динамический символ от перезаписывания вторым динамическим символом? Конфликт имени функции GCC массив из N указателей на функции, возвращающие указатели на функции Является ли «частным» ключевое слово C? Понимание операторов разыменования, адреса и оператора массива в C устаревшее преобразование из строковой константы в ‘char *’ в c Будет ли условие C всегда возвращать 1 или 0? % i или% d для печати целого числа в c с помощью printf ()? Как сообщить компилятору использовать аппаратные команды с плавающей запятой с ARM Программа для поиска длины строки Реализация критического раздела Указатель strcmp из целого без литья valgrind обнаруживает утечку памяти, но приложения работают Как программно вернуть максимум двух целых чисел без использования каких-либо операторов сравнения и без использования if, else и т. Д.? Почему я должен явно ссылаться на libm?

на месте бит-обратного перетасовки на массив

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

Например, предположим, что в массиве 256 элементов, которые я хотел бы поменять каждый элемент с помощью бита с обратным рисунком. Вот два примера (в двоичном виде):

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

и так далее.

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

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

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

Чтобы поменяться местами с помощью одного прохода, повторите один раз через все элементы с увеличением индекса. Выполните обмен только в том случае, если индекс меньше, чем обратный индекс – это пропустит проблему с двойным свопом, а также случаи палиндрома (элементы 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 () может использовать трюк бит-операций Nathaneil. Бит_реверс () будет вызываться 256 раз, но swap () будет вызываться менее 128 раз.

Быстрый способ сделать это – обменять каждый соседний бит, затем 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; 

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

Этот код использует таблицу поиска для быстрого обращения к 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; } 

Наслаждаться,

Роберт К. Картайно

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

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

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

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

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

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

Пример использования 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; } } 

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

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

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

Во-вторых, если вы наивно запускаете массив и меняете все значения с его дополнением, вы будете менять все элементы дважды, поэтому вы ничего не сделали 🙂 Итак, сначала вам нужно идентифицировать, какие дополнения и оставить их вне цикла ,