Как рассчитать количество положительных битов без использования сдвигов? - PullRequest
Новая
       46

Как рассчитать количество положительных битов без использования сдвигов?

6 голосов
/ 20 ноября 2011

Во время собеседования, которое у меня было некоторое время назад, меня попросили подсчитать количество положительных (то есть равных «1») битов в структуре битового вектора (например, целое число без знака или длинное число). Мое решение было довольно простым в C #: 

int CountBits(uint input)
{
   int reply = 0;
   uint dirac = 1; 
   while(input != 0)
   {
      if ((input & dirac) > 0) reply++;
      input &= ~dirac;
      dirac<<=1;
   }
   return reply;
}

Затем меня попросили решить задачу без использования каких-либо сдвигов: ни явных (например, «<<» или «>>»), ни неявных (например, умножение на 2). Решение "грубой силы" с использованием потенциального ряда 2 (например, 0, 1, 2, 4, 8, 16 и т. Д.) Также не подойдет.

Кто-нибудь знает такой алгоритм?

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

Ответы [ 3 ]

13 голосов
/ 20 ноября 2011

Существует этот x & (x-1) хак, который, если вы подумаете об этом, очистит последний 1 в целом числеОтдых тривиален.

1 голос
/ 20 ноября 2011

Точно так же, как описал Энтони Блейк, но, пожалуй, немного более читабельно. 

uint32_t bitsum(uint32_t x)
{
    // leafs (0101 vs 1010)
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

    // 2nd level (0011 vs 1100)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

    // 3rd level (nybbles)
    //x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x07070707) + ((x >> 4) & 0x07070707);

    /*
    // 4th level (bytes)
    //x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x000f000f) + ((x >> 8) & 0x000f000f);

    // 5th level (16bit words)
    //return (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return (x & 0x0000001f) + ((x >> 16) & 0x0000001f);
    */
    // since current mask of bits 0x0f0f0f0f
    // result of summing 0f + 0f = 1f
    // x * 0x01010101 will produce
    // sum of all current and lower octets in
    // each octet
    return (x * 0x01010101) >> 24;
}
1 голос
/ 20 ноября 2011

Некоторые процессоры имеют инструкцию подсчета населения. Если нет, то я считаю, что это самый быстрый метод (для 32-битных): 

int NumberOfSetBits(int i) {
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

См. Эту ссылку для полного объяснения: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

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

int NumberOfSetBits(int i) {
  unsigned char * p = (unsigned char *) &i;
  return BitsSetTable256[p[0]] + BitsSetTable256[p[1]] + 
     BitsSetTable256[p[2]] + BitsSetTable256[p[3]];
}

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
...