例题1
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。
首先肯定不能用传统的int数据存储 因为内存不够 40亿的整数大概为16G左右
思路1： 因为byte位数据小 1字节就有8个byte 那么40亿byte数据大概只有500mb左右
template//先开好总有数据大小 class moxuan_bit { public: //开空间 moxuan_bit() { //char类型有8个字节 所以N个数据就/8即可 假如开10 只开了一个char 不够 所以 //要+1 _bits.resize(N / 8 + 1, 0); } //把x映射的位置标记成1 表示存在 void set(size_t x) { //计算在第几个char范围内 size_t i = x / 8; //计算在第i个char范围内的第几个 size_t j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { //计算在第几个char范围内 size_t i = x / 8; //计算在第i个char范围内的第几个 size_t j = x % 8; //将第j个数改为1 然后取反 其他bit位变为1 j的数变为0 //这时候 按位与 其他比特位为不变 j的比特位为0 就删除了这个值不存在 _bits[i] &= (~(1 << j)); } bool test(size_t x) { //计算在第几个char范围内 size_t i = x / 8; //计算在第i个char范围内的第几个 size_t j = x % 8; //如果跟1是相同 就返回1 true 如果跟1不相同 就返回0 false //并且不是&= 不会改变里面的值 return _bits[i] & (1 << j); } private: std::vector<char> _bits; };
测试：
void test1() { moxuan_bit<100> v; v.set(20); v.set(77); v.set(0); cout << v.test(20) << " " << v.test(77) << " " << v.test(0) << endl; v.reset(0); cout << v.test(20) << " " << v.test(77) << " " << v.test(0) << endl; }
例题2：
. 给定100亿个整数，设计算法找到只出现一次的整数？
思路 ：用两个位图表示 大概数据量为 1G
template
class two_bit
{
public:
void set(size_t x)
{
//返回它的状态 1或 0
int in1 = bit1.test(x);
int in2 = bit2.test(x);
//当两个都为0 状态改为 0 1
if (in1 == 0 && in2 == 0)
{
bit2.set(x);
}
//当为 01 存在时 又遇到了 就改为 10 表示存在1次以上
else if(in1==0&&in2==1)
{
bit1.set(x);
bit2.reset(x);
}
}
//如果该值为 0 1 表示就存在过一次
bool is_once(size_t x)
{
return bit1.test(x) == 0 && bit2.test(x) == 1;
}
private:
//用两个位图表示3种状态 0 0 表示不存在 0 1 表示存在一次 1 0 表示存在一次以上
moxuan_bit bit1;
moxuan_bit bit2;
};
测试：
void test2() { two_bit<13> v1; int a[] = { 5,8,9,2,5,9,4,2,1,0,7,6,5 }; for (auto e : a) { v1.set(e); } for (int i = 0; i 10; i++) { if (v1.is_once(i)) { cout << i << " "; } } }
&按位与 ：
按位”与”运算符 (&) 会将第一操作数的每一位与第二操作数的相应位进行比较。如果两个位均为 1，则对应的结果位将设置为 1。否则，将对应的结果位设置为 0。
| 按位或：
按位”与或”运算符 (|) 将第一个操作数的每个位与第二个操作数的对应位进行比较。如果其中一个位是 1，则将对应的结果位设置为 1。否则，将对应的结果位设置为 0。
^ 按位异或：
按位”异或”运算符 (^) 将第一操作数的每个位与第二操作数的相应位进行比较。如果一个位是 0，另一个位是 1，则相应的结果位将设置为 1。否则，将对应的结果位设置为 0。
~取反：
若操作数为1 设置为0 若为1 则设置为1
>>右移 实际不是向右移动 而是向低位移动
<Original: https://www.cnblogs.com/LonelyMoNan/p/16697538.html
Author: lemon-Breeze
Title: 位图
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/607395/
转载文章受原作者版权保护。转载请注明原作者出处！