本文介绍如何给非常多的整形数据排重。
首先我先解释一下排重的意思:
排重就是给一串数有顺序的重新排列,并且去掉重复的数字。
我们知道java编程中一个整形数据为4个字节,最大整数为2^32-1,所以不同整数的个数最大就有2^32个(这里不考虑负数),从0~2^32-1,那么这样你可以算一下假设用一个整形数组来存储这些数那么它所占的内存是比较大的。可能大于java虚拟机所拥有的内存空间。那么我们是否能用比较小的空间来存储这些数据呢。
想法思路
一个整形数据有32位每个位为0或者1,那么我们要是用它他的每一个位来表示一个整形数据,那么我们可以将我们所需的空间,最大就能缩小为原来的1/32。那么怎么用位来表示不同的整数呢。我们可以这样来向,有一个整形数组。它的第一个元素是一个整形数据,那么这个整形数据我们就用来表示0到31这32个整数,要是整形数据对应的01串上某个位置为1那么这个位置代表的整数就表示存在,同理数组中的第二个元素就能表示32到63这32个整数,依次列推。比如:
00000000 00000000 00000000 00000011 就表示30和31被存在这个整数中,因为01串的第30和31位为1,该01串对应的整数是3=1+2。
按照上面的思路,那么我们要来存储所有不同的整数,就只要开一个2^27长度的int型数组。这样就可以降低所使用的内存空间的大小了。
同样的要是我们开一个byte数组来存储整数那么一个byte为8个,可以用来存储8个整数。可以开一个2^29长度的byte数组来存储所有不同的整数。
下面以用byte数据来存储从小到大排列数据为例的源代码。
package M数排重;
import java.util.Random;
public class Test {
byte[] bytearray=new byte[100];;
/**
* 主函数
* @author lixiongzhi
*/
public static void main(String[] args) {
Test test=new Test();
Random random=new Random();
for(int i=0;i<20;i++){
int n=random.nextInt(50);
System.out.print(n+" ");
test.setBit(n);
}
System.out.println();
test.print(test.bytearray);
}
/**
* 2的n次方
* @param n
* @return
*/
private int N(int n){
int result=1;
for(int i=0;i<n;i++){
result*=2;
}
return result;
}
/**
* 整数n对应的bit并设为1
*/
private void setBit(int n){
//对应的byte数组下标
int index=n/8;
//byte[index]对应的第mod个bit
int mod=n%8;
//获取byte[index]转换成的01串
String str=byteToString(bytearray[index]);
//将str的第mod位设为1
System.out.print(str+" ");
str=setCharat(str, mod);
System.out.print(str+" ");
byte newbyte=StringToByte(str);
System.out.println(newbyte);
bytearray[index]=newbyte;
}
/**
* 将一个01串转化成byte
*/
private byte StringToByte(String str){
byte result=0;
for(int i=0;i<8;i++){
if(str.charAt(i)==(char)49){
result+=N(7-i);
}
}
return result;
}
/**
* 将一个byte转换成01串
* @return
*/
private String byteToString(byte n){
String str="";
for(int i=0;i<8;i++){
str+=n%2;
n/=2;
}
//将str倒序排
String str2="";
for(int i=7;i>=0;i--){
str2+=str.charAt(i);
}
return str2;
}
//设置str第index+1位为1的函数
private String setCharat(String str,int index){
if(str.charAt(index)!="1".charAt(0)){
String str2="";
for(int i=0;i<str.length();i++){
if(i==index){
str2+=1;
}else{
str2+=str.charAt(i);
}
}
return str2;
}
return str;
}
/**
* 排重后输出
* @param array
*/
private void print(byte array[]){
for(int i=0;i<array.length;i++){
if(array[i]!=0){
for(int j=0;j<byteToString(array[i]).length();j++){
if(byteToString(array[i]).charAt(j)==(char)(49)){
int k=8*i+j;
System.out.print(k+" ");
}
}
}
}
}
}
看输出结果:
20 00000000 00001000 8
48 00000000 10000000 -128
17 00001000 01001000 72
11 00000000 00010000 16
38 00000000 00000010 2
11 00010000 00010000 16
8 00010000 10010000 -112
23 01001000 01001001 73
24 00000000 10000000 -128
27 -0000000 -0010000 16
3 00000000 00010000 16
16 01001001 11001001 -55
46 00000000 00000010 2
2 00010000 00110000 48
24 00010000 10010000 -112
8 1-1-0000 1-1-0000 -96
4 00110000 00111000 56
13 -1-00000 -1-00100 68
32 00000010 10000010 -126
0 00111000 10111000 -72
排重后结果为:
3 9 13 18 20 22 24 26 33 35 37 46
第一列01串代表从byte数组中取出的byte转换成的01串,第二列代表加入整数后变成的01串。如第一行 20 00000000 00001000 8 是从byte中取出的bytebytearray[20/8]这个byte转换成01串为00000000 存入20时第20%8位即第4+1位变成1 最后的8代表存入20后的01串再转换成的byte。
很明显这样的运行结果并不符合我们上面的分析。
原因:
当我们将8个01串转换成一个byte时出现了负数的情况。
上网查下:java byte是做为最小的数字来处理的,它的值域被定义为-128~127,也就是signed byte,它的最高位被用来代表正负了1代表负,0代表正这样我们的错误原因也就被找出来了。而上面按照我们的思路byte范围应该是在0~255才对。既然byte最大整数只能代表127,那么我们就用7个01串来表示就好,将上面程序略作修改即可。
package M数排重;
import java.util.Random;
public class Test {
byte[] bytearray=new byte[100];;
/**
* 主函数
* @author lixiongzhi
*/
public static void main(String[] args) {
Test test=new Test();
Random random=new Random();
for(int i=0;i<200;i++){
int n=random.nextInt(50);
System.out.print(n+" ");
test.setBit(n);
}
System.out.println();
test.print(test.bytearray);
}
/**
* 2的n次方
* @param n
* @return
*/
private int N(int n){
int result=1;
for(int i=0;i<n;i++){
result*=2;
}
return result;
}
/**
* 整数n对应的bit并设为1
*/
private void setBit(int n){
//对应的byte数组下标
int index=n/7;
//byte[index]对应的第mod个bit
int mod=n%7;
//获取byte[index]转换成的01串
String str=byteToString(bytearray[index]);
//将str的第mod位设为1
System.out.print(str+" ");
str=setCharat(str, mod);
System.out.print(str+" ");
byte newbyte=StringToByte(str);
System.out.println(newbyte);
bytearray[index]=newbyte;
}
/**
* 将一个01串转化成byte
*/
private byte StringToByte(String str){
byte result=0;
for(int i=0;i<7;i++){
if(str.charAt(i)==(char)49){
result+=N(6-i);
}
}
return result;
}
/**
* 将一个byte转换成01串
* @return
*/
private String byteToString(byte n){
String str="";
for(int i=0;i<7;i++){
str+=n%2;
n/=2;
}
//将str倒序排
String str2="";
for(int i=6;i>=0;i--){
str2+=str.charAt(i);
}
return str2;
}
//设置str第index+1位为1的函数
private String setCharat(String str,int index){
if(str.charAt(index)!="1".charAt(0)){
String str2="";
for(int i=0;i<str.length();i++){
if(i==index){
str2+=1;
}else{
str2+=str.charAt(i);
}
}
return str2;
}
return str;
}
/**
* 排重后输出
* @param array
*/
private void print(byte array[]){
System.out.println("排重后结果为:");
for(int i=0;i<array.length;i++){
if(array[i]!=0){
for(int j=0;j<byteToString(array[i]).length();j++){
if(byteToString(array[i]).charAt(j)==(char)(49)){
int k=7*i+j;
System.out.print(k+" ");
}
}
}
}
}
}
再看输出结果:
4 0000000 0000100 4
25 0000000 0000100 4
15 0000000 0100000 32
33 0000000 0000010 2
6 0000100 0000101 5
28 0000010 1000010 66
12 0000000 0000010 2
5 0000101 0000111 7
30 1000010 1010010 82
11 0000010 0000110 6
49 0000000 1000000 64
22 0000100 0100100 36
6 0000111 0000111 7
2 0000111 0010111 23
39 0000000 0000100 4
24 0100100 0101100 44
38 0000100 0001100 12
25 0101100 0101100 44
27 0101100 0101101 45
27 0101101 0101101 45
排重后结果为:
2 4 5 6 11 12 15 22 24 25 27 28 30 33 38 39 49
很明显结果是正确的。
我们可以让随机数在0到49的范围内产生产生非常多比如1000个。这样可以比较明显的看出结果。
也可猜测一下排后结果就是0到49.(这不是绝对的)
下面是代码运行的结果:
排重后结果为:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
和我们的猜测一样。
因为在0到49随机产生1000个数,包含0到49所有的50个数据的可能性是非常大的。
分享到:
相关推荐
netty案例,netty4.1中级拓展篇十二《Netty流量整形数据流速率控制分析与实战》源码 https://mp.weixin.qq.com/mp/homepage?__biz=MzIxMDAwMDAxMw==&hid=6&sn=d9bbd1e54719c7dce584c34347c12f71
数据类型转换为浮点型数据,浮点型数据转换为整形数
浮点数与整形数据互转软件,支持单精度、双精度等格式。
整形数据转字符串程序,测试过,非常好用 整形数据转字符串程序
大数计算器,用计算机实现以整形、浮点型等类型进行数据计算溢出的问题
用C#编程语言实现数据结构传递整形变量、字符串、数组的方法
医美整形顾客存量数据分析表.docx
整形数据的溢出文本文件
整形数据的溢出.c源文件
我整理了一下PT100的分度表。 分两种类型,一种是unsigned int类型,这种类型每个数据占16位。一种是float型,这种类型每个数据占32位。
数据处理,数据整形,简单实用,用于对原始数据预处理
修改自正点原子STM32F407ZGT6函数,使得NRF2401可以接受和发发送整形数据,收发程序按照自己需要更改参数即可
1.领域:matlab,脉冲整形与匹配滤波的基带数据算法 2.内容:【含操作视频】基于脉冲整形与匹配滤波的基带数据传输,输出眼图,基带数据 3.用处:用于脉冲整形与匹配滤波的基带数据算法编程学习 4.指向人群:本硕博...
长整形数据的四则运算,用双向链表实现,代码有功能分类,设计思路
PHP-数据类型-整形
运用循环结构替代数组,基础的思路
SQL中数据类型分析 介绍了字符串 整形 及其他数据类型的选择
一个简单的整形电路,可以将正弦波整形为方波,以便单片机使用。
STM32的IIC存储和读取整形数据,下面的程序代码是使用stm32F03ZET6的I2C1(PB6,PB7)和AT24C02的EEPROM来测试的。希望对于需要的朋友有帮助。