---
icon: creative
title: 统计不同号码的个数
---

## 题目描述

**已知某个文件内包含大量电话号码，每个号码为8位数字，如何统计不同号码的个数？**

## 思路分析

这类题目其实是求解数据重复的问题。对于这类问题，可以使用**位图法**处理

8位电话号码可以表示的范围为00000000～99999999。如果用 bit表示一个号码，那么总共需要1亿个bit，总共需要大约**10MB**的内存。

申请一个位图并初始化为0，然后遍历所有电话号码，**把遍历到的电话号码对应的位图中的bit设置为1**。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。

最后这个**位图中bit值为1的数量**就是不同电话号码的个数了。

那么如何确定电话号码对应的是位图中的哪一位呢？

可以使用下面的方法来做**电话号码和位图的映射**。

```java
00000000 对应位图最后一位：0×0000…000001。
00000001 对应位图倒数第二位：0×0000…0000010（1 向左移 1 位）。
00000002 对应位图倒数第三位：0×0000…0000100（1 向左移 2 位）。
……
00000012 对应位图的倒数第十三位：0×0000…0001 0000 0000 0000（1 向左移 12 位）。
```

也就是说，电话号码就是1这个数字左移的次数。

## 具体实现

首先位图可以使用一个**int数组**来实现（在Java中int占用**4byte**）。

假设电话号码为 P，而通过电话号码获取位图中对应位置的方法为：

**第一步**，因为int整数占用4*8=32bit，通过 **P/32** 就可以计算出该电话号码在 bitmap 数组中的下标，从而可以确定它对应的 bit 在数组中的位置。

**第二步**，通过 **P%32** 就可以计算出这个电话号码在这个int数字中具体的bit的位置。只要把1向左移 **P%32** 位，然后把得到的值与这个数组中的值做或运算，就可以把这个电话号码在位图中对应的位设置为1。

以00000100号码为例。

1. 首先计算数组下标，100 / 32 = 3，得到数组下标位3。
2. 然后计算电话号码在这个int数字中具体的bit的位置，100 % 32 = 4。取余为0左移1位，故取余为4左移5位，得到000...000010000
3. 将位图中对应的位设置为 1，即arr[2] = arr[2] **|** 000..00010000。
4. 这就将电话号码映射到了位图的某一位了。

![](http://img.topjavaer.cn/img/20220423094735.png)

最后，统计位图中bit值为1的数量，便能得到不同电话号码的个数了。



