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

Учитывая unsigned int, я должен выполнить следующие операции:

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

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

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

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

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

Поэтому мой вопрос: есть ли более быстрый способ сделать это?

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

    Windows / MSVC:

    • _BitScanForward ()
    • _BitScanReverse ()
    • __popcnt ()

    GCC:

    • __builtin_ffs ()
    • __builtin_ctz ()
    • __builtin_clz ()
    • __builtin_popcount ()

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

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

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

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

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

    Возможно, вас тоже заинтересовала битовая строка (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 бит.

    Один из подходов – использовать таблицу поиска.

     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]]; } 
    Давайте будем гением компьютера.