40亿个QQ号，每个QQ号用32位整数（4字节）表示。用bitmap存储，需要多大的空间？你是如何计算的？每个QQ号用11位整数比如手机号码呢。又需要多少？

### **情况一：每个QQ号用32位整数表示** **1. QQ号的范围** - 每个QQ号是一个32位整数，范围为0到\(2^{32} - 1\)，即0到4,294,967,295。 **2. 位图大小计算** - **总位数**：为了表示所有可能的QQ号，需要一个大小为\(2^{32}\)位的位图，即4,294,967,296位。 - **总字节数**：将位数转换为字节数。 $$ 总字节数 = \frac{总位数}{8} = \frac{4,294,967,296}{8} = 536,870,912 \text{字节} $$ - **总兆字节（MB）数**： $$ 总MB数 = \frac{总字节数}{1,048,576} = \frac{536,870,912}{1,048,576} = 512 \text{MB} $$ **3. 结论** - **空间需求**：需要**512 MB**的空间来存储所有可能的QQ号的位图。 - **去重效果**：由于位图中每个QQ号对应的位只能是0或1，重复的QQ号在位图中只会占用一个位，实现了去重存储。 ### **情况二：每个QQ号用11位整数表示** **1. QQ号的范围** - 每个QQ号是一个11位整数，范围为0到\(2^{11} - 1\)，即0到2,047。 **2. 位图大小计算** - **总位数**：需要一个大小为\(2^{11}\)位的位图，即2,048位。 - **总字节数**：将位数转换为字节数。 $$ 总字节数 = \frac{总位数}{8} = \frac{2,048}{8} = 256 \text{字节} $$ - **总兆字节（MB）数**： $$ 总MB数 = \frac{总字节数}{1,048,576} = \frac{256}{1,048,576} \approx 0.000244 \text{MB} $$ **3. 结论** - **空间需求**：仅需要**256字节**的空间来存储所有可能的11位QQ号的位图。 - **去重效果**：同样，位图天然支持去重，重复的QQ号不会增加额外的空间占用。 ### **总结** - **对于32位QQ号**：需要**512 MB**的空间来存储位图。 - **对于11位QQ号**：只需要**256字节**的空间来存储位图。