数据结构之位图（bitmap）详解

1.  概述

位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用。本文介绍了位图的实现方法及其应用场景。

2. 位图实现

（1）自己实现
在位图中，每个元素为“0”或“1”，表示其对应的元素不存在或者存在。

代码如下:

#define INT_BITS sizeof(int)
 
#define SHIFT 5 // 2^5=32
 
#define MASK 0x1f // 2^5=32
 
#define MAX 1024*1024*1024 //max number
 
int bitmap[MAX / INT_BITS];
 
/*
 
* 设置第i位
 
* i >> SHIFT 相当于 i / (2 ^ SHIFT),
 
* i&MASK相当于mod操作 m mod n 运算
 
*/
 
void set(int i) {
 
bitmap[i >> SHIFT] |= 1 << (i & MASK);
 
}
 
//获取第i位
 
int test(int i) {
 
return bitmap[i >> SHIFT] & (1 << (i & MASK));
 
}
 
//清除第i位
 
int clear(int i) {
 
return bitmap[i >> SHIFT] & ~(1 << (i & MASK));
 
}

（2）函数库实现

C++的STL中有bitmap类，它提供了很多方法，详见：http://www.cplusplus.com/reference/stl/bitset/

3.  位图应用

3.1    枚举
（1）全组合
字符串全组合枚举（对于长度为n的字符串，组合方式有2^n种），如：abcdef,可以构造一个从字符串到二进制的映射关系，通过枚举二进制来进行全排序。

代码如下:

null——> 000000
f——> 000001
e——> 000010
ef——> 000011
……
abcedf——> 111111

（2）哈米尔顿距离

枚举算法，复杂度是O(N^2)，怎样降低复杂度呢？
如果是N 个二维的点，那么我们可以怎么用较快的方法求出

通过简单的数学变形，我们可以得到这样的数学公式：

通过观察，我们发现每一对相同元的符号必定相反，如：x_i-y_i，于是我们有了一个二进制思想的思路，那就是枚举这些二i维的点的x 轴y 轴前的正负号，这样就可以用一个0~3 的数的二进制形式来表示每个元素前面的正负号，1表示+号，0表示−号，如：2 表示的二进制位形式为10表示x_i-y_i。这样我们就可以通过2^2*N次记录下这些二元组的不同的符号的数值，对于每个二进制来表示的不同的式子只需记录下他们的值，这样我们只需求max_i 和min_i出这些相同的二进制表示的式子max_i –min_i，最后我们就可以解出ans=max{max_i-min_i}。

通过位图，算法时间复杂度可将为O(N)。

3.2   搜索

设计搜索剪枝时，需要保存已经搜索过的历史信息，有些情况下，可以使用位图减小历史信息数据所占空间。

3.3 压缩

（1）在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数？

（2）腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

4. 总结

Bitmap是一种非常简洁快速的数据结构，他能同使证存储空间和速度最优化（而不必空间换时间）。

5.  参考资料
（1）《C实现bitmap位图》：http://www.jb51.net/article/54438.htm
（2）武森《浅谈信息学竞赛中的“0”和“1”》

赞 (0)

