逻辑左移时,最高位丢失,最低位补0;

逻辑右移时,最高位补0,最低位丢失;

算术左移时,依次左移一位,尾部补0,最高的符号位保持不变。

算术右移时,依次右移一位,尾部丢失,符号位右移后,原位置上复制一个符号位;

循环左移时,将最高位重新放置最低位

循环右移时,将最低位重新放置最高位

1010100010101

逻辑左移一位结果为 0101000101010

逻辑右移一位结果为 0101010001010

算术左移一位结果为 1101000101010

算术右移一位结果为 1101010001010

循环左移一位结果为 0101000101011

循环右移一位结果为 1101010001010

机器零

机器零指机器数所表示的零的形式。

机器零与真值零的区别是:机器零在数轴上表示为0点及其附近的一段区域,即在计算机中小到机器数的精度达不到的数均视为“机器零”,而真值零则表示0这一个点。

若要求全零表示机器零,则阶码应用移码表示、尾数用补码表示(此时阶码为最小阶,尾数为零,移码最小阶为全“0”,补码零的形式也为“0”)

计算机中机器零是指:

1、如果一个浮点数的尾数全为0,则不论其阶码为何值,计算机在处理时都把这种浮点数当作零看待;

2、如果一个浮点数的阶码小于它所表示范围的最小值,则不论其尾数为何值,计算机在处理时都把这种浮点数当作零看待。

计算机保存数字的位有限,所能表示最小的数也有范围,当一个表示方式比它所能表示的数更小时,计算机无法表示,就作为0处理,实际上,这个数也很接近0了,主要还是从数学上理解。

字符集与编码——定长与变长

https://my.oschina.net/goldenshaw/blog/307708

img

假设我们现在有个文件,内容是00000001,假如定长2位(这里的位指十进制的位)是唯一的编码方案,用它去解码,就会得到“hhhe”(可以对比图上的编码,00代表h,所以前6个0转化成3个h,后面的01则转化成e)。

但是,如果定长2位不是唯一的编码方案呢?如上图中的定长4位方案,如果我们误用定长4位去解码,结果就只能得到“he”(0000转化为h,0001转化为e)!

文本文件作为一种通用的文件,在存储时一般都不会带上其所使用编码的信息。编码信息与文件内容的分离,其实这正是乱码的根源。

其实变长多字节方案更早出现,比如GB2312,采用变长主要为了兼容一字节的ASCII,汉字则用两字节表示(这也是迫不得已的事,一字节压根不够用)。随着计算机在全世界的推广,各种编码方案都出来了,彼此之间的转换也带来了诸多的问题。采用某种统一的标准就势在必行了,于是乎天上一声霹雳,Unicode粉墨登场!

对于只用到ASCII字符的人来说,比如老美,让他们采用Unicode,多少还是有些怨言的。怎么说呢?比如“he”两个字符,用ASCII只需要保存成6865(16进制),现在则成了00680065,前面两个毫无作用的0怎么看怎么碍眼,原来假设是1KB的文本文件现在硬生生就要变成2KB,1GB的则变成2GB!

字符之间并不是平等的。用数学的语言来说,每个字符出现的机率不是等概率的,但表示它们却用了同样长度的字节。学过《数据结构与算法》的同学可能听过哈夫曼编码(Huffman Coding),又称霍夫曼编码,就为了解决这样的问题。

如果你对前一篇所发的莫尔斯电码图还有印象,你就会发现,字母e只用了一个点(dot)来编码。

img

其它字母可能觉得不公平,为啥我们就要录入那么多个划(dash)才行呢?这里面其实是有统计规律支撑的。e出现的概率是最大的。z你能想到什么?

著名的Brewer猜想说:对于现代分布式应用系统来说,数据一致性(Consistency)、系统可用性(Availability)、服务规模可分区性(Partitioning)三个目标(合称CAP)不可同时满足,最多只能选择两个。

img

通过前面分析,我们知道,定长二字节方案无法满足容量增长,转向定长四字节又会引发了效率危机,最终,Unicode编码方案演化成了变长的UTF-16编码方案。那么UTF-8方案又是如何来的呢?为何不能统一成一个方案呢?搞这么多学起来真头痛!

UTF-8因为能兼容ASCII而受到广泛欢迎,但在保存中文方面,要用3个字节,有的甚至要4个字节,所以在保存中文方面效率并不算太好,与此相对,GB2312,GBK之类用两字节保存中文字符效率上会高,同时它们也都兼容ASCII,所以在中英混合的情况下还是比UTF-8要好,但在国际化方面及可扩展空间上则不如UTF-8了。

其实GBK之后又还有GB18030标准,采用了1,2,4字节变长方案,把Unicode字符也收录了进来。GB18030其实是国家强制性标准,但感觉推广并不是很给力。

变长设计的核心问题自然就是如何区分不同的变长字节,只有这样才能在解码时不发生歧义。

利用高位作区分

还是以前面的例子来看,我们设计了几种变长方案

img

第一种方案的想法很美好,它试图跟随编号来自然增长,它还是可以编码的,但在解码时则遇到了困难。让我们来看看。

image

可见,由于低位的码位被“榨干”了,导致单个位与多位间无法区分,所以这种方案是行不通的。

第二种方案,低位空间有所保留,5及以上的就不使用了。然后我们通过引入一条变长解码规则:

从左向右扫描,读到5以下数字按单个位解码;读到5或以上数字时,把当前数字及下一个数字两位一起读上来解码。

让我们来看个实例

image

这种方案避免了歧义,因此是可行的方案,但这还是非常粗糙的设计,如果我们想在这串字符中搜索“o”这个字符,它的编码是3,这样在匹配时也会匹配上53中的3,这种设计会让我们在实现匹配算法时困难重重。我们可以在跟随位上也完全舍弃低位的编码,比如以55,56,57,58,59,65,66…这样的形式,但这样也会损失更多的有效编码位。

GB2312,GBK,UTF-8的基本思想也是如此。下面也简单示例一下(0,1代表固定值;黑色的X代表可以为0或1,为有效编码位):

image

注:GBK第二字节最高位也可能为0.

其实关键就在于用高位保留位来做区分,缺点就是有效编码空间少了,可以看到三字节的UTF-8方式中实际有效的编码空间只剩两字节。但这是变长方案无法避免的。

我们还可以看到,由于最高位不同,多字节中不会包含一字节的模式。对于UTF-8而言,二字节的模式也不会包含在三字节模式中,也不会在四字节中;三字节模式也不会在四字节模式中,这样就解决上面所说的搜索匹配难题。你可以先想想看为什么,下面的图以二,三字节为例说明了为什么。

image

可以看到,由于固定位上的0和1的差别,使得二字节既不会与三字节的前两字节相同,也不会它的后两字节相同。其它几种情况原理也是如此。

利用代理区作区分

让我们再来看另一种变长方案。用所谓代理区来实现。

image

这里挖出70-89间的码位,形成横竖10*10的编码空间,使得能再扩展100个编码空间。原来2位100个空间损失了20还剩80,再加上因此而增加的100个空间,总共是180个空间。这样一种变长方式也就是UTF-16所采用的,具体的实现我们留待后面再详述。

好了,关于定变长的问题,就讲到这里,下一篇将继续探讨前面提及但还未深入分析的一些问题。