有10亿个浮点数中找出1万个最大的数(bit比较法)
网上已经有很多多的算法,现考虑一下用bit位比较法,请各位看看有没有问题~
算法思想:
以正整数为例(浮点数类似),假设从总数为total的正整数中求最大的max个数,正整数最高位到最低位分别对应第32-1位:
Proc:
将第i位(i=32)为1的放入文件A中,假设有n个数在A中,
1. 如果n>max,则问题变成求这n个数中最大的max个数,可设total=n, i--然后递归Proc;
2. 如果n<max,则输出这n个数,问题变成求剩下的(total-n)个数中最大的(max-n)个数,可设total=total-n, max=max-n, i-- 然后递归Proc;
3. 如果n==max则这n个数即是所求,输出这n个数,返回即可。
该算法最差需要对每个数查询32次,但时间复杂度仍为O(n).
下面分析浮点型的处理:
浮点数在内存中的存储
单精度浮点数: 1位符号位 8位阶码位 23位尾数
双精度浮点数: 1位符号位 11位阶码位 52位尾数
浮点表示的一般形式为:R=M*2^e (R:Real M:Mantissa尾数 e:exponent阶码)
float型浮点数125.5转化成32位二进制浮点数:
125.5的二进制码为1111101.1,写成二进制的科学计数为:1.111101*2^6(因为科学计数法“整数”部分大于1,在二进制中,“整数”部分只能恒为1)即向左移6位,则e=6,则E=e+127=133,而E的二进制码为10000101,而1.111101把“整数”部 分去除1之后为111101,之后补0,共23b,形成了阶码。
所以125.5的32位二进制浮点数为:
0 10000101 11110100000000000000000
由此,我们知道首先比较符号位,然后再比较阶码位,最后再比较尾数即可解决该问题。
[解决办法]