《Java特种兵》1.3 简单数字游戏玩一玩

本文是《Java特种兵》的样章,感谢博文视点和作者授权本站发布

1.3 简单数字游戏玩一玩

数字游戏?没错,就是玩数字游戏!

Java怎么玩?马上见证下!

玩数字有什么用途呢?我们不是虚拟数据给别人看,而是通过玩数字转换,让我们更了解计算机的数字运算,也许数字运算可以有一些神奇的地方,有些变态的问题也不是我们想的那么简单。

这里不讲基本的“四则运算”,胖哥会讲一些运算符,然后再讲讲“大数字”是如何处理的。

†† 1.3.1 变量A、B交换有几种方式

胖哥认为有3种方法来实现变量交换,其中一种最简单的方法就是定义一个变量C作为中间量来实现,代码例子如下:

int C = A;

A = B;

B = C;

有人开始不想用“定义一个变量C作为中间量”来实现,而是尝试用“数据叠加后再减回来”的方法:

A = A + B;

B = A – B;

A = A – B;

这样也可以实现,A首先变成A与B的和,然后减掉B自然就得到A的值再赋值给B,此时B存储了A原先的值,再用A减掉B就得到原来B的值了。不过,这个方法有一个问题,就是A + B这个操作有可能会越界,越界后就会出现问题。

既然可能越界,聪明的小伙伴们又想到了另一个办法来解决这个问题,那就是“异或”运算:

A = A ^ B;

B = A ^ B;

A = A ^ B;

异或运算是按照二进制位进行“异或”的,对于A、B两个数字,如果某个二进制位上的A、B都是0或都是1,则返回0;如果一个是0,一个是1,则返回1,这样可以得到一个新的数字。这有什么用呢?当这个数字再与A发生“异或”的时候,就能得到B(这个大家可以自行反推)。这样的技巧其实是二进制位上的一个加法但不进位的做法(由于只有0、1,所以1+1=2后还是为0),但是这个运算是最低级的CPU位运算,所以它的效率是极高的,而且不会越界。

“异或”运算在计算机系统中大量存在,它的一个很大的优势就是可以按照反向的规则还原数据本身。

†† 1.3.2 将无序数据Hash到指定的板块

假如有一个长度为5000的数组,每个数组下标就像一个Hash桶那样存放一个链表,此时有一个数据A需要写入,随机吗?肯定不行,因为我们还要查询数据。那么将它放在Hash桶里面可以吗?似乎可以,下面一起来探讨一下。

我们希望写入的数据能按照某种规则读取出来,那么数据应当与数组的下标产生某种关系,这样写入和读取只要按照相同的规则就可以达到目的。此时假设一个“非负数”要写入,或许可以这样做,将这个数据%5000就可以得到下标了,这样在数字不断变化时,得到的下标也会不断变化,数据自然会相对均匀分布到5000个数组中(当然有特殊情况,这里不做探讨)。如果是负数,则需要采用取绝对值Math.abs(A) % 5000来得到下标。

还有没有其他的方法呢?单纯要将数据写入到数组中,可以使用A &4999来完成,这个操作得到的数据将会永远<=4999,因为它自身二进制位为0的部分&操作后都会被清除为0。理论上可以实现我们的要求,而且这种位操作也是最低级的系统运算,效率也是极高的。

只是这样的方法会有一个问题:什么问题呢?此时我们用数字11来说明会更好一些,如果数组的长度是11,那么下标就是0-10,自然输入的数据要和10来做&操作才能得到0-10之间的数字下标,10的二进制位是“1010”,那么意味着输入的任何数字与10进行&操作后都得不到0001、0100、0101这些数字,也就是对应到十进制的数字1、8、9。宏观上讲,如果数组长度是11,按照这种方式存入数据,那么1、8、9这几个数组下标下面永远也没数据,我们预想的是想将数据离散到0-10这些位置,但是有3个位置却永远没数据,这就是问题所在,而问题的根本就是二进制位置为0的地方将永远离散不到,因此要使用这样的方法最好选择相应二进制位都是1的数字,如1、127、255、511、1023等。

†† 1.3.3 大量判定“是|否”的操作

如果发现一个业务系统中的许多操作都是在判定是、否,很多时候大家为了节约空间不会为每一个是、否的值用一个单独int来存储,因为那样比较浪费空间。而一个int是4个字节,所以它可以存放32bit二进制位,一个二进制位就可以代表一个“是|否”。

这样的设计是没有问题的,而且很多小伙伴们都知道这样的设计,但是胖哥发现有些可爱的同学在设计过后,拿出来判定对应的位置是与否的时候,是先用Integer.toBinary String(int)转换为二进制字符串,然后从这个字符串中取出对应位置的char,再判定这个char是’0’还是’1’的操作。

