зеркальные биты 32-битного слова - PullRequest
Новая
       18

зеркальные биты 32-битного слова

7 голосов
/ 22 ноября 2010

Как бы вы сделали это в C? (Пример: 10110001 становится 10001101, если мы должны были отразить 8 бит). Есть ли какие-либо инструкции на некоторых процессорах, которые бы упростили эту задачу?

Ответы [ 11 ]

8 голосов
/ 22 ноября 2010

На самом деле это называется «инвертирование битов» и обычно выполняется в скремблировании FFT.O (log N) путь (до 32 бит): 

uint32_t reverse(uint32_t x, int bits)
{
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); // Swap _<>_
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); // Swap __<>__
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); // Swap ____<>____
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); // Swap ...
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); // Swap ...
    return x >> (32 - bits);
}

Может быть, эта небольшая «визуализация» помогает:
Пример первых 3 назначений, с uint8_t пример: 

b7 b6 b5 b4  b3 b2 b1 b0
-> <- -> <-  -> <- -> <-
----> <----  ----> <----
---------->  <----------

Ну, если мы занимаемся ASCII-искусством, вот мое: 

7 6 5 4 3 2 1 0
 X   X   X   X 
6 7 4 5 2 3 0 1
 \ X /   \ X /
  X X     X X
 / X \   / X \
4 5 6 7 0 1 2 3
 \ \ \ X / / /
  \ \ X X / /
   \ X X X /
    X X X X
   / X X X \
  / / X X \ \
 / / / X \ \ \
0 1 2 3 4 5 6 7

Это похоже на бабочек БПФ.Вот почему он всплывает с БПФ.

3 голосов
/ 22 ноября 2010

Согласно Rich Schroeppel в этой заметке MIT (если вы можете читать мимо ассемблера), следующие биты в 8-битном байте будут инвертированы, если у вас есть 64-битная арифметика: 

byte = (byte * 0x0202020202ULL & 0x010884422010ULL) % 1023;

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

Это действительно 8-битное количество, которое у вас есть?

2 голосов
/ 13 июля 2018

Почти дубликат Самый эффективный алгоритм для обращения бит (от MSB-> LSB до LSB-> MSB) в C (который имеет много ответов, включая один ответ AVX2 для реверсирования каждые 8- битовый символ в массиве).

X86

На x86 с SSSE3 (Core2 и более поздние версии, Bulldozer и более поздние версии), pshufb (_mm_shuffle_epi8) можно использовать как LUT для выполнения 16 параллельных поисков , Вам нужно только 8 поисков для 8 полубайтов в одном 32-разрядном целом числе, но реальная проблема заключается в разделении входных байтов на отдельные полубайты (с обнулением их верхней половины). Это в основном та же проблема, что и для pshufb popcount.

обратный бит регистра avx2 показывает, как это сделать для упакованного вектора из 32-битных элементов. Тот же код, портированный на 128-битные векторы, прекрасно скомпилируется с AVX.

Это все еще хорошо для одиночного 32-разрядного типа int, потому что x86 имеет очень эффективную обратную связь между целочисленной и векторной регистрами: int bitrev = _mm_cvtsi128_si32 ( rbit32( _mm_cvtsi32_si128(input) ) );. Это стоит всего 2 дополнительных movd инструкции, чтобы получить целое число из целочисленного регистра в XMM и обратно. (Задержка приема-передачи = 3 цикла на процессоре Intel, таком как Haswell.)

ARM:

rbit имеет задержку одного цикла и выполняет целое 32-разрядное целое число в одной инструкции.

2 голосов
/ 22 ноября 2010

Наивный / медленный / простой способ состоит в том, чтобы извлечь младший бит ввода и переместить его в другую переменную, которая накапливает возвращаемое значение. 

#include <stdint.h>

uint32_t mirror_u32(uint32_t input) {
    uint32_t returnval = 0;
    for (int i = 0; i < 32; ++i) {
        int bit = input & 0x01;
        returnval <<= 1;
        returnval += bit;    // Shift the isolated bit into returnval
        input >>= 1;
    }
    return returnval;
}

Для других типов число битов хранения равно sizeof(input) * CHAR_BIT, но это включает в себя потенциальные биты заполнения, которые не являются частью значения. Типы фиксированной ширины - хорошая идея здесь.

+= вместо |= позволяет gcc более эффективно компилировать его для x86 (используя инструкцию shift-and-add x86, LEA). Конечно, есть намного более быстрые способы бит-реверса; увидеть другие ответы. Этот цикл хорош для небольшого размера кода (без больших масок), но в остальном в значительной степени не дает никаких преимуществ.

Компиляторы, к сожалению, не распознают этот цикл как битовый и оптимизируют его до ARM rbit или чего-либо еще. (См. в проводнике компилятора Godbolt )

1 голос
/ 31 августа 2012

Я также только что придумал минимальное решение для зеркального отображения 4 бит (полубайта) во временном пространстве только 16 бит. 

mirr = ( (orig * 0x222) & 0x1284 ) % 63
1 голос
/ 22 ноября 2010

Самым быстрым подходом почти наверняка будет таблица поиска: 

out[0]=lut[in[3]];
out[1]=lut[in[2]];
out[2]=lut[in[1]];
out[3]=lut[in[0]];

Или, если вы можете позволить себе 128 КБ табличных данных (под позволить, я имею в виду использование кэша ЦП, а не использование основной памяти или виртуальной памяти)используйте 16-битные единицы: 

out[0]=lut[in[1]];
out[1]=lut[in[0]];
0 голосов
/ 18 октября 2018

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

Итаквнутри функции C, использующей GNU extended asm, я мог бы использовать: 

uint32_t bit_reverse32(uint32_t inp32)
{
    uint32_t out = 0;
    asm("RBIT %0, %1" : "=r" (out) : "r" (inp32));
    return out;
}

Существуют компиляторы, которые предоставляют такие встроенные оболочки C, как это.(armcc __rbit) и gcc также имеют некоторые внутренние свойства через ACLE , но с gcc-arm-linux-gnueabihf я не смог найти __rbit C, поэтому пришел к верхнему коду.

Я не смотрел, но, полагаю, на других платформах вы могли бы создать аналогичные решения.

0 голосов
/ 16 октября 2018

Если вы смотрели на Великолепный ответ Майка ДеСимона (как и я), вот «визуализация» в первых 3 заданиях, например uint8_t: 

b7 b6 b5 b4  b3 b2 b1 b0
-> <- -> <-  <- -> <- ->
----> <----  ----> <----
---------->  <----------

Итак, сначала побитовый своп, потом своп "двухбитовая группа" и т. Д.

0 голосов
/ 13 июля 2018 
int mirror (int input)
{// return bit mirror of 8 digit number 
  int tmp2;
  int out=0;
  for (int i=0; i<8; i++)
    {
      out = out << 1;
      tmp2 = input & 0x01;
      out = out | tmp2;
      input = input >> 1;        
    }
   return out;
}
0 голосов
/ 23 ноября 2010 
quint64 mirror(quint64 a,quint8 l=64) {
    quint64 b=0;
    for(quint8 i=0;i&lt;l;i++) {
        b|=(a>>(l-i-1))&((quint64)1<<i);
    }
return b;
}

Эта функция отражает менее 64 бит.Например, он может отображать 12 бит.

quint64 и quint8 определены в Qt.Но в любом случае это можно переопределить.

Страница:
...