浅谈bitmap算法
久闻《编程珠玑》一书中提出的bitmap算法之大名,只是没有深入的去研究,今天下午有兴致研究一番,才知道其中的玄机奥秘,不亚于KMP算法之巧妙,下面就由浅入深的谈谈bitmap算法。
一、bitmap算法思想
32位机器上,一个整形,比如int a; 在内存中占32bit位,可以用对应的32bit位对应十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询.
优点:1.运算效率高,不许进行比较和移位;2.占用内存少,比如N=10000000;只需占用内存为N/8=1250000Byte=1.25M。
缺点:所有的数据不能重复。即不可对重复的数据进行排序和查找。
比如:
第一个4就是
00000000000000000000000000010000
而输入2的时候
00000000000000000000000000010100
输入3时候
00000000000000000000000000011100
输入1的时候
00000000000000000000000000011110
思想比较简单,关键是十进制和二进制bit位需要一个map图,把十进制的数映射到bit位。下面详细说明这个map映射表。
二、map映射表
假设需要排序或者查找的总数N=10000000,那么我们需要申请内存空间的大小为int a[1 + N/32],其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:
bitmap表为:
a[0]--------->0-31
a[1]--------->32-63
a[2]--------->64-95
a[3]--------->96-127
..........
那么十进制数如何转换为对应的bit位,下面介绍用位移将十进制数转换为对应的bit位。
三、位移转换
例如十进制0,对应在a[0]所占的bit为中的第一位:
00000000000000000000000000000001
0-31:对应在a[0]中
i =0 00000000000000000000000000000000
temp=0 00000000000000000000000000000000
answer=1 00000000000000000000000000000001
i =1 00000000000000000000000000000001
temp=1 00000000000000000000000000000001
answer=2 00000000000000000000000000000010
i =2 00000000000000000000000000000010
temp=2 00000000000000000000000000000010
answer=4 00000000000000000000000000000100
i =30 00000000000000000000000000011110
temp=30 00000000000000000000000000011110
answer=1073741824 01000000000000000000000000000000
i =31 00000000000000000000000000011111
temp=31 00000000000000000000000000011111
answer=-2147483648 10000000000000000000000000000000
32-63:对应在a[1]中
i =32 00000000000000000000000000100000
temp=0 00000000000000000000000000000000
answer=1 00000000000000000000000000000001
i =33 00000000000000000000000000100001
temp=1 00000000000000000000000000000001
answer=2 00000000000000000000000000000010
i =34 00000000000000000000000000100010
temp=2 00000000000000000000000000000010
answer=4 00000000000000000000000000000100
i =61 00000000000000000000000000111101
temp=29 00000000000000000000000000011101
answer=536870912 00100000000000000000000000000000
i =62 00000000000000000000000000111110
temp=30 00000000000000000000000000011110
answer=1073741824 01000000000000000000000000000000
i =63 00000000000000000000000000111111
temp=31 00000000000000000000000000011111
answer=-2147483648 10000000000000000000000000000000
浅析上面的对应表:
1.求十进制0-N对应在数组a中的下标:
十进制0-31,对应在a[0]中,先由十进制数n转换为与32的余可转化为对应在数组a中的下标。比如n=24,那么 n/32=0,则24对应在数组a中的下标为0。又比如n=60,那么n/32=1,则60对应在数组a中的下标为1,同理可以计算0-N在数组a中的下标。
2.求0-N对应0-31中的数:
十进制0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。
3.利用移位0-31使得对应32bit位为1.
四、编程实现
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];//申请内存的大小
//set 设置所在的bit位为1
//clr 初始化所有的bit位为0
//test 测试所在的bit为是否为1
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main()
{ int i;
for (i = 0; i < N; i++)
clr(i);
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}
解析本例中的void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
1.i>>SHIFT:
其中SHIFT=5,即i右移5为,2^5=32,相当于i/32,即求出十进制i对应在数组a中的下标。比如i=20,通过i>>SHIFT=20>>5=0 可求得i=20的下标为0;
2.i & MASK:
其中MASK=0X1F,十六进制转化为十进制为31,二进制为0001 1111,i&(0001 1111)相当于保留i的后5位。
比如i=23,二进制为:0001 0111,那么
0001 0111
& 0001 1111 = 0001 0111 十进制为:23
比如i=83,二进制为:0000 0000 0101 0011,那么
0000 0000 0101 0011
& 0000 0000 0001 0000 = 0000 0000 0001 0011 十进制为:19
i & MASK相当于i%32。
3.1<<(i & MASK)
相当于把1左移 (i & MASK)位。
比如(i & MASK)=20,那么i<<20就相当于:
0000 0000 0000 0000 0000 0000 0000 0001 >>20
=0000 0000 0000 1000 0000 0000 0000 0000
4.void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }等价于:
void set(int i)
{
a[i/32] |= (1<<(i%32));
}
分享到:
相关推荐
在大数据查找算法中,Bitmap可以用来高效地进行数据过滤和查询,这是因为它的空间效率高,查找速度非常快。 首先,Bitmap的核心在于其数据结构。每个bit对应一个唯一的标识,比如在大数据集中的一个唯一ID。当某个...
C# 实现位图算法(BitMap) 位图算法(BitMap)是一种高效的数据结构,主要用于快速查询和存储大规模数据。下面将详细介绍 C# 中如何实现位图算法(BitMap)。 什么是 BitMap BitMap 的基本思想就是用一个 bit 位...
主要讲解bitmap存储,压缩,占用内存,以及内存的优化
基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法...Bitmap技术是一种能有效改善网络处理算法存储空间性能的通用技术,并给未来高性能网络处理算法设计提出以及现有算法的改进都提供了启发思路。
大数据处理算法目录中,主要介绍了三种大数据处理算法:Bitmap 算法、Bloom Filter 算法和分而治之/Hash 映射 + Hash 统计 + 堆/快速/归并排序。 大数据处理算法一:Bitmap 算法 Bitmap 算法是一种常用的大数据...
RoaringBitmap 算法是目前最先进的 Bitmap 算法,它可以高效地存储和查询大量的位图数据。 RoaringBitmap 算法将 bits 分组,每组 65535bit,然后对每组进行编码,编码后的长度为 32bit。 RoaringBitmap 算法可以...
### Bitmap 结构在高性能网络算法设计中的应用 在探讨Bitmap结构如何被应用于高性能网络算法设计之前,我们首先需要理解Bitmap(位图)的基本概念及其在数据处理中的优势。Bitmap是一种用于存储二进制数据的数据...
Bitmap算法,也称为位图,是一种高效的数据存储和检索技术,尤其适用于处理大量数据的场景。在C++中实现Bitmap算法通常涉及到对位操作的熟练掌握。以下是对Bitmap算法及其C++实现的详细解释。 1. **Bitmap算法基础*...
在Android开发中,Bitmap是处理图像数据的基本类,它用于表示位图图像。"bitmap上传图片demo"是一个示例项目,展示了如何利用Bitmap处理本地图片并进行上传,同时提供了将图片裁剪为圆形以适合作为头像的功能。在这...
此外,工程中的代码可能还会涉及错误处理和性能调优,例如检查设备方向,防止不必要的旋转,或者根据设备的硬件特性选择最适合的旋转算法。在实际应用中,我们需要考虑位图的大小和分辨率,因为旋转操作可能会显著...
类 EWAHBoolArray 是一个压缩的位集数据结构。 它通过模板参数(16 位、32 位、64 位)支持多种字大小。 您应该期望 64 位字大小提供更好的性能,但是 更高的内存使用率,而 32 位字大小的压缩可能会更好一些, 以...
位图算法
例如,改变某个像素的颜色或进行图像处理算法。 5. **与控件交互** - 在Windows Forms应用中,`Bitmap`可以与`PictureBox`控件结合显示图像。设置`PictureBox`的`SizeMode`属性以控制图像的显示方式。 - 可以将`...
在机器视觉领域,Halcon是一种广泛应用的图像处理软件,提供了丰富的图像处理算法和功能。而Bitmap图像则是一种常见的图像格式,广泛存在于Windows操作系统和其他多种环境中。在进行机器视觉项目时,有时我们需要将...
在Android开发中,Bitmap是处理图像的基本类,用于在内存中表示位图图像。当我们需要对图片进行裁剪、缩放或进行其他操作时,Bitmap提供了丰富的功能。本篇文章将详细探讨如何在Android环境下利用Bitmap来切割图片。...
在Android开发中,Activity之间的数据传递是常见的操作,特别是在处理图像数据时,如Bitmap对象。Bitmap是Android系统中用于表示图像的重要类,它包含了图像的所有像素信息。在不同Activity之间传递Bitmap,通常是...
`drawBitmap(Bitmap bitmap, Rect src, Rect dst, Paint paint)`是`drawBitmap()`方法的一个重载版本,其参数含义如下: 1. **Bitmap bitmap**: 这是你要绘制的位图对象,通常是从资源文件、内存缓存或者直接创建的...
Bitmap类是.NET Framework中用于处理像素级别的图像的核心类,提供了丰富的功能来实现各种图像处理算法。以下将详细介绍标题和描述中提到的一些关键知识点,并提供相关的编程实现思路。 1. **彩色图像转灰度图像**...
"Android 中 Canvas 转换为 Bitmap" Android 中 Canvas 转换为 Bitmap 是一种常见的需求,especially 在需要将 Canvas 绘制的图形显示在 ImageView 中的情况下。在这篇文章中,我们将详细介绍如何将 Canvas 转换为 ...