Эффективные побитовые операции для подсчета битов или поиска правых | левых

Question

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

1. Подсчитать количество битов, установленных на 1
2. Найти индекс самого левого 1 бита
3. Найти индекс самого правого 1 бита

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

Я сделал это с помощью побитового сдвига, но мне нужно перебирать почти все биты (es.32). Например, считая 1:

unsigned int number= ...;
while(number != 0){
    if ((number & 0x01) != 0)
        ++count;
    number >>=1;
}

Другие операции аналогичны.

Итак, мой вопрос: есть ли более быстрый способ сделать это?

Answer 1

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

Windows / MSVC:

• _BitScanForward ()
• _BitScanReverse ()
• __ POPCNT ()

GCC:

• __ builtin_ffs ()
• __ builtin_ctz ()
• __ builtin_clz ()
• __ builtin_popcount ()

Как правило, они отображаются непосредственно на аппаратные инструкции. Так что это не намного быстрее, чем эти.

Но поскольку для них нет функций C / C ++, они доступны только через встроенные функции компилятора.

Answer 2

Взгляните на ffs (3), ffsl (3), fls (3), flsl (3).

Функции ffs () и ffsl () находят первый установленный бит (начиная с младшего значащего бита) в i и возвращают индекс этого бита.

Функции fls () и flsl () находят последний бит, установленный в i, и возвращают индекс этого бита.

Возможно, вас заинтересует цепочка битов (3).

Answer 3

Цитирование из http://graphics.stanford.edu/~seander/bithacks.html

Лучший способ подсчета битов в 32-разрядном целом числе v следующий:

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Лучший метод подсчета битов занимает всего 12 операций, что аналогично методу таблицы поиска, но позволяет избежать ошибок памяти и кэша таблицы. Это гибрид между чисто параллельным методом, описанным выше, и более ранними методами, использующими умножения (в разделе по подсчету битов с 64-битными инструкциями), хотя он не использует 64-битные инструкции. Подсчет битов, установленных в байтах, выполняется параллельно, а общая сумма битов, установленных в байтах, вычисляется путем умножения на 0x1010101 и сдвига вправо на 24 бита.

Answer 4

Один из подходов заключается в использовании таблицы соответствия.

uint8_t popcount_table[256] = { ... };

uint8_t popcount (uint32_t x)
{
    uint8_t *p = (uint8_t*)&x;

    return popcount_table[p[0]] +
           popcount_table[p[1]] +
           popcount_table[p[2]] +
           popcount_table[p[3]];
}