#1024程序员节 | 征文#
位图概念
位图(bitmap),又称位数组或位向量,是一种数据结构。它利用连续的位(bit)来高效地表示一组布尔值(即0和1)。在位图中,每一位都对应一个可能的元素或状态,通过将该位设置为1或0来表示该元素是否存在或某个状态是否激活。
适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
面试题:
给40亿个不重复的无符号整数,未排过序。给一个无符号整数,如何快速判断这个数是否在这40亿个数中?
给出以下方法:
- 遍历O(N)。
- 排序O(N log_2 N)+二分查找O(log_2 N)。
- set O(log_2 N)、unordered_set O(1)。
以上方法都有一个问题,数据量太大,放不到内存中。40亿个无符号整数,约占用16G内存
位图解决思路:
将数据使用直接定址法映射到数组相应的位置。时间复杂度O(1)。
数组要开多大的空间呢?
开数据范围大小的空间,才能满足所有的数据都能映射到相应的位置。
无符号整数的取值范围为0~4294967295(2^32-1)。所以要开2^32个空间。
开2^32个整型大小的空间(约16G)吗?空间还是不够。数据是否在给定的整型数据中,结果是在或不在,正好是两种状态,使用标志位来表示数据的状态即可,每一位都对应一个元素的状态,此时,只需要开2^32个位大小的空间(约16G/4*32=500MB)
实现位图
bitmap()
- 给所有整数开空间
数组可以定义的最小单位是Byte,并不是bit位。我们数组中依旧存放int类型,一个int占4个Byte,32个bit位。
namespace zxa
{class bitmap{public:bitmap(size_t N){_bits.resize(N, 0);//error_num = 0;}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};
}
_bits.resize(N, 0);//error
这样并不是开N个位大小的空间,而是开了N个整型大小的空间。比如N=100时,我们是想开100个bit位来表示这100个整数在不在的状态,此时,却开了100个int,3200bit的大小。
_bits.resize(N / 32, 0);//error
这样也不对,比如N在0~32个之间(不包括32),那么一个Byte都没有开出来。比如,N=100时,开了100/32=3个int、3*4*8=96bit位的大小,但是,如果整数为97~99,要映射哪个位置?就越界了。
_bits.resize(N / 32 + 1, 0);
永远多开1个int、32bit大小的空间。
set()
- 将整数x映射的位置置为1
注意:数组中存放的是一个一个整型,而不是一个位一个位存的。
//将x映射的位置置为1
void set(size_t x)
{size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将该位置为1
}
reset()
- 将整数x映射的位置置为0。
注意:不排除删除了x之后,又删除x。(也就是x映射的位置本来就为0,又将x映射位置置为0)
//将x映射的位置置为0
void reset(size_t x)
{size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以
}
test()
- 判断整数x在不在。(也就是判断x映射的位置是否为1)
//判断x在不在(x映射的位置是否为1)
bool test(size_t x)
{size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);
}
完整代码+测试
bitmap.hpp:
#pragma once
#include<vector>namespace zxa
{class bitmap{public://给N个整数开空间bitmap(size_t N){//_bits.resize(N, 0);//_bits.resize(N / 32, 0);_bits.resize(N / 32 + 1, 0);_num = 0;}//将x映射的位置置为1void set(size_t x){size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将将该位置为1}//将x映射的位置置为0void reset(size_t x){size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以}//判断x在不在(x所在位是否为1)bool test(size_t x){size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};void test_bitmap();
}
test.cpp:
#define _CRT_SECURE_NO_WARNINGS
#include"bitmap.hpp"//测试,以100个无符号整数为例
void zxa::test_bitmap()
{bitmap bm(100);bm.set(99);bm.set(98);bm.set(95);bm.reset(98);for (size_t i = 0; i < 100; i++){printf("[%d]:%d\n", i, bm.test(i));}
}
int main()
{zxa::test_bitmap();return 0;
}
结果:
对于一开始的面试题,40亿个整数理论都存在文件中,然后从文件中读取,这里不是很好做演示。
补充
表示整数2^32
表示整数 2^32 (4,294,967,296)的方式。
unsigned long long x = 1;
for (size_t i = 0; i < 32; ++i)
{x *= 2;
}
bitmap bm(x);
bitmap bm(-1);
bitmap bm(0Xffffffff);
bitmap bm(pow(2, 32));
位运算基本运算规则
- 按位与 &: 全1为1,有0则0。
- 按位或 |: 有1则1,全0为0。
- 按位异或 ^: 相同为0,相异为1。
- 按位取反 ~:1取反为0,0取反为1。
- 左移 <<: 将一个二进制数的所有位向高位移动指定的位数。
- 右移 >>: 将一个二进制数的所有位向低位移动指定的位数。
位运算都是针对的二进制位,左移右移不是左右方向移位,而是向高位移动。