<?php
//所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
/*
若N=1;申请内存空间为inta[2];
假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为inta[1+N/32]，其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：
1.求十进制0-N对应在数组a中的下标：n/32
2.求0-N对应0-31中的数：N%32=M
3.利用移位0-31使得对应32bit位为1:1<<M，并置1;
举例:
如果想存储3
(1)a下标30/32=0;放在a[0]中;
(2)3%32=30;
(3)左移30位01000000000000000000000000000000这个对应的值$a[0]=1073741824;
1.求十进制0-N对应在数组a中的下标：
十进制0-31，对应在a[0]中，先由十进制数n转换为与32的余可转化为对应在数组a中的下标。比如n=24,那么n/32=0，则24对应在数组a中的下标为0。又比如n=60,那么n/32=1，则60对应在数组a中的下标为1，同理可以计算0-N在数组a中的下标。
2.求0-N对应0-31中的数：
十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。
3.利用移位0-31使得对应32bit位为1.
找到对应0-31的数为M,左移M位：即2^M.然后置1.
由此我们计算10000000个bit占用的空间：
1byte=8bit
1kb=1024byte
1mb=1024kb
占用的空间为：10000000/8/1024/1024mb。
大概为1mb多一些。
*/
classbigMap{
//使用两个字节保存
private$mask=0x1f;
private$bitsperword=32;
//移位的位数为5pow(2,5)=32
private$shift=5;
//存储数据的数组
public$bitArray=array();
/**
$i对应的数归零
*/
functionclearbit($i){
////则将当前byte中的指定bit位取0，&后其他对方数组bit位必然不变，这就是1的妙用
//$i>>SHIFT这里相当于intval($i/32);
//$i&$this->mask这里相当于$i%$this->mask,取余
@$this->bitArray[$i>>$this->shift]&=~(1<<($i&$this->mask));
}
/**
$i对应的数致1
*/
functionsetbit($i){
@$this->bitArray[$i>>$this->shift]|=(1<<($i&$this->mask));
}
//test测试所在的bit为是否为1
functiontestbit($i){
return$this->bitArray[$i>>$this->shift]&(1<<($i&$this->mask));
}
}
$oBig=newbigMap();
$oBig->setbit(30);
var_dump($oBig->testbit(2));
var_dump($oBig->bitArray);
echodecbin($oBig->bitArray[0]),"<br>";
