位图
今天我们所介绍的数据结构叫做位图,在谈什么是位图之前我们先来看一道"非常简单的题":有40亿个无符号的整型数据,现在给定一个目标数字,判断这个数字是否在这40亿数据中。题目看起来确实非常简单,有的同学说直接遍历一遍不就ok了吗?还有的同学给出了更高效的查找方式就是将这些数字排序然后进行二分查找。但是,这是有问题的,问题并不在于你搜索这个数字的效率问题,而是你在遍历也好排序也罢,这些数字在内存中放的下么?
一个整型int就是4个字节,10亿个int差不多已经需要4G的内存了,40亿个int就是16G。所以这里方法行不通的根本原因实际上是内存不够,但是我们今天的讲的位图却能很好的帮助我们处理这个问题。
位图模型
既然根本原因是这些数据用int放不下,那么是否有更小的东西标记这些数字呢?没错,有的同学想到了,char只占一个字节或许能表示一个数字,但是随着数字位数的增多,依旧不可能使用一个字符表示一个数字,这就意味着小于4G内存还是不能解决这个问题。
其实说到这里,我们的问题就转化为如何使用更小的内存单元来标记一个数字,而在程序中我们最小的访问单位的bit位,所以现在我们一起来看使用比特位如何标记(映射)这些数据。
现在我们发现,4个字节本来只能存储一个int,而现在使用位图我们就存了(映射)32个数字,意味着16G/32约等于500m左右我们就能映射这些数据,那么这些数据是怎么映射到位图种的呢?接着看。
设计位图
为了方便,我们将位图用一个数组表示,让vector帮我们开辟一段连续的空间,我们只负责将数据设置或者移除就行。
class BitMap
{
public:
BitMap(size_t range)
{
//右移5位相当于除以32,加1是因为小于32的数字如果与32相除则得到0
_bitTable.resize((range >> 5) + 1);
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
位图元素的设置
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}
1
2
3
4
5
6
7
来看看为什么需要size_t index = x >> 5和size_t num = x % 32两步操作:我们看看要映射5和32这俩个数
5表示防在第1个整型空间的第5位上,32则表示放在第2个整型空间第一位上。而**bitTable[index] |= (1 << num)**能保证把第num位上的数字设置为1,其余数字保持不变。
位图元素的移除
比较简单,需要知道的是**~(1 << num)**表示出了num位为0,其余位都为1.
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num);
}
1
2
3
4
5
6
7
位图元素的查找
这个没啥好说的,很简单,说到这里,你的位图也就实现完了,非常简单把
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}
1
2
3
4
5
6
7
完整代码:
class BitMap
{
public:
BitMap(size_t range)
{
_bitTable.resize((range >> 5) + 1);
}
//标识一个数字在位图中的位置
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}
//取消数字在位图当中的标识.
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num);
}
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
拓展
现在将问题修改为让你寻找出40亿个数据中出现过两次的数据,此时我们就需要使用两位来标记同一个数据了。
N位位图的实现如下:
class NBitMap
{
public:
NBitMap(size_t range)
{
_bitTable.resize((range >> 4) + 1);
}
void SetBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
bool first = _bitTable[index] & (1 << num);
bool second = _bitTable[index] & (1 << (num + 1));
if (!(first && second))
{
_bitTable[index] += (1 << num);
}
}
bool TestBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
return (_bitTable[index] >> num) & 0x03;
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
相关推荐
Oracle 数据库的位图索引原理与应用 Oracle 数据库中的位图索引是一种特殊类型的索引,主要用于解决查询优化问题。 在实际应用中,列值重复率高的情况非常常见,使用 B 树索引效果不佳。在这种情况下,位图索引就成...
本文将深入探讨透明位图的显示原理以及如何在MFC应用中实现这一功能。 首先,Windows API 提供了一个名为`TransparentBlt`的函数,它可以方便地处理具有透明区域的位图。这个函数在Windows 98/Windows 2000及以上...
**BMP位图显示原理详解** BMP(Bitmap)是一种常见的图像文件格式,广泛应用于Windows操作系统及许多其他软件中。这种格式存储了像素数据,使得计算机可以将其转换为屏幕上可见的图像。理解BMP位图的显示原理对于...
在Java编程语言中,解析BMP(Bitmap)位图文件是一项常见的图像处理任务。BMP是一种无损的图像文件格式,广泛应用于Windows操作系统和许多其他软件中。它以未经压缩的二进制形式存储图像数据,因此解析BMP文件可以...
这对于理解工作原理、调试或定制功能非常有帮助。 3. **NotifySys**:通常是指Windows系统通知消息,用于在系统事件发生时通知应用程序,比如窗口状态改变、定时器触发等。在位图句柄取位图模块中,可能涉及到系统...
位图文件(BMP)是Windows操作系统广泛使用的图形文件格式,它包含了图像的像素数据以及关于图像的一些元信息。BMP文件分为两种主要类型:设备相关位图(DDB)和设备无关位图(DIB)。DDB格式与特定的显示设备相关联...
图像处理\用Visual C++显示位图 的原理与方法.pdf
总的来说,从彩色位图到单色位图的转换涉及了图像处理的基本原理和Windows API的使用。在VC环境下,我们可以利用GDI提供的丰富函数实现这一过程,并结合截图和文件操作功能,生成所需要的位图数据文件。这个过程不仅...
CPU原理角位图是用于描述处理器内部电路布局和信号传输路径的图形表示,对于理解芯片的工作机制和进行硬件设计具有重要意义。 MTK6226的CPU部分可能基于ARM7TDMI架构,这是一种古老的但极其可靠的RISC(精简指令集...
首先,我们需要理解位图的基本原理。位图是由像素阵列构成的,每个像素有自己的颜色值,通常用RGB(红绿蓝)三原色表示。位图文件头包含图像的宽度、高度、颜色深度等信息。在Windows系统中,我们可以使用GDI...
用Visual C++显示位图的原理与方法 <<电脑编程技巧与维护 >>2001年01期 王丰 <br>一、介绍 在VC++环境下显示位图并不是什么新技术,但本文仍然在此"老调重弹"的原因是:(1)这一技术十分重要,它是图像编程的...
位图动画程序是一种将一系列静态位图图像组合起来,通过快速连续播放来形成动态效果的技术。在计算机图形学中,位图...通过理解和实现这样的程序,开发者可以深入理解图形编程的基本原理,并提升其C++编程技能。
8583位图计算器的工作原理是这样的:当你输入一个8583报文的BITMAP字段,计算器会根据ISO 8583标准解析出每个位所代表的字段,并展示出来。这使得用户能够快速理解哪些字段包含信息,而哪些没有。这对于调试、数据...
总之,位图马赛克化的原理并不复杂,主要通过像素区域的平均处理来实现。在VC6.0中,结合Windows GDI库,我们可以轻松地编写代码实现这一特效。通过理解和实践,不仅可以掌握马赛克化的具体实现,还能对图像处理和...
通过分析和理解这些代码,我们可以深入学习到图像处理的基本原理和编程技术,以及如何在实际项目中应用这些知识。同时,这样的转换过程在游戏开发、嵌入式系统和移动设备的图形处理中非常常见。
在 VC++ 中,实现透明位图的显示需要了解位图内存和视频内存的原理。位图操作涉及到视频内存和位图内存,每次图形操作都会影响视频内存。位图驻留在位图内存中,如果被移到视频内存,则将显示在监视器上。 二、实现...
下面我们将深入探讨掩码位图的原理、如何在VC++中实现透明图片的制作以及相关的图形处理知识。 首先,了解掩码的基本概念。掩码通常是一个黑白位图,黑色代表透明,白色代表不透明。当我们将掩码与目标图像进行“与...
首先,理解Windows编程的基本原理至关重要。Windows API提供了一组函数,允许开发者直接与操作系统交互,创建窗口、处理消息以及绘制图形,包括位图。C++本身并不直接支持图形处理,因此我们需要借助Windows API来...
二、位图比较原理 位图比较通常涉及比较两个位图的每一个像素,检查它们的颜色值是否相同。如果存在不同,记录下这些像素的坐标。由于24位和32位位图的颜色深度不同,比较时需要考虑Alpha通道的存在与否。 三、VB...
在理解这个工具的工作原理之前,我们需要了解位图(Bitmap)的基本概念。位图是一种常见的图像文件格式,它存储像素颜色信息的二维矩阵。每个像素由一个或多个字节表示,取决于位深度(色彩深度),例如8位灰度图像...