当前位置：首页 > PHP

php实现bitmap

2026-02-14 18:34:27PHP

PHP 实现 Bitmap

Bitmap（位图）是一种高效的数据结构，适用于大规模数据的快速查询、去重和统计。以下是 PHP 中实现 Bitmap 的几种方法。

使用字符串模拟 Bitmap

通过字符串的二进制位来模拟 Bitmap，每个字符的 8 位可以表示 8 个数字的状态。

class Bitmap {
    private $bitmap = '';

    public function set($num) {
        $bytePos = (int)($num / 8);
        $bitPos = $num % 8;

        while (strlen($this->bitmap) <= $bytePos) {
            $this->bitmap .= chr(0);
        }

        $byte = ord($this->bitmap[$bytePos]);
        $byte |= (1 << $bitPos);
        $this->bitmap[$bytePos] = chr($byte);
    }

    public function get($num) {
        $bytePos = (int)($num / 8);
        $bitPos = $num % 8;

        if (strlen($this->bitmap) <= $bytePos) {
            return false;
        }

        $byte = ord($this->bitmap[$bytePos]);
        return ($byte & (1 << $bitPos)) !== 0;
    }
}

// 示例用法
$bitmap = new Bitmap();
$bitmap->set(10);
var_dump($bitmap->get(10)); // true
var_dump($bitmap->get(5));  // false

使用数组模拟 Bitmap

利用 PHP 数组的灵活性，通过整数数组存储位信息。

class Bitmap {
    private $bitmap = [];

    public function set($num) {
        $index = (int)($num / 32);
        $bitPos = $num % 32;

        if (!isset($this->bitmap[$index])) {
            $this->bitmap[$index] = 0;
        }

        $this->bitmap[$index] |= (1 << $bitPos);
    }

    public function get($num) {
        $index = (int)($num / 32);
        $bitPos = $num % 32;

        if (!isset($this->bitmap[$index])) {
            return false;
        }

        return ($this->bitmap[$index] & (1 << $bitPos)) !== 0;
    }
}

// 示例用法
$bitmap = new Bitmap();
$bitmap->set(100);
var_dump($bitmap->get(100)); // true
var_dump($bitmap->get(50));  // false

使用 SplFixedArray 优化性能

SplFixedArray 是 PHP 提供的高性能定长数组，适合处理大量数据。

class Bitmap {
    private $bitmap;
    private $size;

    public function __construct($maxNum) {
        $this->size = (int)($maxNum / 32) + 1;
        $this->bitmap = new SplFixedArray($this->size);

        for ($i = 0; $i < $this->size; $i++) {
            $this->bitmap[$i] = 0;
        }
    }

    public function set($num) {
        $index = (int)($num / 32);
        $bitPos = $num % 32;
        $this->bitmap[$index] |= (1 << $bitPos);
    }

    public function get($num) {
        $index = (int)($num / 32);
        $bitPos = $num % 32;
        return ($this->bitmap[$index] & (1 << $bitPos)) !== 0;
    }
}

// 示例用法
$bitmap = new Bitmap(1000);
$bitmap->set(500);
var_dump($bitmap->get(500)); // true
var_dump($bitmap->get(200)); // false

使用 GMP 扩展处理超大 Bitmap

对于超大范围的 Bitmap，可以使用 PHP 的 GMP 扩展（GNU Multiple Precision Arithmetic Library）。

class Bitmap {
    private $bitmap;

    public function __construct() {
        $this->bitmap = gmp_init(0);
    }

    public function set($num) {
        $this->bitmap = gmp_or($this->bitmap, gmp_pow(2, $num));
    }

    public function get($num) {
        return gmp_testbit($this->bitmap, $num);
    }
}

// 示例用法
$bitmap = new Bitmap();
$bitmap->set(1000000);
var_dump($bitmap->get(1000000)); // true
var_dump($bitmap->get(999999));  // false