Home 数据结构及算法 [转] bitmap算法

转自: 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算法利用这种思想处理大量数据的排序与查询

优点:
  • 效率高,不许进行比较和移位
  • 占用内存少,比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M,如果采用int数组存储,则需要38M多
缺点:
  • 无法对存在重复的数据进行排序和查找
示例:
申请一个int型的内存空间,则有4Byte,32bit。输入 4, 2,  1,  3时:
输入4:
输入2:
输入1:
输入3:

思想比较简单,关键是十进制和二进制bit位需要一个map映射表,把10进制映射到bit位上


map映射表

假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 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;
}


参考链接

0 comment

You may also like

Leave a Comment