Chapter 1

Posted on

位向量

第一章通过提出下面问题带我们认识了位向量

  • 问题：如果对磁盘中的文件进行排序？
  • 问题场景分析：文件存储最多1000万个7位整数，不会出现任何重复的整数
  • 约束：内存之多只有1MB，磁盘看作无限，要求算法优化到10秒

位向量/位图是一个很有用的数据结构，在充分利用小空间存储大量数据方面非常具有优势，Linux内核中很多地方都是用了位图，如分配pid

位图数据结构描述了一个有限定义域内的稠密集合，其中每个元素最多出现一次并且没有其他任何数据与该元素相关联

考虑到计算机中最小的数据单位是非0即1的二进制位，对于一个对象，使用一个二进制位就足够了。很多语言都具有位运算，因为不能用一个变量名直接表示一个位，那么可以将多个位组合成一个基本数据类型，通过对这个基本数据类型进行操作，达到使用位的方法。同时，为了方便，延续使用int数组的做法，把这些由位组合成的基本数据类型也组成数组

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
#include <stdio.h>

#define N 100                   // size of bitset
#define BITSPERWORD 32          // size of byte,it depends on machine
#define NUM (N-1)/BITSPERWORD+1 // size of int array
#define SHIFT 5
#define MASK 0x1F               // 11111 in binary

int a[NUM];

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));   }

void set_2(int i){      a[i/BITSPERWORD] != (1<<(i%BITSPERWORD));       }

void clr_2(int i){      a[i/BITSPERWORD] &= ~(1<<(i%BITSPERWORD));      }

int  test_2(int i){     return a[i/BITSPERWORD] & (1<<(i%BITSPERWORD)); }

int main()
{
        set(19);

        printf("%x",test(19));

}

书上的版本用的位运算，第一眼不一样就能明白，但是运算效率更高，因此自己写了个垃圾版本

i >> SHIFT表示算数右移5位，即i/32，该操作的作用是将数组的索引定位到需要操作的那个int 的位置上，因为我们的位向量结构是由许多个int组成的。i & MASK表示取 i 的最后5位，就相当于i%32

SET操作是取或运算，即把定位到的int中的某位设置为1