1. bitset類 1.1 私有成員

位圖實(shí)際上就是一個(gè)指定比特位個(gè)數(shù)的連續(xù)內(nèi)存空間，所以可以用STL內(nèi)置的容器vector管理，除此之外，理論上任何類型都可以作為元素的類型，只不過(guò)為了容易理解，它的每個(gè)元素的類型被設(shè)定為char。

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),青陽(yáng)企業(yè)網(wǎng)站建設(shè),青陽(yáng)品牌網(wǎng)站建設(shè),網(wǎng)站定制,青陽(yáng)網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,青陽(yáng)網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

template// N個(gè)比特位	
class bitset
{private:
    vector_bits; // 以char為單位管理
};

1. bitset接口 1.1 構(gòu)造函數(shù)

構(gòu)造一個(gè)有N位的位圖，并將所有位初始化為0。

由于申請(qǐng)空間時(shí)的最小單位是char（1字節(jié)），也就是8個(gè)比特位。那么對(duì)于N個(gè)比特位，需要申請(qǐng)N/8+1個(gè)char型空間，因?yàn)镹可能不是8的整數(shù)倍。

申請(qǐng)N=20個(gè)比特位，需要20/8+1=3個(gè)char。

bitset()
{_bits.resize(N / 8 + 1, 0);
}

1.2 set

要把某個(gè)比特位變成1，首先要知道這個(gè)比特位在哪個(gè)位置。

1. 首先計(jì)算這個(gè)比特位在整個(gè)位圖中的第x個(gè)char；
2. 然后計(jì)算比特位在這個(gè)char的第y個(gè)位置；
3. 最后將1左移y位和第x個(gè)char或運(yùn)算。

void set(size_t pos)
{assert(pos< N);

    size_t x = pos / 8;		// 在x個(gè)char
    size_t y = pos % 8;		// 在這個(gè)char的第y個(gè)比特位
    _bits[x] |= (1<< y);	// 將這個(gè)比特位設(shè)為1
}

1.3 reset

要把某個(gè)比特位清空，即恢復(fù)到0狀態(tài)，首先要找到它的位置，和set的操作是一樣的，只有最后一步不同：

1. 首先計(jì)算這個(gè)比特位在整個(gè)位圖中的第x個(gè)char；
2. 然后計(jì)算比特位在這個(gè)char的第y個(gè)位置；
3. 最后將1左移y位后，整體取反，再和第x個(gè)char與運(yùn)算。

注意：

使用~對(duì)左移后的1按位取反，而不是邏輯取反!。

void reset(size_t pos)
{assert(pos< N);

    size_t x = pos / 8;			// 在x個(gè)char
    size_t y = pos % 8;			// 在這個(gè)char的第y個(gè)比特位
    _bits[x] &= (~(1<< y));	// 將這個(gè)比特位設(shè)為0
}

1.4 flip

要把某個(gè)比特位取反，首先要找到它的位置：

1. 首先計(jì)算這個(gè)比特位在整個(gè)位圖中的第x個(gè)char；
2. 然后計(jì)算比特位在這個(gè)char的第y個(gè)位置；
3. 最后將1左移y位后，再和第x個(gè)char異或運(yùn)算。

void flip(size_t pos)
{assert(pos< N);

    size_t x = pos / 8;			// 在x個(gè)char
    size_t y = pos % 8;			// 在這個(gè)char的第y個(gè)比特位
    _bits[x] ^= (1<< y);		// 將這個(gè)比特位取反
}

1.5 test

同樣地：

1. 首先計(jì)算這個(gè)比特位在整個(gè)位圖中的第x個(gè)char；
2. 然后計(jì)算比特位在這個(gè)char的第y個(gè)位置；
3. 獲取某個(gè)位的狀態(tài)：
   • true：已被設(shè)置；
   • false：未被設(shè)置。

void test(size_t pos)
{assert(pos< N);

    size_t x = pos / 8;			// 在x個(gè)char
    size_t y = pos % 8;			// 在這個(gè)char的第y個(gè)比特位
    if (_bits[x] & (1<< y))	// 該位已被設(shè)置
        return true;
    else
        return false;
}

1.6 size、count

• size：獲取位圖中可以容納的位的個(gè)數(shù)。

直接返回模板參數(shù)N。

size_t size()
{return N;
}

