100亿整型数据去重？
整型数据为32位最多有2^32(42亿多），所以100亿整型数据一定有重复的，2^32个整形用位表示，需要(2^32)bit==512MB,需要512MB内存表示。
1.前言
一般情况下，一个字符所占内存大小。
UTF-8编码：一个英文字符等于一个字节，一个中文（含繁体）等于三个字节。
我们知道一个1G=1024M，1M=1024K，1K=1024byte，1byte=8bit，所以1个字节等于8bit，也就是8个二进制位，位图法的概念是用一个位(bit)来标记某个数的存放状态，所以节省了大量的空间。
2.数据结构
unsigned int bit[N]，在这个数组里面，可以存储N*PHP_INT_SIZE*8个数据，但是最大的数只能是N*PHP_INT_SIZE*8-1。例如我们要存储的数据范围为0-63，则我们只需要将N=1，这样就可以把数据存进去，如下图：
数据为[5,1,7,15,0,4,6,10,14]，将这些数据存入这个结构中为（如果有重复的数字呢？？？）
3.算法
定义一个数组$bitmap = array_fill(0,50,0)，长度为50，并且填充上0，我们知道PHP_INT_SIZE在64位系统中是8，则这个数组能容下50*8*8=3200个数据，字节范围（0~49），位范围（0~93），怎么求一个数的字节位置和位位置呢，比如1234，字节位置：1234/64=19，位位置：1234%64=18。字节位置就是$bitmap的下标，而位位置就是在该下标数组的这个数的二进制中的位数。
代码如下
function BitMap($arr)
{
$bitmap = array_fill(0, 50, 0);
$int_bit_size = PHP_INT_SIZE * 8;
foreach ($arr as $item) {
$bytePos = $item / $int_bit_size;
$bitPos = $item % $int_bit_size;
$position = 1 << $bitPos;//这个将1是左移多少位
$bitmap[$bytePos] = $bitmap[$bytePos] | $position; //两个数按或运算，作用就是把二进制上对应位置的0置为1
}
return $bitmap;
}
4.例子
实现排序
//位图法
function bitMap($arr) : array {
$bitmap = array_fill(0,50,0);
$int_bit_size = PHP_INT_SIZE * 8;
foreach ($arr as $item){
$bytePos = $item / $int_bit_size;
$bitPos = $item % $int_bit_size;
$position = 1 << $bitPos;
$bitmap[$bytePos] = $bitmap[$bytePos] | $position;
}
return $bitmap;
}
//输出排序数组
function outPut($bitmap) : array {
$int_bit_size = PHP_INT_SIZE * 8;
$result = array();
foreach ($bitmap as $k=>$item){
for ($i=0;$i<$int_bit_size;$i++){
$temp = 1 << $i;
$flag = $temp & $item;
if ($flag){
$result[] = $k * $int_bit_size + $i;
}
}
}
return $result;
}
$test_arr = array(1,4,3,50,34,60,100,88,200,150,300); //定义一个乱序的数组
$arr_temp = BitMap($test_arr);
$result = outPut($arr_temp);
echo "<pre>";
var_dump($result);
echo "<pre>";
---------------------
作者：咔嚓杨
来源：CSDN
原文：https://blog.csdn.net/u013252047/article/details/80273814
