BitMap的原理不用多说了。

主要说下位操作。

我们假设每个基础存储单元为char，则BYTESIZE = 8，如果为int则16 or 32。

当设置i时，首先ptr+=i/BYTESIZE，到达要操作的那个char。

然后对*ptr |= 0x01<<(i%BYTESIZE)即可。这里在同一个机器上，可以忽略大小端的问题。

检查的时候，也是首先ptr+=i/BYTESIZE，然后查 (*ptr&0x01<<(i%BYTESIZE)) == 0x01<<(i%BYTESIZE)即可。

上面这个0x01<<...实际上...就是0~7，因此我们可以预定义一个数组pre，防止重复计算。

代码如下：

#include <stdio.h>
#include <memory.h>
#include <string.h>

#define BYTES 1024
#define BYTESIZE 8

char buffer[BYTES];
char pre[8] = {0x01<<0, 0x01<<1, 0x01<<2, 0x01<<3, 0x01<<4, 0x01<<5, 0x01<<6, 0x01<<7};

void bitmap_init(char* buf, int n)
{
	memset(buf, 0, sizeof(char)*n);
}

void bitmap_set(char* buf, int n, int i)
{
	int add = i/BYTESIZE;
	int pos = i%BYTESIZE;
	if(add>=n)
	{
		return ;
	}
	buf += add;
	*buf |= pre[pos]; //*buf |= (0x01<<(i % BYTESIZE));
}

int bitmap_check(char* buf, int n, int i)
{
	int add = i/BYTESIZE;
	int pos = i%BYTESIZE;

	if(add>=n)
	{
		return 0;
	}
	buf += add;
	return (*buf&pre[pos])==pre[pos]; // return (*ptr&0x01<<(i%BYTESIZE))==0x01<<(i%BYTESIZE);
}

void bitmap_print(char* buf, int n)
{
	int i;
	int j;
	char bs[BYTESIZE];
	for(i=0;i<BYTESIZE;i++)
	{
		bs[i] = 0x01<<i;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<BYTESIZE;j++)
		{
			if((*buf&bs[j])==bs[j])
			{
				printf("%d\n", i*BYTESIZE+j);
			}
		}
		buf++;	
	}
}

int main()
{
	bitmap_init(buffer, BYTES);
	bitmap_set(buffer, BYTES, 999);
	printf("%d\n", bitmap_check(buffer, BYTES, 999));
	printf("%d\n", bitmap_check(buffer, BYTES, 998));
	bitmap_print(buffer, BYTES);
	return 0;
}