Лучший метод, чтобы узнать установленные битовые позиции в битовой маске в C

Question

Что было бы лучшим способом идентифицировать все установленные битовые позиции в 64-битной битовой маске. Предположим, что моя битовая маска - 0xDeadBeefDeadBeef, тогда каков наилучший способ идентифицировать все позиции битов установленных битов в ней.

long long bit_mask = 0xdeadbeefdeadbeef;
unsigned int bit_pos=0;
while(mask) {
  if((mask&1)==1) {
     printf("Set bit position is:%d \n",bit_pos};
  }
  bit_pos++;
  mask>>=1; 
}

Один из способов состоит в том, чтобы пройти через него и проверить, установлен ли бит или нет, если он установлен, вернуть позицию отсчета и продолжить цикл до MSB, поэтому для 64 битов я буду повторяться, пока не пройдут все установленные биты или все пройденные 64 бита, если установлен MSB, но должен быть лучший способ сделать это?

Answer 1

Алгоритм от восторга Хакера (книга):

int count_bits(long long s)
{
    s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
    s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
    s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
    s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
    s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
    s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);

    return (int)s;
}

Answer 2

Помимо уже объясненных приятных мелочей, есть и другие варианты.

Это предполагает, что у вас есть x86(64), SSE4, gcc и компиляция с ключом -msse4, который вы можете использовать:

int CountOnesSSE4(unsigned int x)
{
    return __builtin_popcount(x);
}

Это скомпилирует в одну команду popcnt. Если вам нужен быстрый код, вы можете проверить SSE во время выполнения и использовать лучшую доступную функцию.

Если вы ожидаете, что число будет иметь небольшое количество единиц, это также может быть быстрым (и всегда быстрее, чем обычный цикл сдвига и сравнения):

int CountOnes(unsigned int x)
{
    int cnt = 0;
    while (x) {
        x >>= ffs(x);
        cnt++;
    }
    return cnt;
}

На x86 (даже без SSE) ffs скомпилируется в одну инструкцию (bsf), и количество циклов будет зависеть от количества единиц.

Answer 3

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

int count_bits(long long value) {
    int n = 0;
    while(value) {
        n += (value & 1);
        value >>= 1;
   }
   return n;
}

Для производительности вы можете вызвать count_bits из ответа X J.

int count_bits(long long s)
{
    s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
    s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
    s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
    s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
    s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
    s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);

    return (int)s;
}

Это зависит от того, хотите ли вы просмотреть свой код и сказать себе: "Да, это имеет смысл" или "Я приму слово этого парня".

Я был вызван на это прежде в переполнении стека. Некоторые люди не согласны. Некоторые очень умные люди предпочитают сложность за простоту. Я считаю, что чистый код - это простой код.

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

Также рассмотрим обзор кода. Что вы собираетесь сказать, когда кто-то говорит: "Как работает count_bits?"

Answer 4

Вы могли бы сделать это:

long long bit_mask = 0xdeadbeefdeadbeef;

int i;
for (i = 0; i < (sizeof(long long) * 8); i++) {
    int res = bit_mask & 1;
    printf ("Pos %i is %i\n", i, res);
    bit_mask >>= 1;

}

Answer 5

Если вы подсчитываете их, вы можете использовать быстрое решение для хакеров, но справочная таблица может быть (не всегда) быстрее. И гораздо понятнее. Вы можете предварительно подготовить таблицу, например, из 256 элементов глубиной, которые представляют собой значения байтов от 0x00 до 0xFF

0, //0x00
1, //0x01
1, //0x02
2, //0x03
1, //0x04
2, //0x05
2, //0x06
3, //0x07
...

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

После сборки вы можете разбить большее число на байты

count  = table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
...

если у вас больше памяти, вы можете сделать таблицу еще больше, представив более широкие числа, таблицу глубиной 65536 для чисел от 0x0000 до 0xFFFF.

count  = table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;

Таблицы - это общий способ сделать такие вещи быстрее за счет потребления памяти. Чем больше памяти вы можете использовать, тем больше вы можете предварительно вычислить (во время или до времени компиляции), а не в реальном времени.