PHP位图统计怎么做

wen PHP项目 2026-08-11 118

本文目录导读：

PHP位图统计怎么做

基础位图实现
高效统计方法（核心算法）
实际应用场景示例
性能优化技巧
二进制串转换方法
注意事项

在PHP中实现位图（Bitmap）统计，主要利用整数的二进制位来高效存储和统计大量数据,以下是几种常见的实现方式：

基础位图实现

使用整数数组存储位图

class Bitmap {
    private $bits = [];
    private $size;
    public function __construct($size) {
        $this->size = $size;
        // 初始化数组，每个元素存储32位
        $this->bits = array_fill(0, ceil($size / 32), 0);
    }
    // 设置某一位为1
    public function set($position) {
        $index = intval($position / 32);
        $offset = $position % 32;
        $this->bits[$index] |= (1 << $offset);
    }
    // 获取某一位的值
    public function get($position) {
        $index = intval($position / 32);
        $offset = $position % 32;
        return ($this->bits[$index] >> $offset) & 1;
    }
    // 统计1的个数
    public function count() {
        $total = 0;
        foreach ($this->bits as $value) {
            // 使用内置函数统计
            $total += substr_count(base_convert($value, 10, 2), '1');
            // 或者使用循环
            // while ($value) {
            //     $value = $value & ($value - 1);
            //     $total++;
            // }
        }
        return $total;
    }
    // 清除某一位
    public function clear($position) {
        $index = intval($position / 32);
        $offset = $position % 32;
        $this->bits[$index] &= ~(1 << $offset);
    }
}
// 使用示例
$bitmap = new Bitmap(100000);
$bitmap->set(5);
$bitmap->set(10);
$bitmap->set(1000);
echo "Count: " . $bitmap->count(); // 输出 3

高效统计方法（核心算法）

布赖恩·克尼根算法

function countBits($n) {
    $count = 0;
    while ($n) {
        $n = $n & ($n - 1); // 清除最低位的1
        $count++;
    }
    return $count;
}

查表法（最快）

class BitmapCounter {
    private static $lookupTable;
    // 初始化查找表
    public static function init() {
        if (!self::$lookupTable) {
            self::$lookupTable = [];
            for ($i = 0; $i < 256; $i++) {
                $count = 0;
                $value = $i;
                while ($value) {
                    $value = $value & ($value - 1);
                    $count++;
                }
                self::$lookupTable[$i] = $count;
            }
        }
    }
    // 快速统计整数中1的个数
    public static function countBits($n) {
        self::init();
        return self::$lookupTable[$n & 0xFF] +
               self::$lookupTable[($n >> 8) & 0xFF] +
               self::$lookupTable[($n >> 16) & 0xFF] +
               self::$lookupTable[($n >> 24) & 0xFF];
    }
    // 统计整个位图
    public static function countBitmap($bitmap) {
        $total = 0;
        foreach ($bitmap as $value) {
            $total += self::countBits($value);
        }
        return $total;
    }
}

实际应用场景示例

用户访问统计

class UserVisitTracker {
    private $bitmap;
    private $startDate;
    public function __construct($userId) {
        // 假设统计365天的数据
        $this->bitmap = new Bitmap(365);
        $this->startDate = time();
    }
    public function recordVisit($timestamp) {
        $dayOfYear = intval(($timestamp - $this->startDate) / 86400);
        if ($dayOfYear >= 0 && $dayOfYear < 365) {
            $this->bitmap->set($dayOfYear);
        }
    }
    public function getVisitDays() {
        return $this->bitmap->count();
    }
    public function getContinuousDays($currentDate = null) {
        $today = $currentDate ?: time();
        $count = 0;
        $dayOfYear = intval(($today - $this->startDate) / 86400);
        for ($i = $dayOfYear; $i >= 0; $i--) {
            if ($this->bitmap->get($i)) {
                $count++;
            } else {
                break;
            }
        }
        return $count;
    }
}

大规模ID去重统计

class IDDuplicateChecker {
    private $bitmap;
    public function __construct($maxId) {
        $this->bitmap = new Bitmap($maxId);
    }
    public function addId($id) {
        if ($this->bitmap->get($id)) {
            return false; // 重复ID
        }
        $this->bitmap->set($id);
        return true; // 新ID
    }
    public function getUniqueCount() {
        return $this->bitmap->count();
    }
}

性能优化技巧

使用SplFixedArray提高性能

class OptimizedBitmap {
    private $bits;
    public function __construct($size) {
        $this->bits = new SplFixedArray(ceil($size / 32));
        for ($i = 0; $i < count($this->bits); $i++) {
            $this->bits[$i] = 0;
        }
    }
    public function set($position) {
        $index = intval($position / 32);
        $offset = $position % 32;
        $this->bits[$index] |= (1 << $offset);
    }
    public function count() {
        $total = 0;
        foreach ($this->bits as $value) {
            // 使用内置函数更快
            $total += substr_count(decbin($value), '1');
        }
        return $total;
    }
}

二进制串转换方法

class BitmapBinaryString {
    private $bitString;
    private $size;
    public function __construct($size) {
        $this->size = $size;
        $this->bitString = str_repeat('0', $size);
    }
    public function set($position) {
        if ($position >= 0 && $position < $this->size) {
            $this->bitString[$position] = '1';
        }
    }
    public function count() {
        return substr_count($this->bitString, '1');
    }
    public function toBitmap() {
        return $this->bitString;
    }
}

注意事项

内存优化：32位系统注意整数溢出问题
性能选择：
- 小规模数据使用循环统计
- 大规模数据使用查表法
- 频繁操作使用SplFixedArray

CAS操作（如果需要并发安全）：

function atomicSet(&$bitmap, $position) {
 $index = intval($position / 32);
 $offset = $position % 32;
 do {
     $oldValue = $bitmap[$index];
     $newValue = $oldValue | (1 << $offset);
 } while (!compareAndSwap($bitmap[$index], $oldValue, $newValue));
}

位图统计的核心在于：