PHP: gmp_popcount - Manual (original) (raw)
(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)
gmp_popcount — Population count
Description
Parameters
num
A GMP object, an int, or a string that can be interpreted as a number following the same logic as if the string was used in gmp_init() with automatic base detection (i.e. when base is equal to 0).
Return Values
The population count of num, as an int.
Examples
Example #1 gmp_popcount() example
<?php $pop1 = gmp_init("10000101", 2); // 3 1's echo gmp_popcount($pop1) . "\n"; $pop2 = gmp_init("11111110", 2); // 7 1's echo gmp_popcount($pop2) . "\n"; ?>
The above example will output:
Found A Problem?
4 years ago
Another way to get the population count when you don't have the gmp extension is using bitwise operations:
<?php
$int = 133; // 10000101
for($count = 0; <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mi>n</mi><mi>t</mi><mo stretchy="false">!</mo><mo>=</mo><mn>0</mn><mo separator="true">;</mo></mrow><annotation encoding="application/x-tex">int != 0; </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">in</span><span class="mord mathnormal">t</span><span class="mclose">!</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8389em;vertical-align:-0.1944em;"></span><span class="mord">0</span><span class="mpunct">;</span></span></span></span>count++) // repeat until <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mi>n</mi><mi>t</mi><mi>i</mi><mi>s</mi><mn>0</mn><mo stretchy="false">(</mo><mi>a</mi><mi>n</mi><mi>d</mi><mi>c</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>a</mi><mi>m</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>o</mi><mi>f</mi><mi>s</mi><mi>t</mi><mi>e</mi><mi>p</mi><mi>s</mi><mi>i</mi><mi>t</mi><mi>t</mi><mi>a</mi><mi>k</mi><mi>e</mi><mi>s</mi><mi>i</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">int is 0 (and count the amount of steps it takes in </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">in</span><span class="mord mathnormal">t</span><span class="mord mathnormal">i</span><span class="mord mathnormal">s</span><span class="mord">0</span><span class="mopen">(</span><span class="mord mathnormal">an</span><span class="mord mathnormal">d</span><span class="mord mathnormal">co</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mord mathnormal">tt</span><span class="mord mathnormal">h</span><span class="mord mathnormal">e</span><span class="mord mathnormal">am</span><span class="mord mathnormal">o</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mord mathnormal">t</span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord mathnormal">s</span><span class="mord mathnormal">t</span><span class="mord mathnormal">e</span><span class="mord mathnormal">p</span><span class="mord mathnormal">s</span><span class="mord mathnormal">i</span><span class="mord mathnormal">tt</span><span class="mord mathnormal" style="margin-right:0.03148em;">ak</span><span class="mord mathnormal">es</span><span class="mord mathnormal">in</span></span></span></span>count)
{
<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mi>n</mi><mi>t</mi><mo>=</mo></mrow><annotation encoding="application/x-tex">int = </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">in</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span></span></span></span>int & <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mi>n</mi><mi>t</mi><mo>−</mo><mn>1</mn><mo separator="true">;</mo><mi mathvariant="normal">/</mi><mi mathvariant="normal">/</mi><mi>r</mi><mi>e</mi><mi>m</mi><mi>o</mi><mi>v</mi><mi>e</mi><mi>t</mi><mi>h</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi><mi>m</mi><mi>o</mi><mi>s</mi><mi>t</mi><mn>1</mn><mi>f</mi><mi>r</mi><mi>o</mi><mi>m</mi></mrow><annotation encoding="application/x-tex">int-1; // remove the right most 1 from </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7429em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">in</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mpunct">;</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">//</span><span class="mord mathnormal">re</span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="mord mathnormal">e</span><span class="mord mathnormal">t</span><span class="mord mathnormal">h</span><span class="mord mathnormal" style="margin-right:0.02778em;">er</span><span class="mord mathnormal">i</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">h</span><span class="mord mathnormal">t</span><span class="mord mathnormal">m</span><span class="mord mathnormal">os</span><span class="mord mathnormal">t</span><span class="mord">1</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord mathnormal">ro</span><span class="mord mathnormal">m</span></span></span></span>int using the bitwise and operator
}
echo $count; // 3
?>
This is Kernighan's population count.
https://youtu.be/ZRNO-ewsNcQ?t=510 has a nice explanation on how it worksphpmanual at headbank dot co dot uk ¶
7 years ago
If you don't have gmp extension enabled (or don't want to use it for any reason), you can get popcount of an int using decbin() and substr_count().
<?php
$int1 = 133; <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi><mi>i</mi><mi>n</mi><mn>1</mn><mo>=</mo><mi>d</mi><mi>e</mi><mi>c</mi><mi>b</mi><mi>i</mi><mi>n</mi><mo stretchy="false">(</mo></mrow><annotation encoding="application/x-tex">bin1 = decbin(</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">bin</span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">d</span><span class="mord mathnormal">ec</span><span class="mord mathnormal">bin</span><span class="mopen">(</span></span></span></span>int1); // "10000101"
echo substr_count($bin1, "1");
// Result: 3
?>
Being a string-comparison this is far less efficient than gmp_popcount() (for which there is a dedicated instruction on most if not all modern processors), but may be handy if gmp is unavailable, or in non-performance-critical code that doesn't otherwise need it.