这种操作显然有点过了,而且操作的时间复杂度很高,或许我们可以学一学Java提供的一些类中是如何处理的。例如“java.lang.reflect.Modifier”,它对类型的修饰符有各种各样的判定(例如,字节码中存储public final static这样的一长串内容只用一个数字来表达),那么它是如何做到的呢?请听胖哥慢慢道来:Java将这些符号进行了固定的规格编码,就像商品类型的名称与编号一样(这个编码会在生成class文件时存在,JVM运行时也会使用)。

◎ 是否为public,使用十六进制数据(0x00000001)表示。

◎ 是否为static,使用十六进制数据(0x00000008)表示。十六进制的8代表二进制的最后3位是100。

◎ 是否为final,使用十六进制数据(0x00000010)表示。十六进制的10代表二进制最后4位为1000。

在Modifier类中大家可以找到private、protected、synchronized、volatile、transient、native、interface、abstract、strict等各种类型的表达数字。

Java程序在读取字节码时,读取到一个数字,该数字只需要与对应的编码进行“&”(按位求与)操作,根据结果是否为0即可得到答案。设计有点小技巧吧!

此时有的小伙伴就会说:“很多时候,需要判定它是不是public final static的,这么多类型要一个个判定好麻烦。”胖哥告诉你,这种方式其实还可以打组合拳。组合拳如何打呢?用“或”运算,具体操作就是:

final static int PUBLIC_FINAL_STATIC = PUBLIC | FINAL | STATIC;

这个值将会事先保存在程序中,由于这三项内容的二进制并不冲突,所以做或运算就代表三者都成立的意思。当传入参数后,只需要与这个值做“按位求与”就能得到结果了。不过,现在“按位求与”的结果不是与0比较,而是与PUBLIC_FINAL_STATIC比较是否等值(因为需要每个二进制位都要对应上,才能证明它的3个特征都成立)。所有的二进制位都必须要匹配上,即使一个不匹配也不行,示例如下:

public static boolean isPublicFinalStatic(int mod) {

return (mod & PUBLIC_FINAL_STATIC) == PUBLIC_FINAL_STATIC;

}

†† 1.3.4 简单的数据转换

数据转换有两种,其中一种是进制转换,另一种是数字与byte[]的等值转换。我们先来看看进制转换。

◎ 将十进制数据转换为“二进制的字符串”,使用Integer.toBinaryString()、Long.toBinaryString()来操作。大家注意了,这里说的是二进制的字符串,数字本身就是以二进制形式存储的,在UI上要看到这个数字的二进制位,所以才转换成字符串来显示。

◎ 将十进制数据转换为“十六进制的字符串”,使用Integer.toHexString(int)来操作。类似的,在float、double、long中也有相应的方法存在。

◎ 将其他进制的数据转换为十进制数据,使用Integer.parseInt(String,int)、Integer. valueOf(String,int)来完成,其中第二个参数传入的就是字符串数据。例如:Integer.valueOf(“10”,16)返回的值就是16,Integer.valueOf(“10”,2)返回的值是2,这样就可以实现任意进制之间的转换了。long也提供了类似的方法。

数字与byte[]之间的转换是什么意思呢?大家都知道,在Java语言中,int是由4个字节(byte)组成的。在网络上发送数据的时候,都是通过byte流来处理的,所以会发送4个byte的内容,4个byte会由高到低顺序排列发送,接收方反向解析。在Java中可以基于DataOutputStream、DataInputStream的writeInt(int)和readInt()来得到正确的数据,代码如图1-6所示。

XTP_TNRA{V8L1LZWSI93)H7

图1-6 DataXXXStream对于数字的处理

如果使用了通道相关的技术,ByteBuffer则由相关的API来实现。这是原始的实现方式,如果其他语言提供的API希望将这些byte位交换位置(例如要求低位先发送),那么你就要自己来处理了,而处理方式就可以参看DataXXXStream的处理方式。

在DataXXXStream的类中,不仅仅有对int类型的处理,还有对boolean、byte、unsigned byte、short、unsigned short、char、int、long、float、unsigned float、double、UTF的处理,而且还有一个readFull()方法,这个方法要求读满一个缓冲区后才返回数据,它会在内部区循环处理。

在ByteBuffer的实现类中也提供了各种数据类型的put、get操作,内部也是通过byte转换来完成的。

在java.io.Bits、java.nio.Bits类中也有大量的数字与byte[]的转换操作(这两个类我们的程序无法直接使用,但是可以看源码),大家可以参考它们的代码来实现自己的特定需求。

†† 1.3.5 数字太大,long都存放不下

long采用8个字节来存放数字,它连时间的毫秒值、微秒值甚至纳秒值都可以存放下,它存放不下的数字很少见,但是它毕竟只有8个字节,如果真的遇到了某些变态的设计怎么办呢?此时需要使用BigDecimal来操作,它不是以固定长度的字节来存储数据,而是以对象的方式来管理位的。我们用一个例子来看看使用BigDecimal对一个大数字操作包含几个步骤。

首先将大数字加上10,输出结果。

