Найти "края" в 32-битном слове bitpattern

Question

Я пытаюсь найти наиболее эффективный алгоритм для подсчета "ребер" в битовой структуре. Край, означающий изменение от 0 до 1 или от 1 до 0. Я выбираю каждый бит каждые 250 мкс и сдвигаю его в 32-битную переменную без знака.

Пока это мой алгоритм

void CountEdges(void)
{
    uint_least32_t feedback_samples_copy = feedback_samples;
    signal_edges = 0;

    while (feedback_samples_copy > 0)
    {
        uint_least8_t flank_information = (feedback_samples_copy & 0x03);

        if (flank_information == 0x01 || flank_information == 0x02)
        {
            signal_edges++;
        }

        feedback_samples_copy >>= 1;
    }
}

Это должно быть как минимум в 2 или 3 раза быстрее.

Answer 1

Вы должны быть в состоянии поразрядно XOR их вместе, чтобы получить битовый шаблон, представляющий перевернутые биты. Затем воспользуйтесь одним из способов подсчета битов на этой странице: http://graphics.stanford.edu/~seander/bithacks.html, чтобы подсчитать, сколько единиц в результате.

Answer 2

Одна вещь, которая может помочь, состоит в том, чтобы предварительно вычислить число фронтов для всех возможных 8-битных значений (таблица поиска 512 записей, поскольку вы должны включить бит, предшествующий каждому значению), а затем суммировать 1 байт счетчика в время.

// prevBit is the last bit of the previous 32-bit word
// edgeLut is a 512 entry precomputed edge count table
// Some of the shifts and & are extraneous, but there for clarity
edgeCount = 
    edgeLut[(prevBit << 8) | (feedback_samples >> 24) & 0xFF] + 
    edgeLut[(feedback_samples >> 16) & 0x1FF] + 
    edgeLut[(feedback_samples >>  8) & 0x1FF] + 
    edgeLut[(feedback_samples >>  0) & 0x1FF];

prevBit = feedback_samples & 0x1;

Answer 3

Мое предложение:

• скопировать введенное значение во временную переменную, смещенное влево на одну
• скопировать младший бит вашего ввода в переменную yout temp
• XOR два значения. Каждый бит, установленный в результирующем значении, представляет один фронт.
• используйте этот алгоритм для подсчета количества установленных бит.

Это может быть код для первых 3 шагов:

uint32 input; //some value
uint32 temp = (input << 1) | (input & 0x00000001);
uint32 result = input ^ temp;

//continue to count the bits set in result
//...

Answer 4

вы всегда можете использовать справочную таблицу, скажем, 8 бит за раз таким образом, вы получите улучшение скорости примерно в 8 раз

не забудьте проверить биты между этими 8 битами. Затем они должны быть проверены «вручную»

Answer 5

Вы смотрите только 2 бита во время каждой итерации.
Самым быстрым алгоритмом, вероятно, будет создание хеш-таблицы для всех возможных значений. Поскольку есть 2 ^ 32 значения, это не лучшая идея.
Но почему бы вам не посмотреть на 3, 4, 5 ... биты за один шаг? Например, вы можете пересчитать для всех 4-битных комбинаций ваш счетчик ребер. Просто позаботьтесь о возможных краях между частями.

Answer 6

Создайте справочную таблицу, чтобы вы могли получить переходы внутри байта или 16-битного значения за один снимок - тогда все, что вам нужно сделать, - это посмотреть на различия в «крайних» битах между байтами (или 16- битовые значения).