前言
如何将两个数合并成一个数又能恢复回原来两个数？这个问题在某次撸代码地时候忽然产生，当时没有想到如何解决，但最近忽然想到了思路，然后趁着这个五一假期实现一下。
原理
这个问题，可不能使用普通的加减乘除解决，因为即使合并得到新数，也无法恢复成之前合并前的那两个数，如 1+3=4，但是4可以有 2+2…很多种方式。
我们可以采用二进制的方式解决这个问题。
合并
假设有两个数 1，3,在计算机语言里，默认是用 int 类型存放数值，一个 int类型 有32 个位，将 1，3分别转成二进制可得到：00000000000000000000000000000001，00000000000000000000000000000011，然后这两个值拼接起来就可以形成一个新的值,即0000000000000000000000000000000100000000000000000000000000000011，可以使用long类型保存，因为long类型有64位，刚好满足这两个值的拼接起来的长度。由此得到新值4294967299。
恢复
现在需要将4294967299 恢复成 1,3，如何处理？很简单，由于4294967299是1,3二进制拼接起来得到的，只要将4294967299转成二进制0000000000000000000000000000000100000000000000000000000000000011，又因为1,3分别占32位，所有，以第32位[从0开始]为分界点，分别得到00000000000000000000000000000001,00000000000000000000000000000011，将其转为10进制，即可得到1,3
实现
合并
还是以1，3为例子。先初始化 result 的值为 left,由于 result 是 long 类型，所以共有64位，此时 result 为 0000000000000000000000000000000000000000000000000000000000000001。左移32位，得到0000000000000000000000000000000100000000000000000000000000000000。接着合并right到 result 的 后32位中，我们可以才有 |运算符，刚可以将值为1的位保留起来，从而得到 0000000000000000000000000000000100000000000000000000000000000011,转成10进制就得到4294967299
/**
* 将合并 left,right 成一个数
* @param left 用于合并的数1
* @param right 用于合并的数2
* @return left,right 合并后的数
*/
private static long mergeNum(int left, int right){
if(left<0||right<0){
//不支持负数合并
throw new RuntimeException("not support negative to merge ");
}
long result=left;
result<<=32;
result|=right;
return result;
}
算法最大支持Integer.MAX_VALUE参数，因为Integer.MAX_VALUE 只占31位，最高位始终为0，也使得到右移时，不会因为最高位而导致补1的情况发送。参考博客
至于为什么不支持复数，因为负数的二进制需要经过反码，补码，与当前合并算法不兼容，加上没有暂时没有想到更好的算法，所以暂时不考虑这负数的情况。参考博客
恢复
还是以4294967299为例子。由上可知，4294967299是由1,3的二进制数拼接起来得到的。所以要算出 1，就是将val 右移32位补0，即可得到0000000000000000000000000000000000000000000000000000000000000001，转为二进制就是 1。最后要算出3。首先需要将高32位去除，可以才有左移方式将高32位变成低32位：0000000000000000000000000000001100000000000000000000000000000000,然后右移32位，使得高32位变成低32位，得到0000000000000000000000000000000000000000000000000000000000000011，转为二进制就是 3
/**
* 将 val 恢复成合并前的两个数
* @param val 合并后的数
* @return 合并 val 前的两个数
*/
private static int[] splitNum(long val){
long left=val>>32;
long right=(val<<32)>>32;
return new int[]{Long.valueOf(left).intValue(),Long.valueOf(right).intValue()};
}
源码
package org.example;
public class AlgorithmTest {
public static void main(String[] args) {
test(Integer.MAX_VALUE,Integer.MAX_VALUE);
test(123,143);
test(1,3);
test(0,123);
test(24,0);
}
private static void test(int left ,int right){
System.out.println("------test["+left+","+right+"]------");
outBinary("left",left);
outBinary("right",right);
long mergeNum= mergeNum(left,right);
outBinary("mergeNum",mergeNum);
int[] splitNums = splitNum(mergeNum);
System.out.printf("------mergeNum=%d,splitNum=[%d,%d]\r\n",mergeNum,splitNums[0],splitNums[1]);
}
/**
* 将 val 恢复成合并前的两个数
* @param val 合并后的数
* @return 合并 val 前的两个数
*/
private static int[] splitNum(long val){
long left=val>>32;
long right=(val<<32)>>32;
return new int[]{Long.valueOf(left).intValue(),Long.valueOf(right).intValue()};
}
/**
* 将合并 left,right 成一个数
* @param left 用于合并的数1
* @param right 用于合并的数2
* @return left,right 合并后的数
*/
private static long mergeNum(int left, int right){
if(left<0||right<0){
//不支持负数合并
throw new RuntimeException("not support negative to merge ");
}
long result=left;
result<<=32;
result|=right;
return result;
}
/**
* 输出 val 的二进制值信息
* @param prefix 输出日志前缀
* @param val 要输出二进制的值
*/
private static void outBinary(String prefix,long val){
System.out.println(prefix+".val="+val);
StringBuilder sb=new StringBuilder();
int n=Long.numberOfLeadingZeros(val);
for (int i = 0; i < n; i++) {
sb.append(0);
}
String valBinaryStr=Long.toBinaryString(val);
sb.append(valBinaryStr);
System.out.println(prefix+".valBinaryStr = "+valBinaryStr);
System.out.println(prefix+". = "+valBinaryStr.length());
System.out.println(prefix+".() = "+sb.toString());
System.out.println(prefix+".() = "+sb.length());
}
}
执行结果
------test[2147483647,2147483647]------
=2147483647
= 1111111111111111111111111111111
= 31
() = 0000000000000000000000000000000001111111111111111111111111111111
() = 64
=2147483647
= 1111111111111111111111111111111
= 31
() = 0000000000000000000000000000000001111111111111111111111111111111
() = 64
=9223372034707292159
= 111111111111111111111111111111101111111111111111111111111111111
= 63
() = 0111111111111111111111111111111101111111111111111111111111111111
() = 64
------mergeNum=9223372034707292159,splitNum=[2147483647,2147483647]
------test[123,143]------
=123
= 1111011
= 7
() = 0000000000000000000000000000000000000000000000000000000001111011
() = 64
=143
= 10001111
= 8
() = 0000000000000000000000000000000000000000000000000000000010001111
() = 64
=528280977551
= 111101100000000000000000000000010001111
= 39
() = 0000000000000000000000000111101100000000000000000000000010001111
() = 64
------mergeNum=528280977551,splitNum=[123,143]
------test[1,3]------
=1
= 1
= 1
() = 0000000000000000000000000000000000000000000000000000000000000001
() = 64
=3
= 11
= 2
() = 0000000000000000000000000000000000000000000000000000000000000011
() = 64
=4294967299
= 100000000000000000000000000000011
= 33
() = 0000000000000000000000000000000100000000000000000000000000000011
() = 64
------mergeNum=4294967299,splitNum=[1,3]
------test[0,123]------
=0
= 0
= 1
() = 00000000000000000000000000000000000000000000000000000000000000000
() = 65
=123
= 1111011
= 7
() = 0000000000000000000000000000000000000000000000000000000001111011
() = 64
=123
= 1111011
= 7
() = 0000000000000000000000000000000000000000000000000000000001111011
() = 64
------mergeNum=123,splitNum=[0,123]
------test[24,0]------
=24
= 11000
= 5
() = 0000000000000000000000000000000000000000000000000000000000011000
() = 64
=0
= 0
= 1
() = 00000000000000000000000000000000000000000000000000000000000000000
() = 65
=103079215104
= 1100000000000000000000000000000000000
= 37
() = 0000000000000000000000000001100000000000000000000000000000000000
() = 64
------mergeNum=103079215104,splitNum=[24,0]