PHP中如何实现2³²以上数值的位掩码？构建高效64元素Set类

一、2³²以上数值的位掩码操作可行性 #

PHP的位运算符直接对整数的二进制补码进行操作，只要目标数值落在有符号64位整数的有效范围（-2⁶³到2⁶³-1）内，即使是2³²以上的数值，也能正常执行位掩码操作。

你提到PHP整数范围是-2³²至2³²、不存在无符号整数——但只要PHP运行在64位环境下，实际支持的是64位有符号整数，完全能容纳2³²到2⁶³-1之间的数值，这类数值的高位（第32位及以上）可以被位运算符正常处理。

二、基于位运算的64元素Set类实现 #

利用64位整数的每一位代表一个元素的存在状态（1表示存在，0表示不存在），可以实现一个高效的Set类，支持64个元素的快速操作：

class BitSet {
    private int $mask = 0;

    // 添加元素（索引范围：0-63）
    public function add(int $index): void {
        if ($index < 0 || $index > 63) {
            throw new InvalidArgumentException('元素索引必须在0到63之间');
        }
        $this->mask |= (1 << $index);
    }

    // 移除元素
    public function remove(int $index): void {
        if ($index < 0 || $index > 63) {
            throw new InvalidArgumentException('元素索引必须在0到63之间');
        }
        $this->mask &= ~(1 << $index);
    }

    // 检查元素是否存在
    public function contains(int $index): bool {
        if ($index < 0 || $index > 63) {
            return false;
        }
        return ($this->mask & (1 << $index)) !== 0;
    }

    // 判断集合是否为空
    public function isEmpty(): bool {
        return $this->mask === 0;
    }

    // 获取集合元素数量
    public function size(): int {
        return substr_count(decbin($this->mask), '1');
    }

    // 计算两个集合的并集
    public function union(BitSet $other): BitSet {
        $newSet = new BitSet();
        $newSet->mask = $this->mask | $other->mask;
        return $newSet;
    }

    // 计算两个集合的交集
    public function intersection(BitSet $other): BitSet {
        $newSet = new BitSet();
        $newSet->mask = $this->mask & $other->mask;
        return $newSet;
    }

    // 计算当前集合相对于另一个集合的差集
    public function difference(BitSet $other): BitSet {
        $newSet = new BitSet();
        $newSet->mask = $this->mask & ~$other->mask;
        return $newSet;
    }
}

使用说明 #

• 元素索引必须限制在0到63之间，对应64位整数的每一位
• 所有核心操作（添加、删除、查询、集合运算）均为位运算，时间复杂度为O(1)，效率极高
• 若需支持超过64个元素，可以扩展为用整数数组存储多段位掩码，但会增加一定复杂度

内容的提问来源于stack exchange，提问作者theking2