引子：

在虞城等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì) 網(wǎng)站設(shè)計(jì)制作按需求定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站建設(shè),全網(wǎng)整合營(yíng)銷推廣,成都外貿(mào)網(wǎng)站制作,虞城網(wǎng)站建設(shè)費(fèi)用合理。

    給40億個(gè)不重復(fù)的無符號(hào)整數(shù)，沒排過序，給一個(gè)無符號(hào)整數(shù)，如何判斷這個(gè)數(shù)是否在這40億個(gè)數(shù)中。

    分析：1 字節(jié)=8位

          1 KB  =1024字節(jié)=2^10字節(jié)

          1 MB  =1024KB

          1 GB  =1024MB

    40億個(gè)數(shù)，40億可以約看為2^32，即需要將近4G的空間存儲(chǔ)，，如果內(nèi)存夠的話，40億個(gè)整數(shù)使用位圖存儲(chǔ)需要500M的空間

    位圖即每一個(gè)位存儲(chǔ)，如果這個(gè)數(shù)存在，則先找到這個(gè)字節(jié)大小，再將字節(jié)的這個(gè)位置1

template<class T> 
class BitMap
{
public:
	BitMap(size_t n)
		:_size(0)
	{
		_a.resize((n>>5)+1);//map存儲(chǔ)數(shù)據(jù)時(shí)是按位存儲(chǔ)，n>>5即n/32
	}
	void set(size_t x)//置位
	{
		size_t index = x >> 5;//即x/32
		size_t num = x % 32;
		
		if ((_a[index] & (1 << num)) == 0)//先判斷當(dāng)前位是否已被置1，若還沒被置1，則_size++且置1
		{
			_size++;
			_a[index] |= (1 << num);
		}
	}
	void Reset(size_t x)//取消置位
	{
		size_t index = x >> 5;
		size_t num = x % 32;
		
		if ((_a[index] & (1 << num)) != 0)//若當(dāng)前位不為0則_size--后置0
		{
			_size--;
			_a[index] &= ~(1 << num);
		}
		
	}
	int test(size_t x)
	{
		size_t index = x >> 5;
		size_t num = x % 32;
		
		return _a[index] & (1 << num);
	}
private:
	vector<T>_a;
	size_t _size;
	 
};

未完待續(xù)

名稱欄目：位圖BitMap
文章轉(zhuǎn)載：http://chinadenli.net/article22/gdjicc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、App開發(fā)、Google、品牌網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)