【出自BD面试题】
难度系数：★★★★☆ 被考察系数：★★★★★
题目描述：
已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
分析与解答：
这个题目从本质上而言也是求解数据重复的问题，对于这类问题一般而言，首先会考虑位图法。对于本题而言，8位电话号码可以表示的范围为：00000000～99999999，如果用1bit表示一个号码，总共需要1亿个bit，总共需要大约100MB的内存。
通过上面的分析可知，这道题的主要思路是：申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。所以bit值为1的数量即为不同电话号码的个数。
那么对于这道题而言，最核心的算法是如何确定电话号码对应的是位图中的哪一位。下面重点介绍这个转化的方法，这里使用下面的对应方法。
00000000对应位图最后一位：0x0000…000001。(www.xing528.com)
00000001对应位图倒数第二位：0x0000…0000010（1向左移1位）。
00000002对应位图倒数第三位：0x0000…0000100（1向左移2位）。
00000012对应位图的倒数十三为：0x0000…0001 0000 0000 0000。
通常，位图都是通过一个整数数组来实现的（这里假设一个整数占用4B）。由此可以得出通过电话号码获取位图中对应位置的方法为（假设电话号码为P）：
（1）通过P/32就可以计算出该电话号码在bitmap数组的下标。（因为每个整数占用32bit，通过这个公式就可以确定这个电话号码需要移动多少个32位，也就是可以确定它对应的bit在数组中的位置。）
（2）通过P%32就可以计算出这个电话号码在这个整型数字中具体的位的位置，也就是1这个数字对应的左移次数。因此可以通过把1向左移P%32位然后把得到的值与这个数组中的值做或运算，这样就可以把这个电话号码在位图中对应的为设置为1。
这个转换的操作可以通过一个非常简单的函数来实现：
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
