腾讯qq|腾讯43亿QQ号码用完后怎么办？( 二 )

如果没有敏感意识到使用bitmap ，就是很糟糕很不应该的事情，说明基本没有好好去准备啊。 bitmap图解如下：

unsigned char共8位，取值范围是[0 255
，这个unsigned char的数值是255 ，能标识0~7这些数字都存在。
同理，如下这个unsigned char类型的值是254 ，它对应的含义是：1~7这些数字是存在的，而数字0是不存的：

由此可见，一个unsigned char类型的数据，可以标识0~7这8个整数的存在与否，这是很好理解的，以此类推：

一个unsigned int类型数据可以标识0~31这32个整数的存在与否。
两个unsigned int类型数据可以标识0~63这64个整数的存在与否。

说白了，也就是4B的内存，可以标识32个整数的存在与否。如果还不清楚的话，我来画个表格，逐步推演一下：

内存大小	标识数的范围
4B	0~31
8B	0~63
16B	0~127
...	...
512MB	0~2^32 - 1

由此可见， 512MB的内存大小，刚好可以用来标识所有的QQ号码的存在与否，一切迎刃而解。
下面，我们看一下bitmap的程序，很好懂，也很实用，轻轻松松地实现了标记功能，顺便去重。
#include <iostream>
#include <set>
#include <cstring>
using namespace std;

#define N 20 // 考究0~19这20个数字
#define SHIFT 5
#define MASK 0x1f
unsigned int a[1 + N / 32
= {0;

// 设置第i位为1 让它处于点亮状态
void setOne(int i)
{
a[i >> SHIFT
|= (1 << (i & MASK));

// 设置第i位为0 让它处于熄灭状态
void setZero(int i)
{
a[i >> SHIFT
&= ~(1 << (i & MASK));

// 获取第i位的状态
int getState(int i)
{
return (a[i >> SHIFT
& (1 << (i & MASK))) && 1;

int main(void)
{
// 把1 ， 3 ， 1 ， 4 ， 9 ， 9 ， 9这几个值的状态点亮，即状态为1
setOne(1);
setOne(3);
setOne(1);
setOne(4);
setOne(9);
setOne(9);
setOne(9);

int i = 0;
for(i = 0; i < N; i++)
{
cout << i << \"对应的状态为:--->\" << getState(i) << endl; // 获取状态

cout << endl;

return 0;

编译运行一下，结果为：
0对应的状态为:--->0
1对应的状态为:--->1
2对应的状态为:--->0
3对应的状态为:--->1
4对应的状态为:--->1
5对应的状态为:--->0
6对应的状态为:--->0
7对应的状态为:--->0
8对应的状态为:--->0
9对应的状态为:--->1
10对应的状态为:--->0
11对应的状态为:--->0
12对应的状态为:--->0
13对应的状态为:--->0
14对应的状态为:--->0
15对应的状态为:--->0
16对应的状态为:--->0
17对应的状态为:--->0
18对应的状态为:--->0
19对应的状态为:--->0

QQ号码和bitmap的渊源就是如此，以后在面试时，不可忽视bitmap的妙用哦，也希望大家看完这篇文章后，有所收货，心情愉快。最后，来画一张动图玩玩，希望大家喜欢。