用bitmap实现中位数的算法

常见面试题之一：50亿个整数，内存限制为1G，找出中位数。

50亿个整数用bitmap来存储的话，大约150M的空间就足够了。

下面是具体的算法，用PHP实现。

define("MASK", 0x1f);

$source = array(1, 74, 4, 256, 1024, 110, 111, 112, 123, 112, 100);

$array = array();
$count = 0;

foreach($source as $num) {
	set($num); // add to bit map
}

$count = intval($count >> 1) + 1; // cal middle number

for($i = 0;;$i++) { // travel the bit map and find the middle number
	$num = $array[$i];
	
	if(!$num) {
		continue;
	}
	
	$sum = 0;
	while($num) {
		if($num & 0x1) {
			if(!--$count) {
				echo ($i << 5) + $sum;
				exit;		
			}
		}
		$num >>= 1;
		$sum++;
	}
}
/*
 * set number to bit map
 */
function set($i) {
	global $array;
	global $count;
	
	$temp = (1 << ($i & MASK));
	$array[$i >> 5] |= $temp;
	
	if($temp) {
		$count++;
	}
}