16 May
BitSet in C -- Programming Pearl
今天开始重温<<编程珠玑>>这本书，第一个例子就讲到用Bitmap这个数据结构，加之最近长期和C语言打交道，于是就想到了如何用C语言实现真正意义上的BitSet(bitset)。
最开始我想到用Structure里面的Bit field来实现，但是Structure里的Alignment导致了内存的浪费（因为BitSet这样的数据结构很多时候就是为了节省空间而使用的，因此这样的做法是不可取的），当然我们可以在Structure里定义8个1位的unsigned char来解决这个问题，但是这样的做法感觉很生硬不优美。
另外关于Structure里的Bit field，我觉得UNIX中文件的Permission可以由其来实现（不过实际上不是这样的）。
typedef struct tagFile{
unsigned char usrr:1;
unsigned char usrw:1;
unsigned char usre:1;
unsigned char grpr:1;
unsigned char grpw:1;
unsigned char grpe:1;
unsigned char othr:1;
unsigned char othw:1;
unsigned char othe:1;
} File;
于是我想到了就用C语言里自带的数据类型配以各种Bit Operator来模拟BitSet中的Set, Reset以及Test方法，写了一个很Naive的小程序：
#include <stdio.h>
#include <stdlib.h>
#define _MAX_ 8388608
#define _BIT_SIZE_ 10
#define _TYPE_SIZE_ 8
typedef unsigned char *BitSet;
typedef unsigned char Type;
typedef unsigned int INT;
const Type bitset[_TYPE_SIZE_] = {1, 2, 4, 8, 16, 32, 64, 128};
const Type bitreset[_TYPE_SIZE_] = {254, 253, 251, 247, 239, 223, 191, 137};
INT getBytes(INT size)
{
return (size/sizeof(Type)+1);
}
BitSet init(INT size)
{
BitSet bs = (BitSet)malloc(getBytes(size));
BitSet p; int i;
for(p = bs, i = 0; i < getBytes(size); ++p, ++i)
*p = 0;
return bs;
}
void set(BitSet bs, INT index)
{
INT item = index / sizeof(Type);
INT offset = index % sizeof(Type);
*(bs+item) = *(bs+item) | bitset[offset];
}
void reset(BitSet bs, INT index)
{
INT item = index / sizeof(Type);
INT offset = index % sizeof(Type);
*(bs+item) = *(bs+item) & bitreset[offset];
}
INT test(BitSet bs, INT index)
{
INT item = index / sizeof(Type);
INT offset = index % sizeof(Type);
if(0 == (*(bs+item) & bitset[offset]))
return 0;
else
return 1;
}
int main(void)
{
/* Initialize the BitSet variable with a specified size. */
BitSet bs = init(_BIT_SIZE_);
/* Set all of the bits to 1. */
int i = 0;
for(i = 0; i < _BIT_SIZE_; ++i)
set(bs, i);
/* Reset one of the bitS to 0. */
reset(bs, rand()%_BIT_SIZE_);
/* Print all of the bits. */
for(i = 0; i < _BIT_SIZE_; ++i){
if(0 == test(bs, i))
printf("0\n");
else
printf("1\n");
}
return 0;
}
我想应该找时间看看STL里的Source Code，毕竟自己的想法太幼稚和简单了。
看了看书上给出的提示，看看人家的代码多简洁（当然这里没有用到数组的动态分配），好在思路是一样的。Simplicity is beautiful。
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
void tst(int i) { return a[i>>SHIFT] & (1<<(i & MASK));}
说几个细节，也算总结一下位操作符的使用：
想要对特定位做Reset操作，那么应该用&操作符，将指定位设为0即可完成操作（注意~操作符）。
想要对特定位做Set操作，那么应该用|操作符，将指定位设为1即可完成操作。
想要Test某一位的值，那么应该用&操作符，将指定位设为1即可实现。
另外在上述代码中，i & MASK实际上是进行的取余运算。
在本章节后面的习题中有这样一个问题，从区间[0, 10^7)中随机找出10^6个不能重复的数。关于随机的问题永远都是有“真伪”的，我们在这里可以使用一个很简单的算法来完成这样的操作，算法复杂度是O(N)。（N代表区间大小）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int x[MAXN];
int randint(int a, int b)
{ return a + (RAND_MAX * rand() + rand()) % (b + 1 - a);
}
int main(int argc, char *argv[])
{ int i, k, n, t, p;
srand((unsigned) time(NULL));
k = atoi(argv[1]);
n = atoi(argv[2]);
for (i = 0; i < n; i++)
x[i] = i;
for (i = 0; i < k; i++) {
p = randint(i, n-1);
t = x[p]; x[p] = x[i]; x[i] = t;
printf("%d\n", x[i]);
}
return 0;
}
写到这里我想起了洗牌问题（Shuffling），通常来说有两种洗牌方法：
1. for i:=1 to n do swap(a[i], a[randomIndex(1,n)]); 2. for i:=1 to n do swap(a[i], a[randomIndex(i,n)]);
我们如何判断这两种方法哪一个是公平的。所谓洗牌，其实就是求出一组数字的一个Random Permutation，而一组大小为N的数字，其全排列的个数应该是N!，因此公平的洗牌方法应该是得出这N!（或者是N!的倍数）种情况下的一种，显然第二种方法是公平的，又因为N^N不能整除N!，所以第一种洗牌方法不是公平的。这样的Shuffling算法也被称为Fisher-Yates Shuffling算法。
Facebook
Google+
LinkedIn
Twitter
Tumblr
Flickr
YouTube
Delicious
Recent Comments