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

Мой контрольный код

start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
    getBitCount($i);
}
end_benchmark();

start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
    NumberOfSetBits($i);
}
end_benchmark();
start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
    substr_count(decbin($i), '1');
}
end_benchmark();

Результат сравнительного анализа:

Контрольный показатель (количество наборов бит()): 1,429042 миллисекунд

Контрольный показатель (substr_count()): 1,672635 миллисекунд

Контрольный показатель (getbitcount()): 10,44981 миллисекунд

Я думаю, что NumberOfSetBits() и substr_count() являются лучшими. Спасибо.

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

• использовать substr_count()
• замените все символы "1" на ", а затем используйте strlen()
• используйте preg_match_all()

PS: если вы начнете с целого числа, в этих примерах сначала потребуется использовать decbin().

Существует ряд других способов; но для десятичного 32-разрядного целого числа NumberOfSetBits определенно самый быстрый.

Недавно я наткнулся на Алгоритм Брайана Керниганса , который имеет O(log(n)) вместо большинства других, имеющих O(n). Я не знаю, почему он не появляется здесь так быстро; но у него все еще есть измеримое преимущество перед всеми другими неспециализированными функциями.

Конечно, ничто не может сравниться NumberOfSetBits с O(1).

Мой контрольные показатели:

function getBitCount($value) { $count = 0; while($value) { $count += ($value & 1); $value = $value >> 1; } return $count; }

function getBitCount2($value) { $count = 0; while($value) { if ($value & 1)$count++; $value >>= 1; } return $count; }
// if() instead of +=; >>=1 instead of assignment: sometimes slower, sometimes faster
function getBitCount2a($value) { for($count = 0;$value;$value >>= 1) if($value & 1)$count ++; return $count; }
// for instead of while: sometimes slower, sometimes faster

function getBitCount3($value) { for($i=1,$count=0;$i;$i<<=1) if($value&$i)$count++; return $count; }
// shifting the mask: incredibly slow (always shifts all bits)
function getBitCount3a($value) { for($i=1,$count=0;$i;$i<<=1) !($value&$i) ?: $count++; return $count; }
// with ternary instead of if: even slower

function NumberOfSetBits($v) {
// longest (in source code bytes), but fastest
    $c = $v - (($v >> 1) & 0x55555555); $c = (($c >> 2) & 0x33333333) + ($c & 0x33333333);
    $c = (($c >> 4) + $c) & 0x0F0F0F0F; $c = (($c >> 8) + $c) & 0x00FF00FF;
    $c = (($c >> 16) + $c) & 0x0000FFFF;    return $c;
}

function bitsByPregReplace($n) { return strlen(preg_replace('_0_','',decbin($n))); }
function bitsByNegPregReplace($n) { return strlen(preg_replace('/[^1]/','',decbin($n))); }
function bitsByPregMatchAll($n) { return preg_match_all('/1/',decbin($n)); }

function bitsBySubstr($i) { return substr_count(decbin($i), '1'); }
function bitsBySubstrInt($i) { return substr_count(decbin($i), 1); }
// shortest (in source code bytes)

function bitsByCountChars($n){ return count_chars(decbin($n))[49]; }
// slowest by far
function bitsByCountChars1($n) { return count_chars(decbin($n),1)[49]; }
// throws a notice for $n=0

function Kernighan($n) { for(;$n;$c++)$n&=$n-1;return$c; }
// Brian Kernighan’s Algorithm

function benchmark($function)
{
    gc_collect_cycles();
    $t0=microtime();
    for($i=1e6;$i--;) $function($i);
    $t1=microtime();
    $t0=explode(' ', $t0); $t1=explode(' ', $t1);
    echo ($t1[0]-$t0[0])+($t1[1]-$t0[1]), " s\t$function\n";
}

benchmark('getBitCount');
benchmark('getBitCount2');
benchmark('getBitCount2a');
benchmark('getBitCount3');
benchmark('getBitCount3a');
benchmark('NumberOfSetBits');
benchmark('bitsBySubstr');
benchmark('bitsBySubstrInt');
benchmark('bitsByPregReplace');
benchmark('bitsByPregMatchAll');
benchmark('bitsByCountChars');
benchmark('bitsByCountChars1');
benchmark('decbin');

Результаты по банковским меткам (отсортированы)

> php count-bits.php
 2.286831 s     decbin

 1.364934 s     NumberOfSetBits
 3.241821 s     Kernighan

 3.498779 s     bitsBySubstr*
 3.582412 s     getBitCount2a
 3.614841 s     getBitCount2
 3.751102 s     getBitCount
 3.769621 s     bitsBySubstrInt*

 5.806785 s     bitsByPregMatchAll*
 5.748319 s     bitsByCountChars1*
 6.350801 s     bitsByNegPregReplace*
 6.615289 s     bitsByPregReplace*

13.863838 s     getBitCount3
16.39626 s      getBitCount3a
19.304038 s     bitsByCountChars*

Это числа из одного из моих запусков (с PHP 7.0.22); другие показывали другой порядок в группе 3,5 секунды. Я могу сказать, что на моей машине четыре из этих пяти довольно равны, и bitsBySubstrInt всегда немного медленнее из-за типов.

Большинство других способов требуют декбина (что в основном занимает больше времени, чем фактический подсчет; Я пометил их * в результатах тестирования); только BitsBySubstr смог бы приблизиться к победителю без этой дурацкой ноги.

Я нахожу заметным, что вы можете сделать count_chars в 3 раза быстрее, ограничив его только существующими символами. Похоже, что индексирование массива требует довольно много времени.

Изменить:

• добавлена еще одна preg_replace версия
• исправлена preg_match_all версия
• добавлен алгоритм Керниганса (самый быстрый алгоритм для целых чисел произвольного размера)
• добавлена сборка мусора для сравнительного анализа функция
• повторные тесты