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

Некоторое время назад во время собеседования меня попросили вычислить количество положительных (т.е. установленных в "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 и т. Д.) Тоже не подойдет.

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

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


algorithm bit-manipulation bitvector
person Alexander Galkin    schedule 20.11.2011    source источник
comment
Все остальные побитовые операции и любые математические функции разрешены, но, предположительно, сложение разрешено только в том случае, если оно не используется для реализации умножения на два, что эквивалентно битовому сдвигу. Эти вопросы на собеседовании глупы, без обид.   -  person Pascal Cuoq    schedule 20.11.2011
comment
Отличный ресурс для вас gurmeet.net/puzzles/fast-bit-counting-routines   -  person zaf    schedule 20.11.2011
comment
Да, это должен был быть другой подход, а не повторная реализация того, что у меня уже было, только с другим вкусом. Спасибо, что уточнили!   -  person Alexander Galkin    schedule 20.11.2011
comment
См. stackoverflow.com / questions / 1611333 / (среди прочего), который ссылается на графику. stanford.edu/~seander/bithacks.html#CountBitsSetNaive   -  person Matthew Strawbridge    schedule 20.11.2011

Ответы (3)


arrow_upward
13
arrow_downward

Есть этот x & (x-1) хак, который, если вы немного поразмышляете, очищает последнее 1 в виде целого числа. Отдых тривиален.

person Community    schedule 20.11.2011
comment
Вы его где-то читали или нашли сначала самостоятельно? Можно ли придумать такое решение спонтанно во время собеседования? В любом случае, +1 и палец вверх! - person Alexander Galkin; 20.11.2011
comment
@AlexanderGalkin, да, если собеседник знает, как работают компьютеры, но это также хорошо известный трюк ... может быть, скорее, техника, часто бывает полезно не просто считать биты. - person harold; 20.11.2011
comment
@harold: Хм, в какой сфере этот трюк известен? Я много программировал на Ассемблере и читал много ресурсов, посвященных поразрядным операциям - и на самом деле я определенно видел это, потому что даже во время интервью это уже стало звонком. Но я не мог вспомнить или быстро вывести его в стрессовых условиях во время интервью. - person Alexander Galkin; 20.11.2011
comment
@AlexanderGalkin: Думаю, от себя. Точно не могу вспомнить. Может быть, я видел, как это реализовано в инструкциях ассемблера, и только потом проанализировал, что делает эта странная операция ... это было давно. - person ; 20.11.2011
comment
@AlexanderGalkin стресс убивает мысли более эффективно, чем алкоголь :) Уловка часто используется при обработке целых чисел как битовых наборов (также часто всплывает в алгоритмах графов на битовых матрицах), при проверке того, является ли что-то степенью 2 (можно назвать подсчетом с ранним exit) и как часть других битхаков. - person harold; 20.11.2011
comment
Фактически использование инструкции BSF x86 с shift может дать такую ​​же скорость. На самом деле это хорошо работает для разреженных битов, установленных на 1, но может быть не так быстро для ситуации, когда установлены все биты. - person ony; 20.11.2011

arrow_upward
1
arrow_downward

Некоторые процессоры имеют инструкцию по подсчету населения. Если нет, я считаю, что это самый быстрый метод (для 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];
}
person Anthony Blake    schedule 20.11.2011
comment
в этом решении 4 смены - person flolo; 20.11.2011
comment
Интересный. Это выглядит безумно, но, возможно, это действительно работает. Но вопроса не было. Кроме того, он специализируется на определенном количестве битов, вопрос для целых или длинных, что для меня означает потенциально любую длину в битах, хранящуюся в одной переменной. - person ; 20.11.2011
comment
См. Метод таблицы поиска выше - извините, дошел до этой части =) - person Anthony Blake; 20.11.2011
comment
Отказ от переключения передач, как по мне, является синтетическим ограничением. Если у вас их просто нет - используйте умножение. Мне нравится идея сворачивания битов с помощью операции суммирования над двоичным деревом, но это решение выглядит немного иначе. - person ony; 20.11.2011
comment
Кстати. Я думаю, что интервьюер хотел получить ответ с помощью таблицы поиска, а не жонглировать этими битами. - person ony; 20.11.2011

arrow_upward
1
arrow_downward

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

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;
}
person ony    schedule 20.11.2011