参考:
一、背景：
首先，明确两点：
- QQ号是 unsigned int 类型（4字节无符号整数，共32bit）, 也就是说 QQ号的取值范围是：$\color{blue}{[0, 2³² - 1]}$。
- QQ号是一个长度为10位的整数，大约是43亿，这也是QQ号码的理论最大值。
- QQ号码的最小值是 10001， 为什么tx要做这种限制呢？仅仅是早期的一个设定而已。
二、43亿QQ号所占内存大小计算：
其次，43亿QQ号所占内存大小是多少呢？512M！
- 一个 unsigned int 类型数据可以标识 0 ~ 31 这32个整数的存在与否（4Byte，0 ~ 31 ）
- 两个 unsigned int 类型数据可以标识 0 ~ 64 这64个整数的存在与否（8Byte，0 ~ 64 ）
又因为QQ号是 unsigned int 类型（无符号整数，4Byte，32位），也就是说 QQ号的取值范围是：$\color{blue}{[0, 2³² - 1]}$。
因此可对 2³² 次方范围内的QQ号所占大小进行推导：
- 1Byte所能标识数的范围为0~7（1字节，8 位）
- 4Byte所能标识数的范围为0~31（4字节，32 位）
- ...
- 那么多少Byte才能够标识 数的范围为 0 ~ 2³²-1（2³² 位）呢？
综上，用 2³² / 32 来表示：0 ~ 2³²-1（2³² 位） 能包含多少个 0 ~ 31（32位） 范围的块。并且每个 0 ~ 31（32位） 的块儿大小为4字节，因此 2³² / 32 × 4字节 的结果就是 0 ~ 2³²-1 范围所占字节的总大小，也就是 43亿 QQ号所占字节总大小。
2³²位 / 32位 × 4字节 / 1024 / 1024 = $\color{blue}{512M}$（1M=1024KB，1KB=1024Byte）
由此可见，512M的内存大小，就可以用来标识所有QQ号的存在与否。
三、bitmap的具体实现：
- 把所有 bitMap 位数组依次拼接后可表示 0 ~ 2³² 范围内43亿的数，所以足够存储40亿不重复的账号了
- bitmap数组中的一个uint32类型元素，由4字节组成(每个字节占8位)：
{[8位][8位][8位][8位]}{[8位][8位][8位][8位]}{[8位][8位][8位][8位]}{[8位][8位][8位][8位]}... - 如：
[0 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]...[...][...][...][... 40亿] - 共需 40亿/8位 = 5亿字节，5亿字节/4字节 = 1.25亿 个uint32类型元素数组来串联拼接表示（uint32类型大小占4字节）,所占内存大小为：4000000000/8/1024/1024 ≈ $\color{blue}{477M}$
- 还原qq号（数组下标从0开始）：当前第block块数 * 每个uint32 block块的固定大小为32 + 当前block块内的偏移量余数 yushu
- 每次新增QQ号时，都只需要在 bitMap[block] 的结果基础上继续进行异或 ^ 运算即可 ~
- 比如原本"QQ号=9（二进制表示
1 0000 0000，位下标为 9）"是有值的，现在又新增了"qq号=10（二进制表示10 0000 0000，位下标为 10）" - 那么9和10相异或后得:
10000 0000 ^10 0000 0000 =110000 0000，表示第 9 位和第 10 位的QQ号都有值了 - 0x1<<(yuShu-1)：比如原本"QQ号=9"时，那就把 0x1 左移8位，即：0x1 << 8，得到
100000000，最后从右至左第9位为1 - 关键代码：bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位：在之前bitMap已有结果的基础上，设置第block块上的第 "(0x1 << (yuShu - 1))" bit位为1
// 把所有位数组依次拼接后可表示 0~2³² 范围内的数，所以足够存储40亿不重复的账号了
// bitmap数组中的一个uint32类型元素，由4字节组成(每个字节占8位)：{[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} ...
// 如：[0 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] ... [...][...][...][... 40亿]
// 共需 40亿/8bit = 5亿byte，5亿byte/4byte = 1.25亿个uint32类型元素数组来串联表示（uint32类型大小占4字节）,所占内存大小为：4000000000/8/1024/1024≈477M
// 还原qq号（数组下标从0开始）：当前第block块数 * 每个block块的固定大小32 + 当前block块内的偏移量余数yushu
// 每次新增QQ号时，都只需要在bitMap[block]的结果上继续进行异或^运算即可~
// 比如原本"QQ号=9（二进制表示 1 0000 0000，位下标为9）"是有值的，现在又新增了"qq号=10（二进制表示 10 0000 0000，位下标为10）"
// 那么相异或后得: 1 0000 0000 ^ 10 0000 0000 = 11 0000 0000，表示第9位和第10位的QQ号都有值了
// 0x1<<(yuShu-1)：比如原本"QQ号=9"时，那就把0x1左移8位，即：0x1 << 8，得到 100000000，从右至左第9位为1
// 根据QQ号来设置其在bitMap中bit位
func BitCalculation(bitMap []uint32, everyBlockSize, qq uint32) {
// 判断是属于第几块的第几个bit位
block := qq / everyBlockSize // 块数：第block块（bitmap数组从第0块开始，无需根据yuShu是否为0来判断block是否+1）
yuShu := qq % everyBlockSize // 余数：第block块中的具体第几个bit位
// fmt.Printf("block=%v, yuShu=%v \n", block, yuShu)
fmt.Printf("在对%v(%b)位运算设置标记位1之前，bitMap的第%v块上二进制表示: %b\n", qq, 0x1<<(yuShu-1), block, bitMap[block])
bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位：在之前bitMap已有结果的基础上，设置第block块上的第 "(0x1 << (yuShu - 1))" bit位为1
fmt.Printf("在对%v(%b)位运算设置标记位1之后，bitMap的第%v块上二进制表示: %b，还原qq号为: %v\n\n", qq, 0x1<<(yuShu-1), block, bitMap[block], block*everyBlockSize+yuShu)
}
// 初始化相关参数
func TestBit(qqCnt uint32, qqArr []uint32) {
var everyBlockSize uint32 = 4 * 8 // uint32类型占32位：一个uint32能标记0~31范围内32个QQ号
blockCnt := qqCnt / everyBlockSize // 40亿QQ号所需uint32类型的块数
bitMap := make([]uint32, blockCnt) // 存储40亿QQ号的bitmap，统一初始化为0
// fmt.Println("blockCnt 40亿QQ号所需uint32类型的块数: ", blockCnt) // 1.25亿块
for i := 0; i < len(qqArr); i++ {
// 设置每个测试QQ到bitMap中
BitCalculation(bitMap, everyBlockSize, qqArr[i])
}
}
func main() {
// 以下均默认在64位操作系统下执行：
// i := int(1) // int在64位系统下默认大小为8，即：int64
// fmt.Println(unsafe.Sizeof(i)) // 8
//
// j := int32(1)
// fmt.Println(unsafe.Sizeof(j)) // 4
//
// k := int64(1)
// fmt.Println(unsafe.Sizeof(k)) // 8 相当于long/double类型，占8字节(64位) 最大能表示范围为：2⁶⁴
//
// ll := float64(1)
// fmt.Println(unsafe.Sizeof(ll))
// int32 表示范围: -2147483648 ~ 2147483647，因为账号数有40亿个，所以采用无符号类型 uint32 类型，表示范围: 0 ~ 4294967295
var qqAccountCnt uint32 = 4000000000
testNumArr := []uint32{9, 399999999, 1234567890} // test data
TestBit(qqAccountCnt, testNumArr)
return
}示例结果展示：
四、扩展
练习一： 文件中有40亿个互不相同的QQ号码，请设计算法对QQ号码进行$\color{blue}{排序}$，内存限制1G。
很显然，直接用bitmap,
标记这40亿个QQ号码的存在性，然后从小到大遍历正整数，当bitmapFlag的值为1时，就输出该值，输出后的正整数序列就是排序后的结果。
请注意，这里必须限制40亿个QQ号码互不相同。通过bitmap记录，客观上就自动完成了排序功能。练习二：文件中有40亿个互不相同的QQ号码，求这些QQ号码的$\color{blue}{中位数}$，内存限制1G。
一些刷题经验丰富的人，最开始想到的肯定是用堆或者文件切割，这明显是犯了本本主义错误。直接用bitmap排序，当场搞定中位数。练习三：文件中有40亿个互不相同的QQ号码，求这些QQ号码的$\color{blue}{topK}$，内存限制1G。
很多人背诵过topK问题，信心满满，想到用小顶堆或者文件切割，这明显又是犯了本本主义错误。直接用bitmap排序，当场搞定topK问题。练习四：文件中有80亿个QQ号码，试判断其中是否存在$\color{blue}{相同}$的QQ号码，内存限制1G。
一些吸取了经验教训的人肯定说，直接bitmap啊。然而，又一次错了。根据容斥原理可知：
因为QQ号码的个数是43亿左右(理论值2^32 - 1)，所以80亿个QQ号码必然存在相同的QQ号码。
五、总结：
- QQ号理论上的范围为：10001 - 43亿（2³²），其类型为
unsigned int - 43亿QQ号所占内存大小，经计算后大约占 512M （满足小于1G的要求）
- 40亿QQ号所占内存大小，经计算后大约占 477M （满足小于1G的要求）
- bitMap实现方案 及 异或 ^ 等位运算
- 利用 bitMap 来处理海量数据问题，内存占用低，满足要求且可以取得不错的效果。包括：排序、中位数、topK、去重 等等...
