Алгоритм для расширения / дублирования битов? - PullRequest
Новая
       14

Алгоритм для расширения / дублирования битов?

6 голосов
/ 26 января 2012

Существует ли эффективный (быстрый) алгоритм, который будет выполнять расширение / дублирование битов?

Например, расширить каждый бит в 8-битном значении на 3 (создав 24-битное значение): 

1101 0101 => 11111100 01110001 11000111

Метод грубой силы, который был предложен, заключается в создании справочной таблицы. В будущем значение расширения, возможно, должно быть переменным. То есть в приведенном выше примере мы расширяемся на 3, но, возможно, потребуется расширить на некоторые другие значения. Это потребует нескольких таблиц поиска, которых я бы хотел избежать, если это возможно.

Ответы [ 2 ]

7 голосов
/ 28 января 2012

Есть шанс сделать это быстрее, чем справочная таблица, если арифметические вычисления по какой-то причине быстрее, чем доступ к памяти. Это может быть возможно, если вычисления векторизованы (PPC AltiVec или Intel SSE) и / или если другим частям программы необходимо использовать каждый бит кэш-памяти.

Если коэффициент расширения = 3, необходимо всего 7 инструкций: 

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7;

Или другой вариант, с 10 инструкциями: 

out = (in | in << 8) & 0x0F00F;
out = (out | out << 4) & 0x0C30C3;
out = (out | out << 2) & 0x249249;
out *= 7;

Для других коэффициентов расширения> = 3: 

unsigned mask = 0x0FF;
unsigned out = in;
for (scale = 4; scale != 0; scale /= 2)
{
  shift = scale * (N - 1);
  mask &= ~(mask << scale);
  mask |= mask << (scale * N);
  out = out * ((1 << shift) + 1) & mask;
}
out *= (1 << N) - 1;

Или другая альтернатива для коэффициентов расширения> = 2: 

unsigned mask = 0x0FF;
unsigned out = in;
for (scale = 4; scale != 0; scale /= 2)
{
  shift = scale * (N - 1);
  mask &= ~(mask << scale);
  mask |= mask << (scale * N);
  out = (out | out << shift) & mask;
}
out *= (1 << N) - 1;
Значения

shift и mask лучше рассчитывать до обработки битового потока.

1 голос
/ 27 января 2012

Вы можете сделать это одним входным битом за раз. Конечно, это будет медленнее, чем справочная таблица, но если вы делаете что-то вроде написания для крошечного 8-разрядного микроконтроллера без достаточного места для таблицы, он должен иметь минимально возможный объем ПЗУ.

...