這篇文章主要介紹了PHP中使用BigMap實(shí)例,本文直接給出實(shí)現(xiàn)代碼,代碼中包含詳細(xì)注釋,需要的朋友可以參考

<?php 
//所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。 
  
/* 
  
若 N =1 ; 申請(qǐng)內(nèi)存空間為 int a[2] ;  
假設(shè)需要排序或者查找的總數(shù)N=10000000，那么我們需要申請(qǐng)內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對(duì)應(yīng)十進(jìn)制數(shù)0-31，依次類推：  
  
1.求十進(jìn)制0-N對(duì)應(yīng)在數(shù)組a中的下標(biāo)： n/32  
  
2.求0-N對(duì)應(yīng)0-31中的數(shù)： N%32=M 
  
3.利用移位0-31使得對(duì)應(yīng)32bit位為1: 1<<M，并置1; 
  
舉例 :  
  
如果想存儲(chǔ) 3  
(1) a下標(biāo) 30/ 32 = 0 ; 放在a[0] 中;  
(2) 3% 32 = 30;  
(3) 左移 30 位 01000000 00000000 00000000 00000000 這個(gè)對(duì)應(yīng)的值$a[0] = 1073741824 ;  
  
  
1.求十進(jìn)制0-N對(duì)應(yīng)在數(shù)組a中的下標(biāo)：  
十進(jìn)制0-31，對(duì)應(yīng)在a[0]中，先由十進(jìn)制數(shù)n轉(zhuǎn)換為與32的余可轉(zhuǎn)化為對(duì)應(yīng)在數(shù)組a中的下標(biāo)。比如n=24,那么 n/32=0，則24對(duì)應(yīng)在數(shù)組a中的下標(biāo)為0。又比如n=60,那么n/32=1，則60對(duì)應(yīng)在數(shù)組a中的下標(biāo)為1，同理可以計(jì)算0-N在數(shù)組a中的下標(biāo)。  
  
2.求0-N對(duì)應(yīng)0-31中的數(shù)：  
  
十進(jìn)制0-31就對(duì)應(yīng)0-31，而32-63則對(duì)應(yīng)也是0-31，即給定一個(gè)數(shù)n可以通過模32求得對(duì)應(yīng)0-31中的數(shù)。  
  
3.利用移位0-31使得對(duì)應(yīng)32bit位為1.  
  
找到對(duì)應(yīng)0-31的數(shù)為M, 左移M位：即2^M. 然后置1. 
  
 由此我們計(jì)算10000000個(gè)bit占用的空間： 
  
1byte = 8bit 
  
1kb = 1024byte 
  
1mb = 1024kb 
占用的空間為：10000000/8/1024/1024mb。 
  
大概為1mb多一些。 
   
 */ 
   
 class bigMap { 
     //使用兩個(gè)字節(jié)保存  
    private $mask = 0x1f ; 
    private $bitsperword = 32 ; 
    // 移位的位數(shù)為5 pow(2,5) = 32  
    private $shift = 5 ; 
    // 存儲(chǔ)數(shù)據(jù)的數(shù)組  
     public $bitArray = array();  
   
     /** 
     $i 對(duì)應(yīng)的數(shù)歸零  
     */ 
     function clearbit($i){ 
         ////則將當(dāng)前byte中的指定bit位取0，&后其他對(duì)方數(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 對(duì)應(yīng)的數(shù)致1  
     */ 
     function setbit($i){ 
         @$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask));  
    } 
   
 //test 測(cè)試所在的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>";