在我们写程序的的时候，有时候我们经常需要存储许多的二值的信息量，如：一件事情有没有发生、很多灯的亮灭的状态、网络传输中判断重复数据包等。这时我们就需用用一个信息单元来存储1、0 信息来表示有或无。那我们该怎么表示呢？最简单的方法就是使用数组了
这个数组中就可以存储256个信息量的状态，每个数组单位中存储一个0或1（buf[0] = 1, buf[1] = 0;）。这里我们有一种更好的方法就是用C语言中的位操作来实现这个需求。使用char类型的8位表示8个信息量，使用每一位01表示不同。这样我们用char buf[32]就可以存储256个二值信息量，大大节约了空间。位操作不能像数组操作那样直接简单，所以我们封装了几组函数如下：
1
2
3
4
5
6
7
8
9
| #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)); }
int test(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); } |
上面是我一个程序中的例子。这里我们使用的是int类型表示32个信息量。
a[i>>SHIFT]来确定设置a数组的哪一个元素，(1<<(i & MASK))用来确定设置一个a数组元素中的某一位！
我们的需求是判断0 ~ 10000000 之中的数字是否出现过，而set(1)、clr(1)、test(1)函数就可以将表示数字一是否存在的哪一位置为1、清零、判断是否为1。这样我们就可以通过这几个函数来实现位的操作。
在我看《编程珠玑》的过程中，出现了新的需求，就是记录 0 ~ 10000000之中数字出现的次数，最多为15次。这里用一位就不可能表示了，所以我们设计为用4位表示一个数字出现的次数。（0000 ~ 1111 : 0 ~ 15）
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #define BITSPERWORD 8
#define SHIFT 3
#define MASK 0x07
#define N 10000000
int a[1 + N/BITSPERWORD];
/* 输出整数j的所有的位 */
void prnt(int j)
{
int i;
for (i = 31; i >= 0; i--) {
if (j & (1 << i )) {
printf("1");
} else {
printf("0");
}
}
printf("\n");
}
void clr(int i)
{
a[i>>SHIFT] &= ~(15<< ((i & MASK) * 4));
}
void set(int i)
{
int t;
t = a[i>>SHIFT] >> ((i & MASK) * 4);
t = ((t & 0x0f) + 1) & 0x0f; /* 这里限定，出现次数最大的数据为15 */
t = t << ((i & MASK) * 4);
clr(i);
a[i>>SHIFT] |= t;
}
int get(int i)
{
int t;
t = ( a[i>>SHIFT] >> ((i & MASK) * 4) ) & 0x0f;
return t;
}
int test(int i)
{
return a[i>>SHIFT] & ( 15 << ((i & MASK) * 4));
} |
没有评论:
发表评论