然后将结果的byte位取出来以二进制形式展现。

最后根据二进制字符串反转为数字对象。

代码清单1-4 BigDecimal测试


import java.math.BigDecimal;
import java.math.BigInteger;

public class BigNumberTest {

	private static String lPad(String now ,
						int expectLength ,
						char paddingChar) {
		if(now == null || now.length() >= expectLength) {
			return now;
		}
		StringBuilder buf = new StringBuilder(expectLength);
		for(int i = 0 , paddingLength = expectLength - now.length();
							i < paddingLength ; i++) {
			buf.append(paddingChar);
		}
		return buf.append(now).toString();
	}

	public static void main(String []args) {
		//这个数字long是放不下的
		BigDecimal bigDecimal
= new BigDecimal("1233243243243243243243243243243243241432423432");
		System.out.println("数字的原始值是:" + bigDecimal);

		//bigDecimal = bigDecimal.add(BigDecimal.TEN);
		//System.out.println("添加10以后:" + bigDecimal);

		//二进制数字
		byte[] bytes = bigDecimal.toBigInteger().toByteArray();
		for(byte b : bytes) {
			String bitString = lPad(Integer.toBinaryString(b & 0xff) ,
									8 , '0');
			System.out.println(bitString);
		}
		//还原结果
		BigInteger bigInteger = new BigInteger(bytes);
		System.out.println("还原结果为:" + bigInteger);
	}
}

在这段代码中,有一个substring()、lPad()操作。这是因为Integer.toBinaryString(b)传入的虽然是byte,但是会转型为int,如果byte的第1个bit位是1,则代表是负数,那么转换为int的高24位将会填充1。其实我们不需要这24位,所以用了substring()。如果是正数,那么输出的字符串会将前面的0去掉,为了在显示上使用8位二进制对齐方式,所以在代码中用了lPad()。我们再来看看输出结果。

数字的原始值是:1233243243243243243243243243243243241432423432

添加10以后:1233243243243243243243243243243243241432423442

00110111

01001100

11110000

00101001

11111111

10001010

00010101

00001101

00011100

01111111

00101001

00000001

01000111

01000110

10110011

01111000

01100100

00011100

00001000

还原结果为:1233243243243243243243243243243243241432423442

数字能转换为二进制数据,又能还原成数字,理论上应该没有问题,大家也可以用一些比较小的数字做测试来印证这个结论(例如2、15、16、1024等)。不过,在印证的过程中,有的同学发现高位出现整个字节的8位全是0的情况,例如255,输出的结果是两个字节的二进制字符串:0000000011111111。大家很疑惑:既然高8位全是0,为何还要单独拿一个byte来存放呢?有一点要注意了,因为255是正数,而一个字节中的最高位变成了1,如果直接用11111111来表达就表示它是一个负数(具体值是-1),所以需要多一个字节来表达自己是正数。

long的存储能力到底有多大?

许多同学设计一些PK列的时候认为数字存储不下,用字符串来存放数字(当然不排除某种编码规则),但是用数字往往计算快速得多,而且空间也少很多。为了了解long的存储能力有多大,我们先看看int的存储能力有多大。Integer.MAX_VALUE的值为“2147483647”,也就是2G-1的大小。如何得来?自然是4字节对应32位,然后去掉负数和0得来的。这个值换算成十进制数据就是21亿,理论上很多表达不到那么大,或者说绝大部分表不会有这么多ID,但是若某些跳跃和历史数据超过这个数字怎么办?那么就用long吧,它的宽度是int的2倍,即4G*4G/2–1(为什么?自己想想)。十六进制数据0x7fffffffffffffffL,换算为十进制数据是“9223372036854775807”,这个数字看不出到底有多大,我们可以和时间进行比较。

Long.MAX_VALUE / (365l * 24 * 60 * 60 * 1000) = 292471208

Long.MAX_VALUE / (365l * 24 * 60 * 60 * 1000 * 1000) = 292471

Long.MAX_VALUE / (365l * 24 * 60 * 60 * 1000 * 1000000) = 292

如果存放毫秒值,则可以存放2.92亿年,微妙值可以存放29.2万年,纳秒值可以存放292年的数据。换句话说,一个表的ID,即使加上跳跃每秒有10E9个ID自动增长,也可以增加292年的数据不重复,胖哥认为这种并发在现在的计算机时代还不存在。小伙伴们,通过这种量化后,自然应该理解某些设计应该如何做了吧。

数字游戏玩到这里就结束了,在本书的后文中,胖哥还会提到一些和数字相关的小玩意,例如i++与++i的问题,或许胖哥的说法与在教材中看到的解释不一样哦。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 《Java特种兵》1.3 简单数字游戏玩一玩


Latest posts by miniWolfer (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (1)
    • 匿名
    • 2014/10/28 3:31下午

    麻烦继续更新呢 我在支持楼主 吼吼

您必须 登陆 后才能发表评论

return top