1. bitset類 1.1 私有成員

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

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

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

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

構造一個有N位的位圖，并將所有位初始化為0。

由于申請空間時的最小單位是char（1字節(jié)），也就是8個比特位。那么對于N個比特位，需要申請N/8+1個char型空間，因為N可能不是8的整數(shù)倍。

申請N=20個比特位，需要20/8+1=3個char。

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

1.2 set

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

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

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

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

1.3 reset

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

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

注意：

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

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

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

1.4 flip

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

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

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

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

1.5 test

同樣地：

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

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

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

1.6 size、count

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

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

size_t size()
{return N;
}

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

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

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

原因是每進行一次操作1，都會將數(shù)x最右端的1消去。那么在x不為0之前，進行了幾次消1操作就是位圖中1個個數(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：判斷位圖中是否有任何位被設置。

只需要遍歷位圖中所有的比特位，一旦有1則返回true，否則返回0。但也可以不用這么干，因為一個char里只要有一個不為0，整個char就是其他字符。ASCII=0對應的字符時'\0'，但是它一般用在字符串處理中，個人認為在這里還是將0強轉為char比較合適。

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

• none：判斷位圖中是否全部位都沒有被設置。

直接復用any的代碼，它們是互斥的。

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

• 判斷位圖中是否全部位都被設置。

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

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

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

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

1.8 打印函數(shù)

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

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

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測試

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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章標題：bitset（C++實現(xiàn)）-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://www.rwnh.cn/article14/cejpde.html

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

廣告

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