php实现bitmap
PHP 实现 Bitmap
Bitmap（位图）是一种高效的数据结构，适用于大规模数据的快速查询和去重。PHP 中可以通过字符串或数组模拟位操作实现 Bitmap。
基础实现（使用字符串）
PHP 字符串的每个字符可视为 8 位（1 字节），通过位运算操作特定位：
class Bitmap {
private $bitmap = '';
// 设置某一位为 1
public function setBit($offset) {
$bytePos = (int)($offset / 8);
$bitPos = $offset % 8;
// 扩展字符串长度
if ($bytePos >= strlen($this->bitmap)) {
$this->bitmap .= str_repeat("\0", $bytePos - strlen($this->bitmap) + 1);
}
$this->bitmap[$bytePos] = $this->bitmap[$bytePos] | chr(1 << $bitPos);
}
// 检查某一位是否为 1
public function getBit($offset) {
$bytePos = (int)($offset / 8);
$bitPos = $offset % 8;
if ($bytePos >= strlen($this->bitmap)) {
return false;
}
return (ord($this->bitmap[$bytePos]) & (1 << $bitPos)) !== 0;
}
}优化实现（使用 GMP 扩展）
若安装 GMP 扩展，可直接操作大整数实现更高效的 Bitmap：
class BitmapGMP {
private $bitmap;
public function __construct() {
$this->bitmap = gmp_init(0);
}
public function setBit($offset) {
$this->bitmap = gmp_or($this->bitmap, gmp_pow(2, $offset));
}
public function getBit($offset) {
return gmp_testbit($this->bitmap, $offset);
}
}使用示例
$bitmap = new Bitmap();
$bitmap->setBit(100);
var_dump($bitmap->getBit(100)); // 输出 true
var_dump($bitmap->getBit(99)); // 输出 false应用场景
- 去重处理：快速判断元素是否存在
- 布隆过滤器：作为底层数据结构
- 权限系统：用位表示权限组合
性能注意事项
- 字符串实现的 Bitmap 在 PHP 中内存占用较高，建议对超过 100,000 位的场景使用 GMP 扩展
- 位操作时需注意 PHP 的整数溢出问题（32/64 位系统差异）