• count：獲取位圖中被設(shè)置的位的個(gè)數(shù)。

要知道位圖中被設(shè)置為1的位的個(gè)數(shù)，就是遍歷整個(gè)位圖，統(tǒng)計(jì)1的個(gè)數(shù)。

1. 將當(dāng)前數(shù)x與x-1與運(yùn)算得到新的數(shù)x；
2. x是否為0：
   1. 為0：結(jié)束；
   2. 不為0：重復(fù)操作。

原因是每進(jìn)行一次操作1，都會(huì)將數(shù)x最右端的1消去。那么在x不為0之前，進(jìn)行了幾次消1操作就是位圖中1個(gè)個(gè)數(shù)。

size_t count()
{size_t count = 0;
    for (auto e : _bits)
    {char num = e;
        while (num)
        {num &= num - 1;
            count++;
        }
    }
    return count;
}

1.7 any、none、all

• any：判斷位圖中是否有任何位被設(shè)置。

只需要遍歷位圖中所有的比特位，一旦有1則返回true，否則返回0。但也可以不用這么干，因?yàn)橐粋€(gè)char里只要有一個(gè)不為0，整個(gè)char就是其他字符。ASCII=0對(duì)應(yīng)的字符時(shí)'\0'，但是它一般用在字符串處理中，個(gè)人認(rèn)為在這里還是將0強(qiáng)轉(zhuǎn)為char比較合適。

bool any()
{for (auto e : _bits)
    {if (e != (char)0)
            return true;
    }
    return false;
}

• none：判斷位圖中是否全部位都沒(méi)有被設(shè)置。

直接復(fù)用any的代碼，它們是互斥的。

bool none()
{return !any();
}

• 判斷位圖中是否全部位都被設(shè)置。

判斷全部位置都被設(shè)置為1，分為兩步：

1. 判斷所有完整的char中8個(gè)比特位是否都為1；
2. 判斷剩下（可能）不完整的char的所有比特位是否都為1。

同樣地，第一步中可以判斷這個(gè)char是否等于比特位全為1對(duì)應(yīng)的字符，也就是(char)127，遍歷剩下的比特位是否為1即可。

bool all()
{size_t size = _bits.size();
    for (size_t i = 0; i< size - 1; i++)	// 前size-1個(gè)完整的char
    {if (_bits[i] != (char)127)
            return false;
    }
    for (size_t i = 0; i< N % 8; i++)		// 最后一個(gè)char的剩下位
    {if ((_bits[size - 1] & (1<< i)) == (char)0)
            return false;
    }
    return true;
}

1.8 打印函數(shù)

這不是bitset內(nèi)置的成員函數(shù)，因?yàn)镾TL中重載了流輸入>>和流輸出<<運(yùn)算符，可以直接打印bitset中的內(nèi)容，而模擬實(shí)現(xiàn)并未重載它們，所以用打印函數(shù)輸出容器內(nèi)容。

思路和上一個(gè)很類似，也是分批打印：

void Print()
{string ret = "";
    size_t size = _bits.size();
    for (size_t i = 0; i< size - 1; i++)
    {for (size_t j = 0; j< 8; j++)
        {if (_bits[i] & (1<< j))
                ret += "1";
            else
                ret += "0";
        }
    }
    for (size_t j = 0; j< N % 8; j++)
    {if (_bits[size - 1] & (1<< j))
            ret += "1";
        else
            ret += "0";
    }

    cout<< ret<< endl;
}

2. bitset測(cè)試

void bitset_test1()
{xy::bitset<30>bs1;
	bs1.set(8);
	bs1.set(9);
	bs1.set(7);
	bs1.set(27);
	bs1.set(20);
	bs1.Print();
	cout<< bs1.count()<< endl;

	bs1.reset(8);
	bs1.reset(9);
	bs1.reset(20);
	bs1.Print();

	cout<< bs1.count()<< endl;
	cout<< bs1.any()<< endl;

	bs1.reset(7);
	bs1.reset(27);
	bs1.Print();
	cout<< bs1.none()<< endl;
}

輸出：

000000011100000000001000000100
5
000000010000000000000000000100
2
1
000000000000000000000000000000
1

源代碼

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：bitset（C++實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://chinadenli.net/article14/cejpde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、App開(kāi)發(fā)、軟件開(kāi)發(fā)、網(wǎng)站導(dǎo)航、網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)