注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

生命无非记忆

不要在记忆中丢失了自己

 
 
 

日志

 
 

bitmap算法  

2015-08-19 16:32:07|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
算法介绍参见:http://blog.csdn.net/hackerwin7/article/details/17585257
下面是使用c++实现的一个简单的bitmap类

#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;
#ifndef NULL
#define NULL (0)
#endif
#ifndef false
#define flase (0)
#ifndef true
#define true (1)
#endif
#endif

#define ELEMENT_SIZE (sizeof(unsigned int) * 8)

class BitMap
{
public:
BitMap(){ bit = NULL; len = 0;}
BitMap(int count);
~BitMap();

bool AddNumber(int n);
bool DelNumber(int n);
bool ExistNumber(int n);
void OutPutAll();

private:
inline bool bitexist(int idx, int bt)
{
return bit[idx] & (1<<bt);
}

inline void addbit(int idx, int bt)
{
bit[idx] |= (1<<bt);
}

inline void delbit(int idx, int bt)
{
bit[idx] &= ~(1<<bt);
}

private:

unsigned int *bit;
int len;
};

BitMap::BitMap(int count)
{
if (count <= 0)
{
len = 0;
bit = NULL;
return;
}

len = count/ELEMENT_SIZE + 1;
bit = (unsigned int *)malloc(len * sizeof(unsigned int));
if (bit)
memset(bit, 0, len * sizeof(unsigned int));
}

BitMap::~BitMap()
{
if (bit != NULL)
{
free(bit);
bit = NULL;
}
}


bool BitMap::ExistNumber(int n)
{
return bitexist(n/ELEMENT_SIZE, n%ELEMENT_SIZE);
}

bool BitMap::AddNumber(int n)
{
int idx = n/ELEMENT_SIZE;
int bt = n%ELEMENT_SIZE;

if (idx > len)
{
cout << "target number " << n <<" is larger than the bitmap max number "<< (len * ELEMENT_SIZE)<<endl;
return flase;
}

if (bitexist(idx, bt))
{
cout << "target number " << n << " has existed in bitmap";
return false;
}

addbit(idx, bt);
return true;
}

bool BitMap::DelNumber(int n)
{
int idx = n/ELEMENT_SIZE;
int bt = n%ELEMENT_SIZE;

if (!bitexist(idx, bt))
{
cout << "target number " << n << " not in bitmap";
return false;
}

delbit(idx, bt);
return true;
}
void BitMap::OutPutAll()
{
int pre = 15;
int total = 0;
int i = 0;

for (i = 0; i < len; i++)
{
for (int j = 0; j < ELEMENT_SIZE; j++)
{
if (!bitexist(i, j))
continue;

if (total >= pre)
{
cout<<endl;
total = 0;
}

cout << (i*ELEMENT_SIZE + j) << " ";
total++;
}
}

cout << endl;
}
int main(void)
{
int max = 10000000;
BitMap bm(max);
int n = 0;

srand(time(NULL));
for(int i = 0;i < 100; i++)
{
n = rand()%max;

if ((i%15) == 0)
cout<<endl;

cout<<n<<" ";
bm.AddNumber(n);
}

cout<<endl;
bm.OutPutAll();
bm.DelNumber(n);
bm.OutPutAll();

return 0;
}



  评论这张
 
阅读(105)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017