当前位置：首页 > PHP

php实现bitmap

2026-01-29 20:42:19PHP

PHP 实现 Bitmap

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

php实现bitmap

使用 PHP 的位运算实现 Bitmap

Bitmap 的核心思想是利用一个二进制位数组（通常用整数数组实现）来标记数据是否存在。每个位可以表示一个数字是否存在（1 表示存在，0 表示不存在）。

php实现bitmap

class Bitmap {
    private $bitmap = [];

    // 设置某个数字存在
    public function set($number) {
        $index = (int)($number / 32);
        $offset = $number % 32;
        if (!isset($this->bitmap[$index])) {
            $this->bitmap[$index] = 0;
        }
        $this->bitmap[$index] |= (1 << $offset);
    }

    // 检查某个数字是否存在
    public function get($number) {
        $index = (int)($number / 32);
        $offset = $number % 32;
        if (!isset($this->bitmap[$index])) {
            return false;
        }
        return ($this->bitmap[$index] & (1 << $offset)) != 0;
    }

    // 清除某个数字的标记
    public function clear($number) {
        $index = (int)($number / 32);
        $offset = $number % 32;
        if (isset($this->bitmap[$index])) {
            $this->bitmap[$index] &= ~(1 << $offset);
        }
    }
}

示例用法

$bitmap = new Bitmap();
$bitmap->set(10);
$bitmap->set(20);

var_dump($bitmap->get(10)); // true
var_dump($bitmap->get(15)); // false
var_dump($bitmap->get(20)); // true

$bitmap->clear(20);
var_dump($bitmap->get(20)); // false

使用字符串模拟 Bitmap

如果数字范围较大，可以用字符串来模拟 Bitmap，节省内存。

class StringBitmap {
    private $bitmap = '';

    // 设置某个数字存在
    public function set($number) {
        $byteIndex = (int)($number / 8);
        $bitOffset = $number % 8;
        if (strlen($this->bitmap) <= $byteIndex) {
            $this->bitmap .= str_repeat("\0", $byteIndex - strlen($this->bitmap) + 1);
        }
        $this->bitmap[$byteIndex] = $this->bitmap[$byteIndex] | chr(1 << $bitOffset);
    }

    // 检查某个数字是否存在
    public function get($number) {
        $byteIndex = (int)($number / 8);
        $bitOffset = $number % 8;
        if (strlen($this->bitmap) <= $byteIndex) {
            return false;
        }
        return (ord($this->bitmap[$byteIndex]) & (1 << $bitOffset)) != 0;
    }

    // 清除某个数字的标记
    public function clear($number) {
        $byteIndex = (int)($number / 8);
        $bitOffset = $number % 8;
        if (strlen($this->bitmap) > $byteIndex) {
            $this->bitmap[$byteIndex] = $this->bitmap[$byteIndex] & chr(~(1 << $bitOffset));
        }
    }
}

示例用法

$bitmap = new StringBitmap();
$bitmap->set(100);
$bitmap->set(200);

var_dump($bitmap->get(100)); // true
var_dump($bitmap->get(150)); // false
var_dump($bitmap->get(200)); // true

$bitmap->clear(200);
var_dump($bitmap->get(200)); // false