bitmap运算
2024-08-31 22:11:52
概述
所谓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;
}
参考链接
最新文章
- sublime编辑器插件
- Linux 流程控制语句 if else、for、while、until
- js实现cookie记住密码
- java核心知识点学习----创建线程的第三种方式Callable和Future CompletionService
- MyBatis知多少(18)MyBatis系统
- 配置文件,环境配置和war报分离,方便生产更改
- Gentoo安装
- MapReduce的reduce函数里的key用的是同一个引用
- 多种下载文件方式 Response.BinaryWrite(byte[] DocContent);Response.WriteFile(System.IO.FileInfo DownloadFile .FullName);Response.Write(string html2Excel);
- java 显示目录下全部文件
- 主流芯片解决方案Ambarella的高清网络摄像机、德州仪器和控制海思
- CSS——(2)与标准流盒模型
- SharePoint 2010 加入项目到用户/欢迎菜单
- trove 开发者阅读翻译
- centos 创建用户组及用户
- 201521123087 《Java程序设计》第4周学习总结
- AVFoundation 框架初探究(三)
- CentOS7 64位安装mysql教程
- 网络工具之chisel + openvpn混合
- xib中的label加边框
热门文章
- SWIFT中获取配置文件路径的方法
- magento建立多语言网站
- opencv-python教程学习系列7-opencv图像基本操作
- 【转】Python xlrd、xlwt、xlutils读取、修改Excel文件
- Prime Ring Problem dfs
- Hash表的平均查找长度ASL计算方法
- (转)C++初始化与赋值
- 转-Hive/Phoenix + Druid + JdbcTemplate 在 Spring Boot 下的整合
- BL老师的建议,数学不好的,大数据一票否决--后赋从java转大数据
- Json.NET Updates: Merge, Dependency Injection, F# and JSONPath Support