How to speed up bit counting in php?

Question

I just want to find the fastest bit count function in php.

For example, 0010101 => 3, 00011110 => 4

I saw that there is a good algorithm that can be implemented in C ++. How to count the number of bits in a 32-bit integer?

Is there a built-in php function or the fastest custom function?

Answer 1

You can try applying a mask with binary AND, and use the shift to test the bits one by one, using a loop that will repeat 32 times.

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

You can also easily place your function in PHP style.

 function NumberOfSetBits($v) { $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; } 

Answer 2

My control code

 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(); 

Benchmarking result:

(NumberOfSetBits ()): 1.429042 milliseconds

benchmark (substr_count ()): 1.672635 milliseconds

(getBitCount ()): 10.464981 milliseconds

I think NumberOfSetBits () and substr_count () are better. Thanks.

Answer 3

I could figure out a few ways, but not sure which one would be the fastest:

• use substr_count ()
• replace all characters '1' with '' and then use strlen ()
• use preg_match_all ()

PS: if you start with an integer, these examples will include using decbin () first.

Answer 4

There are several other ways; but for a decimal 32-bit integer, NumberOfSetBits is by far the fastest.

I recently stumbled upon Brian Kernighan's algorithm , which O(log(n)) has O(n) instead of most others. I do not know why it is not so fast here. but it still has a measurable advantage over all other non-specialized functions.

Of course, nothing can beat NumberOfSetBits with O(1) .

my tests are:

 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'); 

banchmark results (sorted)

 > 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* 

These are numbers from one of my launches (since PHP 7.0.22); others showed different orders in the group in 3.5 seconds. I can say that on my machine four of these five are pretty equal, and bitsBySubstrInt always a bit slower due to types.

For most other methods, decbin is required (which basically takes longer than the actual calculation, I noted them * in the test results); only BitsBySubstr would approach a winner without this gem leg.

It seems to me that you can make count_chars 3 times faster by restricting it to existing characters only. It seems like indexing an array is quite time consuming.

---

edit:

• another version of preg_replace
• fixed version of preg_match_all
• Kernigan algorithm added (fastest algorithm for integers of arbitrary size)
• garbage collection added to benchmarking function
• reran tests

Answer 5

This parameter is slightly faster than NumberOfSetBits ($ v)

 function bitsCount(int $integer) { $count = $integer - (($integer >> 1) & 0x55555555); $count = (($count >> 2) & 0x33333333) + ($count & 0x33333333); $count = ((((($count >> 4) + $count) & 0x0F0F0F0F) * 0x01010101) >> 24) & 0xFF; return $count; }