事物的正反两面被哲学家讨论了几千年。计算机里的0和1也照旧玩出了各种花样。
二进制数 VS 十进制数
本小节讲二进制写法,以及到十进制的转换方法,如果已熟悉这些内容可以直接跳到下一小节。
我们生活在一个十进制的世界中。10个一毛就是一块,10个一两就是一斤。在数学上有满十进一或借一当十。
十进制数的基数就是0到9,因此所有的十进制数都是由0到9这九个数字组合出来的。
计算机底层处理的都是二进制数,可以对比十进制数来看看二进制数的特点:
满二进一或借一当二,基数是0和1,就是说所有的二进制数都是由0和1这两个数字组合出来的。
就十进制而言,十个1已经达到“满十”的条件,所以要“进一”,于是就是10,这是个十进制数,它的值就是十,因为是十个1合在了一起。
就二进制而言,两个1已经达到“满二”的条件,所以要“进一”,于是就是10,这是个二进制数,它的值就是二,因为是两个1合在了一起。
如果刚刚这个明白了,结合十进制和二进制的特点,接下来就非常容易理解了:
1 + 1=2 -> 10。
1 + 1 + 1=3=2 + 1 -> 10 + 1 -> 11。
1 + 1 + 1 + 1=4=3 + 1 -> 11 + 1 -> 100。
照此类推,列出几个十进制和对应的二进制:
0 -> 000
1 -> 001
2 -> 010
3 -> 011
4 -> 100
5 -> 101
接下来尝试找出二进制和十进制之间的换算关系。
首先,十进制数是怎么使用每个位置上的数字表示出来的呢?相信所有人都很熟悉。如下面示例:
123 -> 100 + 20 + 3
123 -> 1 * 100 + 2 * 10 + 3 * 1
因十进制满十进一,要想办法和十联系起来,100就是10的2次方,10是10的1次方,1是10的0次方,于是:
123 -> 1 * 10 ^ 2 + 2 * 10 ^ 1 + 3 * 10 ^ 0;
进而,我们发现百位的位置是3,但次方却是2,正好是3减去1,十位的位置是2,但次方是1,正好是2减去1,个位就是1减去1,也就是0次方了。
于是,这个公式就出来了,太简单了,大家都知道,就不写了。
然后,我们把这个“套路”搬到二进制数里试试看吧,只不过二进制数是满二进一,因此要用2的次方。
000 -> 0 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0
000 -> 0 * 4 + 0 * 2 + 0 * 1 -> 0
000 -> 0
001 -> 0 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2 ^ 0
001 -> 0 * 4 + 0 * 2 + 1 * 1 -> 1
001 -> 1
010 -> 0 * 2 ^ 2 + 1 * 2 ^ 1 + 0 * 2 ^ 0
010 -> 0 * 4 + 1 * 2 + 0 * 1 -> 2
010 -> 2
011 -> 0 * 2 ^ 2 + 1 * 2 ^ 1 + 1 * 2 ^ 0
011 -> 0 * 4 + 1 * 2 + 1 * 1 -> 3
011 -> 3
100 -> 1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0
100 -> 1 * 4 + 0 * 2 + 0 * 1 -> 4
100 -> 4
101 -> 1 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2 ^ 0
101 -> 1 * 4 + 0 * 2 + 1 * 1 -> 5
101 -> 5
我们发现算出来的正好都是其对应的十进制数。这是巧合吗?当然不是了。其实:
这就是二进制数向十进制数的转化方法。
我们也可以模仿数学,推导出个公式来:
d=b(n) + b(n - 1) + ... + b(1) + b(0)
b(n)=a * 2 ^ n,(a={0、1},n >=0)
就是把二进制数的每一位转化为十进制数,再加起来即可。
负数的二进制 VS 正数的二进制
上一小节都是以正数举例。除了正数之外,还有负数和零。
因此,计算机界规定,在需要考虑正负的时候,二进制的最高位就是符号位。
即这个位置上的0或1是用来表示数值符号的,而非用来计算数值的,且规定:
0表示为正数,1表示为负数。
那0既不是正数也不是负数,该怎么表示呢?把0的二进制输出一下:
0 -> 00000000
发现全是0,最高位也是0,因此0是一种特殊情况。
接下来开始讲解负数的二进制表示,保证看完后有一种“恍然大悟”的感觉(如果没有,那我也没办法),哈哈。
长期以来受数学的影响,要把一个正数变成对应的负数,只需在前面加一个负号“-”即可。
基于此,再结合上面计算机界的规定,我们很容易想当然的认为,一个正数只要把它的最高位由0设置为1就变成了对应的负数,像这样:
因为 1的二进制是,00000001
所以-1的二进制是,10000001
郑重声明,这是错误的。继续往下看就知道原因了。
首先会从官方的角度给出正确结果(装b用的),然后会从个人的角度给出正确结果(恍然大悟用的)。
站在官方(或学术)的角度,先引入三个概念:
原码:把一个数当作正数(负数的话把负号去掉即可),它的二进制表示就叫原码。
反码:把原码中的0变成1、1变成0(即0和1对调),所得到的就叫反码。
补码:反码加上1,所得到的就叫补码。
(这是学术界的名词,不要纠结为什么,记住即可)
还以-1为例,进行一下推导:
把 -1当作 1,原码是,00000001
把0和1对调,反码是,11111110
然后加上 1, 补码是,11111111
于是-1的补码是,11111111。再使用类库中的工具类输出一下-1的二进制形式,发现竟然还是它。这也不是巧合,因为:
在计算机中,负数的二进制就是用它的补码形式表示的。
这就是官方的说法,总喜欢整一些名词来把大家弄得一懵一懵的。
下面就站在个人角度,以最“土鳖”的方式来揭秘。
首先,-1的二进制是11111111这种形式一下子确实不容易接受。
反倒是把-1的二进制假设为10000001更容易让人接受,因为与它对应的1的二进制是00000001。
这样从数值的大小上(即绝对值)来看都是1,从符号上来看一个是1一个是0恰好表示一负一正,简直“堪称完美”。
那为什么这种假设的形式却是错的呢?
因为从十进制的角度来说,1 + (-1)=0。
再按假设的形式把它们转换为对应的二进制,
00000001 + 10000001=10000010,
依照假设,这个结果的值是-2。
可见,一个是0,一个是-2,这显然是不对的。虽然是采用不同的进制,但结果应该是一样的才对。
很显然,二进制这种计算方式的结果是错误的,错误的原因是,-1的二进制形式不能按照我们假设的那种方式进行。
那-1的二进制应该按什么逻辑去计算呢?相信你已经猜到了。
因为,-1=0 - 1,所以,
-1=00000000 - 00000001=11111111。
因此,-1的二进制就是11111111。这样一来,
-1 + 1=11111111 + 00000001=00000000=0。
这样是不是一下子就明白了-1的二进制为什么全是1了。因为这种形式满足了数值计算上的需要。
同理可以算下-2的二进制,
-2=-1 - 1=11111111 - 00000001=11111110。
其实原码/反码/补码之间的转换关系也是基于正数和负数的和为零而设计出来的。仔细体会下便可明白。
可见,官方角度和个人角度的本质是一样的,只不过一个阳春白雪、一个下里巴人。
这让我想起来了雅和俗,很多人标榜着追求雅,其实他们需要的恰恰是俗。
下面是一些正数和对应负数的例子:
2,00000010
-2,11111110
5,00000101
-5,11111011
127,01111111
-127,10000001
可以看到十进制数的和是0,对应二进制数的和也是0。
这才是正确的负数的二进制表示,虽然看起来的跟感觉起来的不太一样。
就十进制来说,当位数固定后,所有位置上都是9时,数值达到最大,如最大的四位数就是9999。
对于二进制来说也是一样的,除去最高位0表示正数外,剩余的位置全部是1时,数值达到最大,如最大的八位数就是01111111,对应的十进制数就是127。
一个字节的长度就是8位,因此一个字节能表示的最大正数就是127,即一个0带着7个1,这是正向的边界值了。
通过观察负数,除去最高位1表示负数外,后面7位全部为0时,应该是负数的最小值,即一个1带着7个0,对应的十进制数是-128,这是负向的边界值了。
而且正向和负向的边界值是有关系的,你发现了吗?就是正向边界值加上1之后的相反数即为负向边界值。
二进制的常规操作
这些内容应该都非常熟悉了,瞄一眼即可。
位操作
与(and):
1 & 1 -> 1
0 & 1 -> 0
1 & 0 -> 0
0 & 0 -> 0
或(or):
0 | 0 -> 0
0 | 1 -> 1
1 | 0 -> 1
1 | 1 -> 1
非(not):
~0 -> 1
~1 -> 0
异或(xor):
0 ^ 1 -> 1
1 ^ 0 -> 1
0 ^ 0 -> 0
1 ^ 1 -> 0
移位操作
左移(<<):
左边丢弃(符号位照样丢弃),右边补0。
移完后,最高位是0为正数,是1为负数。
左移一位相当于乘2,二位相当于乘4,以此类推。
当左移一个周期时,回到原点。即相当于不移。
超过一个周期后,把周期部分除掉,移动剩下的。
移动的位数和二进制本身的长度相等时,称为周期。如8位长度的二进制移动8位。
右移(>>):
右边丢弃,正数左边补0,负数左边补1。
右移一位相当于除2,二位相当于除4,以此类推。
在四舍五入时,正数选择舍,负数选择入。
正数右移从都丢弃完开始往后数值都是0,因为从左边补进来的都是0,直到到达一个周期时,回到原点,即回到原来的数值。相当于不移。
负数右移从都丢弃完开始往后数值都是-1,因为从左边补进来的都是1,直到到达一个周期时,回到原点,即回到原来的数值。相当于不移。
超过一个周期后,把周期部分除掉,移动剩下的。
无符号右移(>>>):
右边丢弃,无论正数还是负数左边都是补0。
因此对于正数来说和右移(>>)没有什么差别。
对于负数来说会变成正数,就是使用原来的补码形式,丢弃右边后当作正数来计算。
为什么没有无符号左移呢?
因为左移时,是在右边补0的,而符号位是在最左边的,右边补的东西是影响不到它的。
可能有人会想,到达一个周期后,再移动的话不就影响到了嘛,哈哈,在一个周期的时候是会进行归零的。
二进制的伸/缩
以下内容都假定高位字节在前低位字节在后的顺序。
伸:
如把一个字节伸长为两个字节,则需要填充高位字节。(等于把byte类型赋给short类型)
其实就是这个字节原样不动,在它的左边再接上一个字节。
此时符号和数值大小都保持不变。
正数符号位是0,伸长时高位字节填充0。
00000110 -> 00000000,00000110
负数符号位是1,伸长时高位字节填充1。
11111010 -> 11111111,11111010
缩:
把两个字节压缩为一个字节,需要截断高位字节。(等于把short类型强制赋给byte类型)
其实就是左边字节直接丢弃,右边字节原样不动的保留。
此时符号和数值大小都可能发生改变。
如果压缩后的字节仍能放得下这个数,则符号和数值大小都保持不变。
具体来说就是如果正数的高位字节全是0,同时低位字节的最高位也是0。或负数的高位字节全是1,同时低位字节的最高位也是1。截断高位字节不会对数造成影响。
00000000,00001100 -> 00001100
11111111,11110011 -> 11110011
如果压缩后的字节放不下这个数,则数值大小一定改变。
具体说就是如果正数的高位字节不全是0,负数的高位字节不全是1,截断高位字节肯定会对数的大小造成影响。
至于符号是否改变取决于原符号位和压缩后的符号位是否一样。
例如,压缩后大小发生改变,符号不变的如下:
00001000,00000011 压缩为 00000011,还是正数
11011111,11111101 压缩为 11111101,还是负数
例如,压缩后大小和符号都发生改变的如下:
00001000,10000011 压缩为 10000011,正数变负数。
11011111,01111101 压缩为 01111101,负数变正数。
整数的序列化和反序列化
一般来说,一个int类型是由四个字节组成的,在序列化时,需要将这四个字节一一拆开,按顺序放入到一个字节数组中。
在反序列化时,从字节数组中拿出这四个字节,把它们按顺序接在一起,重新解释为一个int类型的数字,结果应该保持不变。
在序列化时,主要用到的就是移位和压缩。
首先将要拆出来的字节移到最低位(即最右边),然后强制转换为byte类型即可。
假如有一个int类型数字如下:
11111001,11001100,10100000,10111001
第一步,右移24位并只保留最低八位,
byte b3=(byte)(i >> 24);
11111111,11111111,11111111,11111001
11111001
第二步,右移16位并只保留最低八位,
byte b2=(byte)(i >> 16);
11111111,11111111,11111001,11001100
11001100
第三步,右移8位并只保留最低八位,
byte b1=(byte)(i >> 8);
11111111,11111001,11001100,10100000
10100000
第三步,右移0位并只保留最低八位,
byte b0=(byte)(i >> 0);
11111001,11001100,10100000,10111001
10111001
这样就产生了四个字节,把它们放入字节数组就可以了。
byte[] bytes=new byte[]{b3, b2, b1, b0};
在反序列化时,主要用到的就是伸长和移位。
首先从字节数组中拿出一个字节,将它转换为int类型,然后再处理符号问题,接着再左移到适合位置。
第一步:
取出第一个字节,
11111001
然后伸长为int,
11111111,11111111,11111111,11111001
因为它的符号位就表示了原来整数的符号位,因此不用处理符号,直接左移24位,
11111001,00000000,00000000,00000000
第二步:
取出第二个字节,
11001100
然后伸长为int,
11111111,11111111,11111111,11001100
因为它的符号位是处在原来整数的中间位置的,因此它不表示符号而表示数值,需要处理符号位,就是执行一个与操作,
如下,上面两行相与得到第三行,
11111111,11111111,11111111,11001100
00000000,00000000,00000000,11111111
00000000,00000000,00000000,11001100
接着左移16位
00000000,11001100,00000000,00000000
第三步,
取出第三个字节,
10100000
然后伸长为int,
11111111,11111111,11111111,10100000
然后处理符号位,
00000000,00000000,00000000,10100000
接着左移8位,
00000000,00000000,10100000,00000000
第四步,
取出第四个字节,
10111001
然后伸长为int,
11111111,11111111,11111111,10111001
然后处理符号位,
00000000,00000000,00000000,10111001
接着左移0位,
00000000,00000000,00000000,10111001
这样四步就产生了四个结果,如下:
11111001,00000000,00000000,00000000
00000000,11001100,00000000,00000000
00000000,00000000,10100000,00000000
00000000,00000000,00000000,10111001
可以看到四个字节都已经位于自己应该在的位置上了。
最后来一个加法操作就可以了,其实或操作也是可以的。
i=i4 + i3 + i2 + i0
i=i4 | i3 | i2 | i0
这样我们就将字节数组中的四个字节合成为一个int类型的数字了。
模拟实现无符号数
无符号数,即最高位不是符号位而是数值位。
有一些语言如Java不支持无符号数,所以需要使用有符号数来模拟实现。
因为同一个类型作为无符号数时的范围会大于作为有符号数时的范围,因此会用更长的类型存放短类型的无符号数。
如byte类型是一个字节,作为有符号数时范围是-128到127,作为无符号数时范围是0到255,所以至少需要用两个字节的short类型来存放。
处理方法很简单,只需两步,伸长和处理符号位。
假如有一个字节是,10101011,这是一个byte类型的负数。
第一步,伸长,此时变成两个字节了,但还是一个负数
11111111,10101011
第二步,处理符号,即执行一个与操作
11111111,10101011
00000000,11111111
00000000,10101011
这就已经处理完了,由一个字节的负数变成了两个字节的正数。
其实就是将原来的字节前面(即左边)接上去一个全0的字节。
当byte作为无符号数,取到最大值255时,二进制是这样的
00000000,11111111
此时也只不过才刚刚使用完低位置。
因此使用长类型表示短类型的无符号数,对长类型的字节利用效率最高也就百分之五十了。
对于这种情况,在序列化时,其实只需写入低半部分的字节即可。
在反序列化时,一是要用长类型来承接,二是所有字节都要处理符号,作为无符号数对待。
PS:这次算是认认真真的复习了十年前在大学里的专业课基础知识。
其实我是在写“品Spring”系列文章时,发现最好能熟悉Java的字节码(.class)文件内部结构。
在尝试解析字节码文件时,发现它里面存储的都是无符号数,所以需要写一个把字节数组反序列化为无符号数的工具。
在写工具时看了一点JDK相关部分的源码,就索性把二进制的基本知识和操作都亲自写代码测试了一遍。