智慧团建网站登录平台手机版,文章修改网站,建设网站的工作,网件路由器和华硕路由器哪个好博文转载于http://www.cnblogs.com/dyllove98/archive/2013/07/26/3217741.html概述所谓bitmap就是用一个bit位来标记某个元素对应的value#xff0c;而key即是这个元素。由于采用bit为单位来存储数据#xff0c;因此在可以大大的节省存储空间算法思想 32位机器上#xff0c… 博文转载于http://www.cnblogs.com/dyllove98/archive/2013/07/26/3217741.html 概述 所谓bitmap就是用一个bit位来标记某个元素对应的value而key即是这个元素。由于采用bit为单位来存储数据因此在可以大大的节省存储空间 算法思想 32位机器上一个整形比如int a;在内存中占32bit可以用对应的32个bit位来表示十进制的0-31个数bitmap算法利用这种思想处理大量数据的排序与查询 优点 效率高不许进行比较和移位 占用内存少比如N10000000;只需占用内存为N/8 1250000Bytes 1.2M如果采用int数组存储则需要38M多 缺点 无法对存在重复的数据进行排序和查找 示例 申请一个int型的内存空间则有4Byte32bit。输入 4 2, 1, 3时 输入4 输入2 输入1 输入3 思想比较简单关键是十进制和二进制bit位需要一个map映射表把10进制映射到bit位上 map映射表 假设需要排序或者查找的总数N10000000,那么我们需要申请的内存空间为 int a[N/32 1].其中a[0]在内存中占32位,依此类推 bitmap表为 a[0] ------ 0 - 31 a[1] ------ 32 - 63 a[2] ------ 64 - 95 a[3] ------ 96 - 127 ...... 下面介绍用位移将十进制数转换为对应的bit位 位移转换 1 求十进制数0-N对应的在数组a中的下标 index_loc N / 32即可index_loc即为n对应的数组下标。例如n 76, 则loc 76 / 32 2,因此76在a[2]中。 2求十进制数0-N对应的bit位 bit_loc N % 32即可例如 n 76, bit_loc 76 % 32 12 3利用移位0-31使得对应的32bit位为1 代码示例(c语言) #include stdio.h #include stdlib.h #define SHIFT 5 #define MASK 0x1F /** * 设置所在的bit位为1 * * T O(1) * */ void set(int n, int *arr) { int index_loc, bit_loc; index_loc n SHIFT; // 等价于n / 32 bit_loc n MASK; // 等价于n % 32 arr[index_loc] | 1 bit_loc; } /** * 初始化arr[index_loc]所有bit位为0 * * T O(1) * */ void clr(int n, int *arr) { int index_loc; index_loc n SHIFT; arr[index_loc] 0; } /** * 测试n所在的bit位是否为1 * * T O(1) * */ int test(int n, int *arr) { int i, flag; i 1 (n MASK); flag arr[n SHIFT] i; return flag; } int main(void) { int i, num, space, *arr; while (scanf(%d, num) ! EOF) { // 确定大小动态申请数组 space num / 32 1; arr (int *)malloc(sizeof(int) * space); // 初始化bit位为0 for (i 0; i num; i ) clr(i, arr); // 设置num的比特位为1 set(num, arr); // 测试 if (test(num, arr)) { printf(成功\n); } else { printf(失败!\n); } } return 0; }
