bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte 的空间,将这些空间的所有Bit位都置为0(如下图:)
然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0x01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为一(如下图):
然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:
然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。下面的代码是用C语言实现的BitMap。
- bitmap.h
- /*
- *bitmap的c语言实现
- *作者:bitileaf
- *时间:2010-12-18 14:12
- */
- #ifndef _BITMAP_H_
- #define _BITMAP_H_
- /*
- *功能:初始化bitmap
- *参数:
- *size:bitmap的大小,即bit位的个数
- *start:起始值
- *返回值:0表示失败,1表示成功
- */
- int bitmap_init(int size, int start);
- /*
- *功能:将值index的对应位设为1
- *index:要设的值
- *返回值:0表示失败,1表示成功
- */
- int bitmap_set(int index);
- /*
- *功能:取bitmap第i位的值
- *i:待取位
- *返回值:-1表示失败,否则返回对应位的值
- */
- int bitmap_get(int i);
- /*
- *功能:返回index位对应的值
- */
- int bitmap_data(int index);
- /*释放内存*/
- int bitmap_free();
- #endif
- bitmap.c
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include "bitmap.h"
- unsigned char *g_bitmap = NULL;
- int g_size = 0;
- int g_base = 0;
- int bitmap_init(int size, int start)
- {
- g_bitmap = (char *)malloc((size/8+1)*sizeof(char));
- if(g_bitmap == NULL)
- return 0;
- g_base = start;
- g_size = size/8+1;
- memset(g_bitmap, 0x0, g_size);
- return 1;
- }
- int bitmap_set(int index)
- {
- int quo = (index-g_base)/8 ;
- int remainder = (index-g_base)%8;
- unsigned char x = (0x1<<remainder);
- if( quo > g_size)
- return 0;
- g_bitmap[quo] |= x;
- return 1;
- }
- int bitmap_get(int i)
- {
- int quo = (i)/8 ;
- int remainder = (i)%8;
- unsigned char x = (0x1<<remainder);
- unsigned char res;
- if( quo > g_size)
- return -1;
- res = g_bitmap[quo] & x;
- return res > 0 ? 1 : 0;
- }
- int bitmap_data(int index)
- {
- return (index + g_base);
- }
- int bitmap_free()
- {
- free(g_bitmap);
- }
- 测试程序bitmap_test.c:
- #include <stdio.h>
- #include "bitmap.h"
- int main()
- {
- int a[] = {5,8,7,6,3,1,10,78,56,34,23,12,43,54,65,76,87,98,89,100};
- int i;
- bitmap_init(100, 0);
- for(i=0; i<20; i++)
- bitmap_set(a[i]);
- for(i=0; i<100; i++)
- {
- if(bitmap_get(i) > 0 )
- printf("%d ", bitmap_data(i));
- }
- printf("/n");
- bitmap_free();
- return 0;
- }
执行结果:
[root@localhost bitmap]# make
gcc -c -o bitmap_test.o bitmap_test.c
gcc bitmap.o bitmap_test.o -o bitmap
[root@localhost bitmap]# ./bitmap
1 3 5 6 7 8 10 12 23 34 43 54 56 65 76 78 87 89 98 100
bitmap在对数据进行排序时,其复杂度为O(n)。当然这是拿空间换来的。与bitmap类似的还有Bloom filter,Bloom filter可以看做是对bit-map的扩展。
【问题实例】
1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)
2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个 2bit-map,都是一样的道理。
相关推荐
bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 适用范围:可进行数据的快速查找,...
c语言实现的位图bitmap,简单易用,如有更多需要,可以方便添加新的操作。
Bitmap方法C语言实现,支持插入、删除和查找功能。
树操作【中】 算法系列15天速成——第十一天 树操作(上) 算法系列15天速成——第十天 栈 算法系列15天速成——第九天 队列 算法系列15天速成——第八天 线性表【下】 算法系列15天速成——第七天 线性表【上】 ...
位图可以节省内存资源,而C语言又是高效的编程语言
BMP(Bitmap-File)图形文件是Windows采用的图形文件格式,在Windows环境下运行的所有图象处理软件都支持BMP图象文件格式。Windows系统内部各图像绘制操作都是以BMP为基础的。Windows 3.0以前的BMP图文件格式与显示...
主要介绍了C语言实现的bitmap位图代码分享,位图(bitmap)是一种非常常用的结构,在索引、数据压缩等方面有广泛应用,需要的朋友可以参考下
主要介绍了C语言实现BMP转换JPG的方法,涉及C#图片格式转换的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
Android开发者学习笔记——View、Canvas、bitmap
机器视觉技术必备,从位图到halcon图像,bitmap图像转为halcon图像,bitmap to Hobject
Halcon_Bitmap转换方法 写的文档 开发笔记
用C语言读取BITMAP文件,此源码默认读取当前目录下的1.bmp。可以改成处理其他BMP文件。
Bitmap位图旋转范例 一个完整工程
BMP2H264 Bitmap图像转换为H264
一个在VC中将Bitmap转换为Byte[]的小例子。
改用原始图像数据流回调函数RegisterImageStreamCallback进行抓图 但回调函数帧为YUV420格式 需要转成Bitmap才用用于显示及本地查看 在网上找了好多都是基于R Y+1 4075 V 128 G Y 0 3455 U 128 – 0 7169 V 128 B Y+...
输入一串字符串 自动生成bitmap 和exe同一目录下, 几乎包含所有的编码方式