我的小站——半生瓜のblog

位图算法

已空间换时间。

很多不重复的整数，其中最大值不超过40亿，最小值是0，要求判断某个指定的整数，是否在这个集合中。

使用2个字节，表示16个数，的状态(有或者没有)

上面为表示的数，下面为该数的个数。

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

例如：要表示1,13,4,5,6

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
0	0	1	0	0	0	0	0	0	1	1	1	0	0	1	0

要表示40亿个数

4000000000/8 = 500000000字节

500000000字节/1024= 488281K

488281k/1024 = 476.837M

单位换算

1字节== 8比特位

1K == 1024字节

1M == 1024K

代码实现：

#include<iostream>
using namespace std;
//初始化容器内容
void init(char* data, int len)
{
    unsigned int tempN = len * 8;//40亿个数——40亿个位

    //假定需求:这个容器中存的是40亿以前能被3整数的数
    //就将他对应的比特位改成1(默认是0——memset())
    for (unsigned int i = 0; i < tempN; i++)
    {
        if (i % 3 == 0)
        {
            //找到这个数对应的字节
            char* p = data + (i / 8);
            //找到对应的位，并且将对应的位改成1
            *p = *p | (1 << (i % 8));//解释如下:
            /*
                如何将这个数对应的位(在比特位中的第几位数)改成1？

                对1进行左移操作,这个数 % 8等于多少
                (就是该数与该字节的最右侧中间间隔了几个位)，
                1就左移几位，

                然后和这个字节进行按位或操作，例如

                i = 12;
                //上面是对应的数,下面是对应比特位的数
                15 14 13 12 11 10 9 8
                0  0  0  0  0  0  0 0 
                与   1 << (i % 8)  进行按位或操作
                0  0  0  1  0  0  0 0
                得到
                15 14 13 12 11 10 9 8
                0  0  0  1  0  0  0 0

            */
        }
    }
}

//位图算法实现
bool check(char* data,int len,int value)
{
    //找到对应的字节
    char* p = data + value / 8;
    //找到对应的位，并判断是否存在
    bool ret = *p & (1 << (value % 8));//解释如下
    /*
        对1进行的左移操作同上
        然后将这个所在的字节与1左移后的值，进行按位与
        1 & 1 = 1
        1 & 0 = 0
        0 & 0 = 0
        0 &1 = 0；

    */
    return ret;
}
int main(void)
{
    unsigned int n = 4000000000;//这个40亿代表40个数(80亿个比特位)
    int len = n / 8 + 1;//40亿个数对应的字节个数
    char* data = new char[len];//创建对应字节个数这么大的一个数组(容器)
    memset(data, 0, len);//容器清0
    init(data, len);//往容器中存数据
    int a = 0;
    //输入测试
    while (1)
    {
        cout << "请输入你要查找的数" << endl;
        cin >> a;
        if (a == -1)
        {
            break;
        }
        if (check(data, len, a))
        {
            cout << a << "被找到啦" << endl;
        }
        else
        {
            cout << a << "找不到" << endl;
        }

    }

    return 0;
}