位圖的介紹和模擬實現

@TOC

位圖的介紹

經典面試題：

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。

常用方法有：

1.先排序，在利用二分查找

2.將數據放到unorder_set中，利用find進行查找，判斷是否在這些數中

方法1的時間復雜度：排序O(NlogN),二分查找O(logN)

方法2的時間復雜度：O(N)

這2個方法都還可以，但是40億個無符號整數會占用內存約16GB，空間消耗非常的大，所以上面的2種方法就不行了。

那么用位圖來解決

數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態，那么可以使用一個二進制比

特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0代表不存在。

例如：

無符號整數是2^32個字節，也就是521MB的大小，空間消耗變得很小了。

位圖概念

位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來判斷某個

數據存不存在的。

位圖的應用

快速查找某個數據是否在一個集合中

排序

求兩個集合的交集、并集等

操作系統中磁盤塊標記

位圖使用

位圖的定義

方式一：構造1個16位的位圖，所有初始化位是0

bitset<16> foo;

方式二：構造1個16位的位圖，根據所給值初始化前n位

bitset<16> bar(0xf);

方式三：構造1個16位的位圖，根據字符串的0,1序列初始化

bitset<16> baz(string("1000001"));

打印出來的效果：

位圖的成員函數

void Testbiset2() { bitset<16> baz; baz.set(8); baz.set(10); cout << baz << endl; baz.reset(8);//清空第8位 cout << baz << endl; baz.flip(8);//反轉第8位 cout << baz << endl; cout << baz.size() << endl; cout << baz.any() << endl; cout << baz.none() << endl; cout << baz.all() << endl; }

位圖運算符的使用

1.bitset中對>>,<<重載過可以直接使用

bitset<8> baz; cin >> baz; cout << baz << endl;

2.對一些運算符的重載

賦值運算符：=

關系運算符：==、!=

復合賦值運算符：&=、|=、^=、<<=、>>=

單目運算符：~

bitset<4> foo(std::string("1001")); bitset<4> bar(std::string("0011")); cout << (foo ^= bar) << endl; // 1010 cout << (foo &= bar) << endl; // 0010 cout << (foo |= bar) << endl; // 0011 cout << (foo <<= 2) << endl; // 1100 cout << (foo >>= 1) << endl; // 0110 cout << (~bar) << endl; // 1100 cout << (bar << 1) << endl; // 0110 cout << (bar >> 1) << endl; // 0001 cout << (foo == bar) << endl; // false cout << (foo != bar) << endl; // true cout << (foo & bar) << endl; // 0010 cout << (foo | bar) << endl; // 0111 cout << (foo ^ bar) << endl; // 0101

3.opeartor[],直接對某位進行修改或訪問

bitset<4> bar; bar[1] = 1; bar[2] = bar[1]; cout << bar << endl;

位圖的模擬實現

構造函數

我們需要根據所給的N來構造N位的位圖，并且將位圖中的所有位初始化位0

1個整形是32個比特位，N位的位圖就是N/32，但是N可能不是32的整數倍還需要+1。

bitset() { _bits.resiez(N / 32 + 1,0); }

set、reset、filp

set設置位

設置位圖中指定位的方法：

1.計算出是第i個數的第j位

2.將1左移j位后和第i個位進行或運算

代碼如下：

void set(size_t pos) { assert(pos < N); //計算pos映射在第幾個數的多少位 int i = pos / 32; int j = pos % 32; _bits[j] |= (1 << j);//將該位置設為1 }

reset清空位

清空位圖中指定位的方法：

1.計算出是第i個數的第j位

2.將1左移j位再整體取反與第i個數相與

代碼如下：

void reset(size_t pos) { assert(pos < N); //計算pos映射在第幾個數的多少位 int i = pos / 32; int j = pos % 32; _bits[j] &= (~(1 << j));//左移取反在相與 }

filp反轉指定位

1.計算出是第i個數的第j位

2.將1左移j位后和第i個位進行異或運算

void filp(size_t pos) { assert(pos < N); int i = pos / 32; int j = pos % 32; _bits[j] ^= (1 << j);//左移在取反 }

size、count

size直接返回N即可

size_t size() { return N; }

count獲取位圖中設置位的個數

邏輯如下：

1.將原數n與n-1與運算得到新數n

2.判斷n是否為0，不為0繼續進行第1步

size_t count() { size_t count = 0; //將每個整數中1的個數累加起來 for (auto e : _bits) { int num = e; //計算整數num中1的個數 while (num) { num = num & (num - 1); count++; } } return count; //位圖中1的個數，即被設置位的個數 }

其他的接口博主就沒有實現，主要都是位運算的操作。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。