位图的几个总结

电玩女神 2022-08-11 00:45 174阅读 0赞

1.当满足下面三个条件的时候，可以使用位图来解决问题。

1)输入的数据在一个范围之内。 2)输入的数据不重复 。 3)输入的数据是整型数据。

比如编程珠玑上面的一题：

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出：按升序排列的输入正数的列表。

约束：最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

2.位图解决问题的思路是：

用每个位来表示对应的数存在不存在。

比如说一个20长的字符串，可以用来表示一个所有元素都小于20的简单的非负整数集合。

比如下面的字符串可以用来表示集合\{1,2,3,5,8,13\}.

11101001000010000000

这个串中的哪一位为1, 则表示集合中存在这个元素，比如第一位为1,则表示1在这个集合中，第4位为0,

则表示集合中没有4。

3.编程珠玑上题目的实现代码:

#include <stdio.h>
    
    #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 main()
    {	int i;
    	for (i = 0; i < N; i++)
    		clr(i);
    /*	Replace above 2 lines with below 3 for word-parallel init
    	int top = 1 + N/BITSPERWORD;
    	for (i = 0; i < top; i++)
    		a[i] = 0;
     */
    	while (scanf("%d", &i) != EOF)
    		set(i);
    	for (i = 0; i < N; i++)
    		if (test(i))
    			printf("%d\n", i);
    	return 0;
    }

4.与位图相关的面试题总结：

1).给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。（腾讯面试题)

用位图法：40亿unsigned int，则用位图表示的话需要大小为40亿个bit=4\*10  9 bit=0.5\*10  9 bytes 因此申请的内存只需要大小约为512MB左右，这样在内存每个bit代表一个unsigned int整数，并将每个bit初始化为0，然后将40亿个unsigned int的整数读入，每个unsigned int的整数对应bit设置为1，读入后，最后看所给定的数对应的bit是否为1，是1存在，否则不存在。

2).[http://blog.csdn.net/jiqiren007/article/details/6451560][http_blog.csdn.net_jiqiren007_article_details_6451560]  查看这里的讨论。

[http_blog.csdn.net_jiqiren007_article_details_6451560]: http://blog.csdn.net/jiqiren007/article/details/6451560