<?php
//所謂的Bit-map就是用一個bit位來標(biāo)記某個元素對應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。

/*

若 N =1 ; 申請內(nèi)存空間為 int a[2] ; 
假設(shè)需要排序或者查找的總數(shù)N=10000000，那么我們需要申請內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對應(yīng)十進制數(shù)0-31，依次類推： 

1.求十進制0-N對應(yīng)在數(shù)組a中的下標(biāo)： n/32 

2.求0-N對應(yīng)0-31中的數(shù)： N%32=M

3.利用移位0-31使得對應(yīng)32bit位為1: 1<<M，并置1;

舉例 : 

如果想存儲 3 
(1) a下標(biāo) 30/ 32 = 0 ; 放在a[0] 中; 
(2) 3% 32 = 30; 
(3) 左移 30 位 01000000 00000000 00000000 00000000 這個對應(yīng)的值$a[0] = 1073741824 ; 


1.求十進制0-N對應(yīng)在數(shù)組a中的下標(biāo)： 
十進制0-31，對應(yīng)在a[0]中，先由十進制數(shù)n轉(zhuǎn)換為與32的余可轉(zhuǎn)化為對應(yīng)在數(shù)組a中的下標(biāo)。比如n=24,那么 n/32=0，則24對應(yīng)在數(shù)組a中的下標(biāo)為0。又比如n=60,那么n/32=1，則60對應(yīng)在數(shù)組a中的下標(biāo)為1，同理可以計算0-N在數(shù)組a中的下標(biāo)。 

2.求0-N對應(yīng)0-31中的數(shù)： 

十進制0-31就對應(yīng)0-31，而32-63則對應(yīng)也是0-31，即給定一個數(shù)n可以通過模32求得對應(yīng)0-31中的數(shù)。 

3.利用移位0-31使得對應(yīng)32bit位為1. 

找到對應(yīng)0-31的數(shù)為M, 左移M位：即2^M. 然后置1.

 由此我們計算10000000個bit占用的空間：

1byte = 8bit

1kb = 1024byte

1mb = 1024kb
占用的空間為：10000000/8/1024/1024mb。

大概為1mb多一些。
 
 */
 
 class bigMap {
	 //使用兩個字節(jié)保存 
	private $mask = 0x1f ;
	private $bitsperword = 32 ;
	// 移位的位數(shù)為5 pow(2,5) = 32 
	private $shift = 5 ;
	// 存儲數(shù)據(jù)的數(shù)組 
	 public $bitArray = array(); 
 
	 /**
	 $i 對應(yīng)的數(shù)歸零 
	 */
	 function clearbit($i){
		 ////則將當(dāng)前byte中的指定bit位取0，&后其他對方數(shù)組bit位必然不變，這就是 1 的妙用
		 // $i>>SHIFT 這里相當(dāng)于 intval($i /32) ;
		 // $i & $this->mask 這里相當(dāng)于 $i % $this->mask ,取余
		 @$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask)); 
	}
 
 	 /**
	 $i 對應(yīng)的數(shù)致1 
	 */
	 function setbit($i){
		 @$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask)); 
	}
 
 //test 測試所在的bit為是否為1 
 function testbit($i){ 
		return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask)); 
	} 	 
 }


$oBig = new bigMap() ; 

$oBig->setbit(30) ; 

var_dump($oBig->testbit(2)) ; 
var_dump($oBig->bitArray) ; 

echo decbin($oBig->bitArray[0]),"<br>";