Как узнать, сколько бит включено в число

Ответ 1

Я думаю, что тип формальности, который вы ищете, является "состязательным доказательством".

Предположим, что у нас есть алгоритм A, который работает быстрее, чем O (n). Тогда при достаточно большом n A не должен смотреть на некоторый бит i. Затем мы утверждаем, что A должно быть неверным. "Противник" даст две строки s1 и s2, которые идентичны, за исключением противоположных значений бит i. Алгоритм A вернет то же значение для s1 и s2, поэтому противник "обманул" A, давая неправильный ответ. Таким образом, не существует правильного алгоритма A, выполняющегося в o (n) времени.

Ответ 2

Бит Twiddling Hacks содержит ряд методов, в том числе:

Установленные счетные биты, способ Брайана Кернигана

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Метод Брайана Кернигана проходит через столько итераций, сколько есть установить биты. Итак, если у нас есть 32-битное слово с только набором высоких бит, тогда он будет проходить один раз через цикл.

Примеры алгоритма в действии:

128 == 10000000 ₂, 1 бит установлен

128 & 127 ==   0    10000000 & 01111111 == 00000000

177 == 10110001 ₂, 4 бита

177 & 176 == 176    10110001 & 10110000 == 10110000
176 & 175 == 160    10110000 & 10101111 == 10100000
160 & 159 == 128    10100000 & 10011111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

255 == 11111111 ₂, 8 бит

255 & 254 == 254    11111111 & 11111110 == 11111110
254 & 253 == 252    11111110 & 11111101 == 11111100
252 & 251 == 248    11111100 & 11111011 == 11111000
248 & 247 == 240    11111000 & 11110111 == 11110000
240 & 239 == 224    11110000 & 11101111 == 11100000
224 & 223 == 192    11100000 & 11011111 == 11000000
192 & 191 == 128    11000000 & 10111111 == 10000000
128 & 127 ==   0    10000000 & 01111111 == 00000000

Что касается языкового агностического вопроса об алгоритмической сложности, невозможно сделать лучше, чем O (n), где n - количество бит. Любой алгоритм должен проверять все биты в числе.

Какая сложность в этом заключается, когда вы не будете осторожны в определении n и пусть n будет "числом команд смещения/маскировки бит" или некоторыми такими. Если n - это число бит, то даже простая битовая маска (&) уже является операцией O ( n).

Итак, можно ли это сделать лучше, чем O (n) бит-тесты? Нет.
Может ли это быть сделано меньше, чем O (n) операции add/shift/mask? Да.

Ответ 3

Я всегда использую это:

int
count_bits(uint32_t v)
{
        v = v - ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        return ((v + (v >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}

Вы должны знать размер ваших целых чисел.

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Ответ 4

Брайан Кернханган алгоритм для подсчета 1 бит.

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Прочтите этот и другие бит-трюки: Бит-скручивающиеся хаки.

Ответ 5

Самый быстрый способ сделать это вычисление - с массивом table edx [bl], где регистр bl содержит значение байта. Если число представляет собой один байт, то ответ представляет собой одну инструкцию:

 mov eax, [edx:bl]

Если число содержит в нем много байтов (скажем, массив, на который указывает ebp), то вы зацикливаете байты (где ecx - количество байтов в массиве, содержащем число):

    sub ecx, 1
    mov eax, 0
 DoNextByte:
    mov bl, [ebp:ecx]
    add eax, [edx:bl]
    test ecx, ecx
    jz Done:
    sub ecx, 1
    jmp DoNextByte:
 Done:
    ; answer is in eax

Это самый быстрый способ сделать это и будет быстрее любых математических вычислений. Обратите внимание, что инструкции сдвига в решении Art очень дорогостоящие CPU.

Проблема с решением Kernighan заключается в том, что даже при ручной кодировке в сборке он медленнее, чем мой алгоритм. Если он скомпилирован C, он, вероятно, сгенерирует много обращений к памяти, что замедлит его даже за счет большего количества тактовых циклов, которые требуются.

Обратите внимание, что если сопоставление byte-to-count вставляется рядом с этой инструкцией, тогда вся таблица данных будет находиться в кэше CPU, поэтому будет очень быстро. В этом случае программа C не будет близка (думаю, 20x медленнее или больше).

Ответ 6

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

Он будет еще O (количество бит), но с небольшим коэффициентом.

Ответ 7

Хорошо, здесь, похоже, возникает некоторая путаница о статистике порядка, асимптотической нотации, "большой O".

Верно, что алгоритм Брайана Кернигана лучше с точки зрения количества операций. Тем не менее, неверно, что он асимптотически лучше.

Это можно увидеть из определения большого-O.

Напомним, что по определению функция O (f (n)), когда существует функция g (n) такая, что f (n) & le; k g (n), когда n растет достаточно большим.

Теперь давайте определим w как число бит, заданное в слове, и еще раз отметим, что время выполнения для одного слова, как было отмечено выше, является функцией количества установленных битов. Вызовите эту функцию c (w). Мы знаем, что существует фиксированная ширина слова, назовите ее ww; ясно для любого слова, 0 & le; c (w) & le; ww, и, конечно, худшим случаем является то, что c (w) = c (ww). Таким образом, время выполнения этого алгоритма в худшем случае n c (ww).

Таким образом, для n время выполнения - & le; n c (ww); то есть n & le; n c (ww), и, таким образом, по определению этот алгоритм имеет асимптотическое наихудшее время выполнения O (n).