当前位置：首页 > PHP

php实现bigmap

2026-02-14 18:08:41PHP

PHP 实现 Bitmap

Bitmap（位图）是一种高效的数据结构，常用于大量数据的快速查询和去重。PHP 中可以通过数组或字符串模拟位操作实现 Bitmap。

基础 Bitmap 实现

使用字符串或数组存储位信息，每个位代表一个数字是否存在。

class Bitmap {
    private $bitmap;

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

    public function setBit($num) {
        $index = (int)($num / 32);
        $offset = $num % 32;
        if (!isset($this->bitmap[$index])) {
            $this->bitmap[$index] = 0;
        }
        $this->bitmap[$index] |= (1 << $offset);
    }

    public function getBit($num) {
        $index = (int)($num / 32);
        $offset = $num % 32;
        if (!isset($this->bitmap[$index])) {
            return false;
        }
        return ($this->bitmap[$index] & (1 << $offset)) != 0;
    }
}

使用示例

$bitmap = new Bitmap();
$bitmap->setBit(100);
var_dump($bitmap->getBit(100)); // bool(true)
var_dump($bitmap->getBit(101)); // bool(false)

优化版本（字符串存储）

对于更大规模的 Bitmap，可以使用字符串存储减少内存占用。

php实现bigmap

class StringBitmap {
    private $bitmap;

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

    public function setBit($num) {
        $bytePos = (int)($num / 8);
        $bitPos = $num % 8;
        while (strlen($this->bitmap) <= $bytePos) {
            $this->bitmap .= "\0";
        }
        $this->bitmap[$bytePos] = $this->bitmap[$bytePos] | chr(1 << $bitPos);
    }

    public function getBit($num) {
        $bytePos = (int)($num / 8);
        $bitPos = $num % 8;
        if (strlen($this->bitmap) <= $bytePos) {
            return false;
        }
        return (ord($this->bitmap[$bytePos]) & (1 << $bitPos)) != 0;
    }
}