将超出机器存储范围的整型数据导入内存的一种处理方式

         题目是这样的：给定10亿+个int型数，要求找出重复出现的数字，并输出。（前提是在32位的机器上）

 

           首先，对题目进行认识，如果给定的int型数据很少的话，筛选数据的一般方法是直接建立整型数组存入数据，再利用冒泡或者其他排序方式进行排序就可以很容易筛选出重复的。

 

          然后，要判断机器运算的范围究竟是多大。32位的机器，内存有2的32次方bit，换算成GB是4G，然而实际计算机能用到的不到2G。。。10亿个int，每个int等于4个byte，1个byte等于8个bit，如果全部导入内存的话需要的空间将近30G，远远超出计算机的计算范围。

 

           所以，要将int型数转化之后才能导入内存。计算机内的最小存储单位是bit，如果把数字全存到bit数组里会多大呢？计算之后发现用不了1G，所以可以尝试。用bit数组的下标来记录数字，因为bit只有0和1，所以可以让bit做标志位，初值为0，当该下标的数出现时变为1，当已经为1时证明该下标的数已出现过，one by one的判断。

       例如要找的数是100，只需判断bit[100]为0还是1。

 

 

 

           然而，代码能开的最小数组是byte，开不了bit的。所以建立byte数组后需要先找到要找的数（bit位）在byte数组中的位置，把该数展开为8位的bit，将用到的位提取出来，对该位上的符号进行判断和处理。

       例如还是找100，100/8=12余4，即要找的"bit[100]"其实就在byte[12]中（因为从byte[0]开始），将byte[12]按位展开，得到范围为0-7的8位字符，假设得到的是"00000000",因为余数是4，所以第4位就变为1（从第0位开始），变成"00001000"。

        找“bit数组”中的位置就变成找byte数组中的位置（下标）和该位置 按位 展开后某一位的位置。用要找的数除以8，商就是byte数组的下标，余数就是8位中的位置。

 

 

至于将byte展开为bit的方法可以自己按位运算写一个方法也可以直接调用如下方法：

        String string = Integer.toBinaryString(byte[n]);

       这个方法可以将10进制数转化为2进制字符串。然后就可以从字符串中提取当前所需要的位进行操作。具体操作如下代码，如果该位为1即已出现，输出；如果该位为0说明第一次出现，赋值为1。

 

			char[] c=new char[8];
			for (int j = 0; j <8; j++) {
				c[j]=string.charAt(j);
			}
			if(c[yu]=='1'){
				System.out.println(a[i]+"已出现");
							}
			else{
				c[yu]='1';
				
			}

 

对位运算过后因为要保存数据，所以更改过的位要重新写入byte数组中 。

			String st="";
			for(int m=0;m<8;m++){
			st=st+c[m];
			}
			bytes[zheng]=(byte) Integer.parseInt(st, 2);

 

 

    另外要注意的一点是因为我们用java写的代码，java中byte是有符号的。

在把byte转展开为2进制数时，如果数展开不足8位，及为较小正数时，系统不会自动左补零补够8位。

在把string的8位当做2进制转成byte时，因为是强制转型，当该数为负时会变成32位，左边全部是1。

具体解决方案如下：

0不够就左补0，为负时就截取最后8位。

			while(string.length()<8){//为正小于八位时左补零
				string="0"+string;
			}
			while(string.length()>9){//为负大于八位截取最后八位
				string=string.substring(24,32);
			}
			

 

 

         最后，所有要找的数全部由随机产生。

 

完整代码如下：

package com.test.myNum;

import java.util.Random;

public class test {
	public static void main(String[] args) {
		byte[] bytes=new byte[170000000];
		Random random=new Random();
		int a[]=new int[10000000];
		int zheng,yu,flag=0;
		for(int i=0;i<1000000;i++){
			a[i]=random.nextInt(1000000000);
			zheng=a[i]/8;
			yu=a[i]%8;
			
			String string = Integer.toBinaryString(bytes[zheng]);
			
			while(string.length()<8){//为正小于八位时左补零
				string="0"+string;
			}
			while(string.length()>9){//为负大于八位截取最后八位
				string=string.substring(24,32);
			}
			
			
			char[] c=new char[8];
			for (int j = 0; j <8; j++) {
				c[j]=string.charAt(j);
			}
			if(c[yu]=='1'){
				System.out.println(a[i]+"已出现");
				flag++;
			}
			else{
				c[yu]='1';
				
			}
			String st="";
			for(int m=0;m<8;m++){
			st=st+c[m];
			}
			System.out.println(st);
			bytes[zheng]=(byte) Integer.parseInt(st, 2);//
			System.out.println(a[i]);
		}
		
		System.out.println("所有数字共重复出现"+flag+"次");
	}
}

 

 

 

 

 

评论

2 楼 wz94 2014-01-24  

mfkvfn 写道

你这是《编程珠玑》这本书第一章的例子。里面有很详细的讲解。

谢谢，有空的话我会找这本书看下的

1 楼 mfkvfn 2014-01-24  

你这是《编程珠玑》这本书第一章的例子。里面有很详细的讲解。