Introduction

Counting set bits, also called population count, appears in permission masks, bloom filters, ranking features, and compact analytics. In PHP, the fastest method depends on data shape and call volume, so a useful answer has to include both algorithm choice and benchmarking strategy. The real optimization question is whether your workload is one-off, hot-path, or bulk-oriented.

Method 1: String Conversion Baseline

The simplest implementation converts integer to binary text and counts character 1.

1<?php
2
3declare(strict_types=1);
4
5function popcountString(int $value): int
6{
7    if ($value < 0) {
8        throw new InvalidArgumentException('Only non-negative integers are supported.');
9    }
10
11    return substr_count(decbin($value), '1');
12}
13
14$values = [0, 1, 3, 7, 255, 1023];
15foreach ($values as $v) {
16    echo $v . ' => ' . popcountString($v) . PHP_EOL;
17}

This is readable and fine for low-frequency code, but repeated string conversion is slower in hot paths.

Method 2: Brian Kernighan Algorithm

A faster numeric method repeatedly clears the lowest set bit. Loop count equals number of ones, not total bit width.

1<?php
2
3declare(strict_types=1);
4
5function popcountKernighan(int $value): int
6{
7    if ($value < 0) {
8        throw new InvalidArgumentException('Only non-negative integers are supported.');
9    }
10
11    $count = 0;
12    while ($value !== 0) {
13        $value &= ($value - 1);
14        $count++;
15    }
16
17    return $count;
18}
19
20$values = [0, 1, 3, 7, 255, 1023, 123456789];
21foreach ($values as $v) {
22    echo $v . ' => ' . popcountKernighan($v) . PHP_EOL;
23}

This is usually the best default because it is fast, compact, and dependency-free for most PHP workloads.

Method 3: Byte Lookup Table for Bulk Processing

For very large arrays, precompute set-bit counts for all byte values and reuse the table.

1<?php
2
3declare(strict_types=1);
4
5function buildByteTable(): array
6{
7    $table = array_fill(0, 256, 0);
8
9    for ($i = 1; $i < 256; $i++) {
10        $table[$i] = $table[$i >> 1] + ($i & 1);
11    }
12
13    return $table;
14}
15
16function popcountLookup(int $value, array $table): int
17{
18    if ($value < 0) {
19        throw new InvalidArgumentException('Only non-negative integers are supported.');
20    }
21
22    $count = 0;
23    while ($value > 0) {
24        $count += $table[$value & 0xFF];
25        $value >>= 8;
26    }
27
28    return $count;
29}
30
31$table = buildByteTable();
32echo popcountLookup(65535, $table) . PHP_EOL;

This can outperform other methods when processing many values in tight loops.

Benchmark in Your Own Environment

Performance results vary by PHP version, hardware, and data distribution. Always benchmark locally before deciding.

1<?php
2
3declare(strict_types=1);
4
5function benchmark(callable $fn, array $data, int $rounds = 5): float
6{
7    $best = INF;
8
9    for ($r = 0; $r < $rounds; $r++) {
10        $start = hrtime(true);
11        $sum = 0;
12
13        foreach ($data as $value) {
14            $sum += $fn($value);
15        }
16
17        $elapsedMs = (hrtime(true) - $start) / 1_000_000;
18        $best = min($best, $elapsedMs);
19
20        if ($sum < 0) {
21            echo $sum;
22        }
23    }
24
25    return $best;
26}
27
28$data = [];
29for ($i = 0; $i < 200000; $i++) {
30    $data[] = random_int(0, 2_000_000_000);
31}
32
33$table = buildByteTable();
34
35echo 'kernighan: ' . benchmark('popcountKernighan', $data) . PHP_EOL;
36echo 'lookup: ' . benchmark(fn(int $v): int => popcountLookup($v, $table), $data) . PHP_EOL;

Use input ranges that reflect your production values. Sparse and dense bit patterns can change results.

Input Contract and Edge Cases

Define whether negative integers are allowed. Most popcount use cases assume non-negative masks. If you accept negatives, behavior depends on integer representation and shift semantics, which can surprise callers.

For strict APIs, reject negative input early with clear error messages.

Also consider integer width. PHP integer size can differ by platform. If your code depends on fixed 32-bit behavior, normalize inputs explicitly.

Common Pitfalls

• Choosing the fastest looking method without benchmarking real data.
• Rebuilding lookup table inside every function call.
• Ignoring negative value handling and producing ambiguous results.
• Using string conversion in high-volume loops where performance matters.
• Comparing results across environments without recording PHP version and runtime settings.

Summary

• Start with a readable baseline, then optimize only where measurements justify it.
• Kernighan algorithm is a strong default for fast and simple popcount.
• Use byte lookup tables for repeated bulk workloads.
• Benchmark with realistic datasets and controlled runtime conditions.
• Define integer input rules clearly to avoid subtle behavior differences.