相关推荐

  • C语言实现的bitmap位图代码分享

    事实上,我们是用每一个 元素表示一个32位的二进制字符串,这样这个元素可以保留相邻32个号码是否存在的信息,数组范围就下降到10000000/32了.例如对于号码 89256,由于89256 mod 32=2789-8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1. #define WORD 32 #define SHIFT 5 ////移动5个位,左移则相当于乘以32,右移相当于除以32取整 #define MASK 0x1F //16进制下的31 #define N

  • Android Bitmap详细介绍

    复制代码 代码如下: package com.testbitmapscale; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.util.Iterator; import com.testbitmapscale.R.drawable; im

  • 海量数据处理系列之:用C++实现Bitmap算法

    bitmap是一个十分有用的结构.所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素.由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省. 适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码扩展:bloom filter可以看做是对bit-map的扩展问题实例:1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数.8位最

  • C++中Cbitmap,HBitmap,Bitmap区别及联系

    加载一位图,可以使用LoadImage: HANDLE LoadImage(HINSTANCE hinst,LPCTSTR lpszName,UINT uType,int cxDesired,int CyDesired,UINT fuLoad): LoadImage可以用来加载位图,图标和光标 加载时可以规定加载图的映射到内存的大小: cxDesired:指定图标或光标的宽度,以像素为单位.如果此参数为零并且参数fuLoad值中LR_DEFAULTSIZE没有被使用,那么函数使用目前的资源宽度.

  • 浅析KJFrameForAndroid框架如何高效加载Bitmap

    我们在写Android程序的时候,肯定会用到很多图片.那么对于图片的压缩处理自然是必不可少.为什么要压缩?我想这个问题不必在强调了,每个人在最初学习Android的时候肯定都会知道这么一个原因:我们编写的应用程序都是有一个最大内存限制,其中JAVA程序和C程序(NDK调用时)共享这一块内存大小,程序占用了过高的内存就容易出现OOM(OutOfMemory)异常.至于这个最大内存是多少,我们可以通过调用Runtime.getRuntime().maxMemory()方法验证一下. 正因为受到内存大

  • Android Activity之间传递图片(Bitmap)的方法

    Android Activity之间传递图片(Bitmap)的方法

    在Android开发中:Activity之间传递参数是常见的事:如果我们要在Activity之间传递图片:1.MainActivity中包括一个ImageView:当我们点击ImageView时:把图片传递给另外一个Activity MainActivity的主要代码: 复制代码 代码如下: Intent intent=new Intent(MainActivity.this,TranActivity.class);            intent.putExtra("bitmap"

  • android bitmap compress(图片压缩)代码

    android的照相功能随着手机硬件的发展,变得越来越强大,能够找出很高分辨率的图片.有些场景中,需要照相并且上传到服务,但是由于图片的大小太大,那么就上传就会很慢(在有些网络情况下),而且很耗流量,要想速度快,那么就需要减小图片的大小.减少图片的大小有两种方法,1. 照小图片: 2. 压缩大图片. 照相时获取小图片一般不太符合要求,因为,图片的清晰度会很差,但是这种情况有个好处就是应用速度会快些: 压缩图片,就是把大图片压缩小,降低图片的质量,在一定范围内,降低图片的大小,并且满足需求(图片仍

  • android保存Bitmap图片到指定文件夹示例

    复制代码 代码如下: /** 保存方法 */ public void saveBitmap() { Log.e(TAG, "保存图片"); File f = new File("/sdcard/namecard/", picName); if (f.exists()) { f.delete(); } try { FileOutputStream out = new FileOutputStream(f); bm.compress(Bitmap.CompressFor

  • Android Bitmap详解及Bitmap的内存优化

    Android Bitmap详解及Bitmap的内存优化 一.Bitmap: Bitmap是Android系统中的图像处理的最重要类之一.用它可以获取图像文件信息,进行图像剪切.旋转.缩放等操作,并可以指定格式保存图像文件. 常用方法: public void recycle() // 回收位图占用的内存空间,把位图标记为Dead public final boolean isRecycled() //判断位图内存是否已释放 public final int getWidth() //获取位图的

  • Redis中的bitmap详解

    Redis中的bitmap详解

    1.什么是bitmap? bitmap也叫位图,也就是用一个bit位来表示一个东西的状态,我们都知道bit位是二进制,所以只有两种状态,0和1. 2.为什么要有bitmap? bitmap的出现就是为了大数据量而来的,但是前提是统计的这个大数据量每个的状态只能有两种,因为每一个bit位只能表示两种状态. 下面我们直接以一个统计亿级用户活动的状态来说明吧. 3.案例说明 3.1.案例描述 如果有一个上亿用户的系统,需要我们去统计每一天的用户登录情况,我们应该如何去解决? 前提条件:设置在9月19号

  • ES6新增数据结构WeakSet的用法详解

    WeakSet和Set类似,同样是元素不重复的集合,它们的区别是WeakSet内的元素必须是对象,不能是其它类型. 特性: 1.元素必须是对象. 添加一个number类型的元素. const ws = new WeakSet() ws.add(1) 结果是报类型错误. TypeError: Invalid value used in weak set 添加一个对象. const ws = new WeakSet() var a = {p1:'1', p2:'2'} ws.add(a) conso

  • 数据结构 红黑树的详解

    数据结构 红黑树的详解

    数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色. 2.根是黑色的. 3.如果一个节点是红色的,那么它的子节点必须是黑色. 4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 下面是一棵红黑树. 1.自底向上插入 通常把新项作为树叶放到树中.如果我们把该项涂成黑色,那么违反条件4,因为将会建立一条更长的黑节点路径.因此这一项必须涂成红色.如果它的父节点是黑色的,插入完成.如果父节点是红色的,那么违反条件3.在这种情况下我们

  • python算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • c++ 数据结构map的使用详解

    map的常用用法 map 表示映射,可以将任何基本类型(包括 STL 容器)映射到任何基本类型(包括 STL 容器),例如可以建立如 int 到 double,string 到 int 的映射等. map 提供一对一的 hash,该功能类似 Python 的字典: 第一个称为键( key ),每个关键字只能在 map 中出现一次: 第二个称为该键的值( value ): 1. 头文件 <bits/stdc++.h> 头文件已经包括了该头文件. 2. 定义 定义 map 如下,参数的第一个为 k

  • Java数据结构之单链表详解

    Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • Java数据结构顺序表用法详解

    Java数据结构顺序表用法详解

    目录 1.什么是顺序表 2.顺序表的基本功能和结构 3.顺序表基本功能的实现和解析 1.判断线性表是否为空 2.获取指定位置的元素 3.向线性表表添加元素 4.在位置i处插入元素 5.删除指定位置的元素,并返回该元素 6.查找t第一次出现的位置 7.手动扩容方法 1.什么是顺序表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等.一组数据中包含的元素个数可能发生变化(可以增加或删除元素). 对于这种需求,最简单的解决方

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • Java数据结构之散列表详解

    Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

随机推荐