bitarray.php

<?php

class BitArray {

    //Sacrifice 2x the amount of memory, so we can use pack/unpack easily
    const INT_SIZE = 4;

    private $bitArray;
    public function __construct($numberOfBits, $bitArray = null) {
        $numberOfInts = $numberOfBits / self::INT_SIZE / 8; // PHP_INT_SIZE is in bytes
        if($bitArray != null)
            $this->bitArray = $bitArray;
        else {
            for($i = 0; $i < $numberOfInts; $i++) {
                $this->bitArray[] = 0;
            }
        }
    }

    public function setBit($bit) {
        $index = floor($bit / self::INT_SIZE / 8);
        $bitInIndex = $bit % (self::INT_SIZE * 8);
        $this->bitArray[$index] = pow(2, $bitInIndex) | $this->bitArray[$index];
    }

    public function unsetBit($bit) {
        $index = floor($bit / self::INT_SIZE / 8);
        $bitInIndex = $bit % (self::INT_SIZE * 8);
        $this->bitArray[$index] = (~pow(2, $bitInIndex)) & $this->bitArray[$index];
    }

    public function toIntArray() {
        $intIndex = 0;
        $retArray = array();
        foreach($this->bitArray as $intInArray) {
            for($i = 0; $i < (self::INT_SIZE * 8); $i++) {
                if(($intInArray | pow(2, $i)) == $intInArray) {
                    $retArray[] = $intIndex;
                }
                $intIndex++;
            }
        }
        return $retArray;
    }

    public function __tostring() {
        $retString = "";
        foreach($this->bitArray as $intToPack) {
            $retString .= pack("L", $intToPack);
        }
        return $retString;
    }

    public static function loadFromString($string) {
        $bitArray = array_merge(unpack("L*", $string));
        return new BitArray(mb_strlen($string, '8bit'), $bitArray);
    }

    public static function orFn($thisBitArray, $thatBitArray) {
        return BitArray::loadFromString($thisBitArray->__tostring() | $thatBitArray->__tostring());
    }
}