三、位图实现
1.位图定义
位图只需要定义一个成员_bits即可，表明传入的数据个数：
1. #pragma once 2. #include<assert.h> 3. namespace delia 4. { 5. template<size_t N>//数据总数 6. class BitSet 7. { 8. private: 9. vector<int> _bits; 10. }; 11. }
2.构造
1个字节可以表示32个数在不在，因此只需要申请N/32+1个空间，向上取整
1. public: 2. BitSet() 3. { 4. _bits.resize(N/32+1,0)//向上取整，否则不够存，默认每一位标记为0 5. }
3.标记
只把该位置1，其他位都不变：
①计算x在位图中的第几个整数的第几个位置
②要把该位置1，就必须让该位和1按位或，且其他位都不能被改变
1. //标记 2. void Set(size_t x) 3. { 4. assert(x < N); 5. 6. //计算x映射的位在第i个整数 7. //计算x映射的位在这个整数的第j位 8. 9. size_t i = x / 32; 10. size_t j = x % 32; 11. 12. //_bits[i]的第j位标记为1，并且不影响其他位 13. _bits[i] |= (1 << j); 14. }
4.删除
只把该位置0，其他位都不变：
①计算x在位图中的第几个整数的第几个位置
②要把该位置0，就必须让该位和0按位与，且其他位都不能被改变
③把1左移j位再按位取反，就可以将该位置为0。
1. //删除 2. void Reset(size_t x) 3. { 4. assert(x < N); 5. 6. //计算x映射的位在第i个整数 7. //计算x映射的位在这个整数的第j位 8. 9. size_t i = x / 32; 10. size_t j = x % 32; 11. 12. //_bits[i]的第j位标记为0，并且不影响其他位， 13. _bits[i] &= (~(1 << j)); 14. }
5.检验在不在
①计算x在位图中的第几个整数的第几个位置
②返回该位和1左移j位置后相与的结果
1. //检验在不在 2. void Test(size_t x) 3. { 4. assert(x < N); 5. 6. //计算x映射的位在第i个整数 7. //计算x映射的位在这个整数的第j位 8. 9. size_t i = x / 32; 10. size_t j = x % 32; 11. 12. //如果第j位为1，结果是非0，非0为真 13. //如果第j位为0，结果是0，0为假 14. 15. return _bits[i] & (1 << j); 16. }
6.完整代码段
1. #pragma once 2. #include<assert.h> 3. #include<vector> 4. using namespace std; 5. 6. namespace delia 7. { 8. template<size_t N> 9. class BitSet 10. { 11. public: 12. BitSet() 13. { 14. _bits.resize(N/32+1,0)//向上取整，否则不够存，默认每一位标记为0 15. } 16. 17. //标记 18. void Set(size_t x) 19. { 20. assert(x < N); 21. 22. //计算x映射的位在第i个整数 23. //计算x映射的位在这个整数的第j位 24. 25. size_t i = x / 32; 26. size_t j = x % 32; 27. 28. //_bits[i]的第j位标记为1，并且不影响其他位 29. _bits[i] |= (1 << j); 30. } 31. 32. //删除 33. void Reset(size_t x) 34. { 35. assert(x < N); 36. 37. //计算x映射的位在第i个整数 38. //计算x映射的位在这个整数的第j位 39. 40. size_t i = x / 32; 41. size_t j = x % 32; 42. 43. //_bits[i]的第j位标记为0，并且不影响其他位， 44. _bits[i] &= (~(1 << j)); 45. } 46. 47. //检验在不在 48. void Test(size_t x) 49. { 50. assert(x < N); 51. 52. //计算x映射的位在第i个整数 53. //计算x映射的位在这个整数的第j位 54. 55. size_t i = x / 32; 56. size_t j = x % 32; 57. 58. //如果第j位为1，结果是非0，非0为真 59. //如果第j位为0，结果是0，0为假 60. 61. return _bits[i] & (1 << j); 62. } 63. private: 64. vector<int> _bits; 65. }; 66. 67. void test_BitSet() 68. { 69. BitSet<4294967295u>* bs=new BitSet<4294967295u>;//40亿个数据向上取整，即开辟2^32个bit位 70. } 71. }
四、位图应用
1.给定两个文件，这两个文件分别都有100亿个整数，现在只有1G内存，如何找两个文件交集？
方案（1）：依次读取第一个文件中的所有整数并标记映射到一个位图，再读取第二个文件中的所有整数，判断在不在位图，在就是交集中的书，不在就不是
方案（2）：依次读取第一个文件的所有证书标记映射为位图1，一次读取第二个文件的所有证书标记映射为位图2，再对两个位图进行相与，结果为1的位就是交集。
无论方案（1）还是方案（2），由于整数最多只有2^32=4294967295个，42亿多个，文件有100亿个数据，肯定有重复的，因此只需要开辟2^32个bit位就能覆盖到这100亿个数据。
2.给定100亿个整数，设计算法找到只出现一次的整数
方案：位图是一个bit位标记一个值，现在用两个bit位标记一个值，位图能标记32个值在不在，那么现在只能标记16个值在不在：
00 出现0次
01 出现1次
10 出现2次及以上
11 不考虑
最后找出01标记的整数
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. #include<assert.h> 4. #include<iostream> 5. #include<vector> 6. #include<bitset> 7. using namespace std; 8. 9. int main() 10. { 11. vector<int> v = { 3,67,259,1,7890,4,36,23 }; 12. 13. bitset<4294967295u>* bs1 = new bitset<4294967295u>; 14. bitset<4294967295u>* bs2 = new bitset<4294967295u>; 15. 16. for (auto e : v) 17. { 18. if (!bs1->test(e) && !bs2->test(e))//00->01，第一次出现 19. { 20. bs2->set(e); 21. } 22. else if (!bs1->test(e) && bs2->test(e))//01->10，第二次出现 23. { 24. bs1->set(e); 25. bs2->reset(e); 26. } 27. else if (bs1->test(e) && !bs2->test(e))//10->11，第三次出现 28. { 29. //不用处理 30. } 31. else//第四次出现 32. { 33. //不用处理 34. assert(false); 35. } 36. } 37. 38. for (size_t i = 0; i < 4294967295; i++) 39. { 40. if (!bs1->test(i) && bs2->test(i))//找01 41. { 42. cout << i << endl; 43. } 44. } 45. return 0; 46. }
3. 1个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
现在用两个bit位标记一个值，
00 出现0次
01 出现1次
10 出现2次
11 出现3次
最后找出01和10标记的，即出现1次和出现2次的整数
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. #include<assert.h> 4. #include<iostream> 5. #include<vector> 6. #include<bitset> 7. using namespace std; 8. 9. int main() 10. { 11. vector<int> v = { 3,67,259,1,7890,4,36,23 }; 12. 13. bitset<4294967295u>* bs1 = new bitset<4294967295u>; 14. bitset<4294967295u>* bs2 = new bitset<4294967295u>; 15. 16. for (auto e : v) 17. { 18. if (!bs1->test(e) && !bs2->test(e))//00->01，第一次出现 19. { 20. bs2->set(e); 21. } 22. else if (!bs1->test(e) && bs2->test(e))//01->10，第二次出现 23. { 24. bs1->set(e); 25. bs2->reset(e); 26. } 27. else if (bs1->test(e) && !bs2->test(e))//10->11，第三次出现 28. { 29. bs1->set(e); 30. } 31. else//第四次出现 32. { 33. //不用处理 34. assert(false); 35. } 36. } 37. 38. //找01或10 39. for (size_t i = 0; i < 4294967295; i++) 40. { 41. if ((!bs1->test(i) && bs2->test(i)) 42. || (bs1->test(i) && !bs2->test(i)) 43. { 44. cout << i << endl; 45. } 46. } 47. 48. return 0; 49. }
