文档章节

有趣的二进制

wier
 wier
发布于 2017/03/20 07:38
字数 2750
阅读 5467
收藏 287
点赞 11
评论 22

我们来看上一篇的一个Varint算法,这个算法的目的是为了令一个整型占用更少的字节,比如小于127的数字,只需占用一个字节即可,小于16384的数字,采用2个字节即可。算法如下:

 while (true) {
  if ((value & ~0x7F) == 0) {
    buffer[position++] = (byte) value;
    return;
  } else {
    buffer[position++] = (byte) ((value & 0x7F) | 0x80);
    value >>>= 7;
  }
}

我们来看看具体图例:

我们看到在小于2097153期间,占用空间会小于4个字节,这个优势还比较明显,不过也有弊端,比如超过268435456之后会有占用5个字节,考虑到大多数情况下,并不会应用到这么大的数字,优化空间方面还是不错的。

通过上述算法实现,我发现优秀的应用算法都会大量用到了位运算,而位运算在工作中却很少用到。位运算速度要快于整数运算的,特别是整数乘法,需要10个或者更多个时钟,若果采用移位操作一个或者2个时钟就够了,不过由于我们常采用十进制来进行算术运算,对二进制的位运算不够熟悉,阅读起来会比较耗费精力,所以借助上述算法实现,我们分析一下位运算的优势以及应用,从而更好的理解二进制。上述代码中,有运用到移位操作,位运算,字节序等相关知识点,我们一一分析。

进位制

我们知道,计算机的存储和处理的信息都是以二进制的,虽然在编写程序的期间数运算还是采用10进制表示,但到机器执行的时候,还会以2进制来进行处理。对于有10个指头的人来说,熟知10进制是很自然的事情,你看教小孩子数学的时候,都是先从数指头开始的,那么若是我们只有2个指头,是不是我们现在会更好理解二进制了?

 

其他进制转换10进制

大多数教材会教大家二进制和十进制如何互换,但多数说都是死记硬背式的,并没有去讲解真正含义,换一个进制之后,依然不会,我们回到最根本的一些计数方法上,从10进制来推算。比如我们看一个数字1001,采用十进制表示是:1x10^3+0*10^2+0*10^1+1*10^0。首先从右往左,我们可以看成是从低位到高位,每高一位,指数+1,其次10进制是以10为底数,其三这个公式是采用10进制算术进行计算的(用什么进制算出答案就相当于把当前进制转换为了什么进制了)。这个方式适合所有的进制转换,理解了这个,后续的进制转换都会很容易理解。

2进制的比较简单,我们直接忽略,我们来看下应用到3进制,同样是1001,转换10进制公式:1x3^3+0*3^2+0*3^1+1*3^0=28,我们发现只是底数改变,因为是3进制,所以以3为底数,另外计算方式还是采用10进制算式计算,这表明用10进制算出的答案,就相当于3进制转换为10进制,1001转换为10进制就是28。

那为何不采用其他进制来计算?采用其他进制计算,那么其他进制的乘法口诀你的熟练一遍了,比如10进制的99乘法口诀,你用其他进制的乘法口诀得自己来演绎一遍了,如此这个和我们的常用习惯有些相驳,换算起来会比较慢,所以一般采用十进制与其它进制互转或者作为中间步骤来处理。

10进制转换为其他进制

采用上述方法后,我们已经可以做到所有进制转换,包括10进制转3进制,比如十进制28转换为3进制28=2*3+22,这个采用3进制(3的三进制表示10)来进行计算,但是会很麻烦。所以10进制转换其他进制,我们常采用短除法,如下:

当前数不断除以3并把余数作为新的最高位,28除以3余1,1为“个位”,9除以3余0,0为“十位”,3除以3余0,0为“百位”,最终的1是“千位”。如果我们有注意到前面的3进制转10进制算法,我们可以发现短除法其实是3进制转10进制的逆操作,比如3进制转换为十进制时候是:1*3^3+0*3^2+0*3^1+1*3^0  ,我们转换一下是((1*3+0)*3+0)*3+1,如此和10进制转换3进制的时候逆向操作。

小数

如果前面的理解了,小数就可以很容易理解了,我们还是先从10进制来看。比如十进制12.34,我们看小数后面十分位部分.3,表示把1分为10份只取3份,.04百分位部分是把1分为100份,取4份。那么我们换成公式:

12.34=1*10^1+2+3*(1/10)+4*(1/100)
     =1*10^1+2+3*10^-1+4*10^-2

我们看到小数部分还是以进制为底数,不过指数部分采用了负数,点的左边的位的指数是位的正幂,点数的右边是位的指数负幂。理解了这个,其他进制的小数部分也就了解, 它们是相同的,比如二进制1001.101:

有了这个理解,我们后续的浮点数就比较好理解了,IEEE浮点表示浮点数,也是基于这种方式,只是定义了些规范,后续我们会详细了解。

 

移位操作

常见的移位操作有三种:左移,逻辑右移,算术右移。

移动操作

操作
参数x [01100011] [10010101]
x<<4 [00110000] [01010000]
x>>4(逻辑右移) [00000110] [00001001]
x>>4(算术右移) [00000110] [11111001]

左移

x向左移动k位,会丢弃最高的k位,并在右端补k个0,也就是常说的当前值乘以2的k次方。为何是乘以2的k次方?我们看10进制的时候,某数乘以10,就是在末尾增加1个0 ,由此我们可以联想到,二进制左移一位(末尾加一个0)相当于乘以2,这个结论普遍存在于所有进位制中:k进制数的末尾加个0,相当于该数乘以k。

我们从图中可以看到,左移动一位,就相当于进位制展开式的每个指数都加1,如此移动一位,就相当于当前数(1*2^5+1*2^1+!*2^0)*2^1=1*2^6+1*2^2+1*2^1

右移

理解了左移的原理,右移动的原理也是相同的,右移k位=进位制展开式的每个指数都减k,也就是当前数除以进制的k次方。唯一不同的是分为逻辑右移和算术右移。

逻辑右移就是无符号移位,右移几位,就在左端补几个0,比如上边 Varint中每次右移7位,相应的当前数高位就会补充7个0。

算术右移动是有符号移位,和逻辑右移不同的是,算术右移是在左端补k个最高有效位的值,如此看着有些奇特,但对有符号整数数据的运算非常有用。我们知道有符号的数,首位字节,是用来表示数字的正负。负数采用补码形式来存储,比如[11100110],10进制是-26,算术右移1位之后[11110011],10进制是-13,如若不是补最高有效位的值1而是补做事0的话,右移之后就变成正数了。

 

字节序

单个字节并没有字节序的问题,当一个数据需要多个字节存储的时候,就会牵扯到这样的问题,这个数据的地址是什么,存储器中如何排列这些字节,是高位地址存最高有效位,还是低位地址存最高有效位。

比如一个int类型的变量,它的地址是使用字节中最小的地址,比如在存储器上的位置是0x101、0x102、0x103,它的地址是0x101,若是这个数据是一个w位的整数,位表示为[x(w-1),x(w-2)....,x1,x0],那么其中x(w-1)是最高有效位,x0是最低有效位,w若是8的倍数,位被分组成字节,那么最高有效字节是[x(w-1)...x(w-8)],最低有效字节是[x7,x6...x0]。这个也可以成为物理顺序,和我们普通人理解的存储顺序预期相符合,比如十进制也是高位(百位,10位)在地位(个位)前面。

 

小端法(little endian)

如果字节的逻辑顺序与物理顺序相反,也就是w的最低有效字节在前面[x7,x6....x0],最高有效字节[x(w-1)...x(w-8)]在后面,此时成为小端法(little endian)。多数intel兼容机都采用这种规则。

大端法(big endian)

如果字节的逻辑顺序与物理顺序相同,也就是w的最低有效字节[x(w-1)...x(w-8)]在前面,最高有效字节[x7,x6....x0]在后面,称为大端法(big endian),大多数IBM和SunMicrosystems的机器都是采用这种规则。

 

比如一个十六进制数:0x01234567,我们用大端小端法看他们在存储器上的位置。

我们可以看到大端法是比较符合我们习惯的,高位在前地位在后。

上述Varint的算法,是采用小端法来存储字节顺序的。

 buffer[position++] = (byte) ((value & 0x7F) | 0x80);

每次都是获取当前数据的后7个字节存储到数据流buffer里面,也就是低位字节放在buffer字节数组的前面。

----------------------------------------------end------------------------------------------------

扫描关注更多,关注个人成长和技术学习,期待用自己的一点点改变,带给你一些启发及感悟。

 

 

© 著作权归作者所有

共有 人打赏支持
wier
粉丝 718
博文 49
码字总数 131483
作品 0
东城
技术主管
加载中

评论(22)

Skqing
Skqing
写的很好,但是我看不到啊,鄙人愚昧!
Mr憨慢
Mr憨慢

引用来自“Mr憨慢”的评论

比如十进制12.34,我们看小数后面十分位部分.3,表示把10分为10份只取3份,.04百分位部分是把10分为100份,取4份???应该是把一分成十份吧。。。:flushed:

引用来自“喷子”的评论

十进制,当然是分10
嗯嗯 那也是把1分成10分哈 楼主已经改过来了哈:smile:
广
广漠飘羽
非常感谢
myw31415926
myw31415926

引用来自“myw31415926”的评论

写得挺好的,谢谢!请教一下,你的这些图是用什么软件画的?

引用来自“wier”的评论

gliffy
我看了,感谢你推荐的这个工具,谢谢!
wier
wier

引用来自“张伟斌卍”的评论

写的好,就是有错别字,sun microsystem中居然出现了汉字
:astonished:
wier
wier

引用来自“zenerna”的评论

1001.101这个转化的图是不是错了?
已经切图了,没办法了,谢谢指正
wier
wier

引用来自“myw31415926”的评论

写得挺好的,谢谢!请教一下,你的这些图是用什么软件画的?
gliffy
ox48
ox48
好东西
张伟斌卍
张伟斌卍
写的好,就是有错别字,sun microsystem中居然出现了汉字
itfanr
itfanr
好棒
JDK 9对于开发人员而言并不像JDK 8那么有趣

  【IT168 资讯】Java编程语言自出现以来似乎一直是个慢性子,这次终于决定做出点改变了。Java之后的更新速度终于可以和现代编程语言相提并论了。近日,Azul Systems营销副总裁Howard Gree...

it168网站
2017/09/15
0
0
通过 LLVM 在 Android 上运行 Swift 代码

Swift 已经发布一年多了,苹果承诺将在 2015 年底开源 Swift。这是非常棒的一件事情,但是我们现在可以在 Android 设备上运行 Swift 吗? Swift 编译器 这都是由 Chris Lattner 设计的,很容...

oschina
2015/10/15
4.3K
15
Linux下内网反弹技巧总结与杂谈

导读 靠谱点的公司都不会将应用服务器直接对外,而是通过代理转发或映射等方式对外,当可以执行命令的服务器能够访问公网(这个要看具体情况,比如需要加载公网资源或者其他需求)时,反连技...

问题终结者
07/08
0
0
面向对象语言--Boo

Boo 是个面向对象语言,语法非常接近 Python,并且提供了许多可以扩充编译器的有趣特色,并且可以运行在 .NET Framework 或 Mono 上。 缘起 在微软推出.NET Framework之后,作者Rodrigo Bar...

匿名
2012/06/28
1K
0
Debian Linux 19 岁生日

Debian GNU/Linux 可谓世上最为古老的 Linux 发行版之一。迄今为止,Debian 已经 19 岁了。Debian 项目原由 Ian Murdock 创建于 1993 年 8 月 16 日。其名称由当时还是 Ian Murdock 女友的 ...

oschina
2012/08/17
2K
5
Github Atom 1.12.0 和 1.13.0-beta0 发布

Github Atom 1.12.0 和 1.13.0-beta0 发布了。 Atom 是 Github 专门为程序员推出的一个跨平台文本编辑器。具有简洁和直观的图形用户界面,并有很多有趣的特点:支持CSS,HTML,JavaScript等网...

局长
2016/11/10
1K
7
Rob Pike:走进Go语言

序言:关于Go Go语言是一个开源、并发、高效、简单、有趣(但对某些人来说可能很无聊)的编程语言,支持垃圾回收(GC),具有很好的可伸缩性。Go是从2007年末由Robert Griesemer, Rob Pike,...

平凡之路
2014/10/15
0
0
CNN高效感受野的惊奇发现

摘要:在这篇文章中,“高效感受野”(ERF)的理念和在卷积神经网络(CNN)上自然产生的视觉有着惊人的关系。 感受野(receptive field)是怎样一个东西呢,从CNN可视化的角度来讲,就是输出...

阿里云云栖社区
2017/11/28
0
0
怪异的JavaScript系列(三)

译者按: JavaScript有很多坑,经常一不小心就要写bug。 原文: What the f*ck JavaScript? 译者: Fundebug 为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学...

Fundebug
04/26
0
0
JAVA按位逻辑运算基本教程(3)

四、右移运算符 右移运算符>>使指定值的所有位都右移规定的次数。它的通用格式如下所示: value >> num 这里,num 指定要移位值value 移动的位数。也就是,右移运算符>>使指定值的所有位都右...

Pracy
2010/03/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JAVA 三种WebService 规范

JAVA 中共有三种WebService 规范,分别是JAX-WS(JAX-RPC)、JAXM&SAAJ、JAX-RS。 1. Jaxws(掌握) JAX-WS 的全称为 Java API for XML-Based Webservices ,早期的基于SOAP 的JAVA 的Web 服务...

onedotdot
10分钟前
0
0
将博客搬至CSDN

将博客搬至CSDN

xpbob
11分钟前
0
0
TensorFlow 拟合异或 one-hot方式

增加隐含层数目 之前是按照计算出的数值按照0.5分为0和1,现在是算出向量,用维度较大的作为结果 import tensorflow as tfimport numpy as np# 网络结构:2维输入 --> 2维隐藏层 --> ...

阿豪boy
14分钟前
0
0
Aidl进程间通信详细介绍

目录介绍 1.问题答疑 2.Aidl相关属性介绍 2.1 AIDL所支持的数据类型 2.2 服务端和客户端 2.3 AIDL的基本概念 3.实际开发中案例操作 3.1 aidl通信业务需求 3.2 操作步骤伪代码 3.3 服务端操作...

潇湘剑雨
29分钟前
0
0
python爬虫日志(3)下载图片

import urlliburl='https://xxx.jpg'#图片地址res=urllib.request.urlopen(url)#此函数用于对url的访问data=res.read() #字节流with open(r'D:\1.jpg',"wb") as code: c...

茫羽行
46分钟前
0
0
vue中$emit的用法

1、父组件可以使用 props 把数据传给子组件。 2、子组件可以使用 $emit 触发父组件的自定义事件。 vm.$emit( event, arg ) //触发当前实例上的事件 vm.$on( event, fn );//监听event事件后运...

JamesView
55分钟前
0
0
bash审计系统搭建

step1:使用saltstack工具bash部署>>>>>> # salt -N clienta state.sls audit step2:安装elasticsearch>>>>>> 注意: 1.不能以root用户进行启动,需要创建用户,并对解压的elasticsearch目录赋......

硅谷课堂
56分钟前
0
0
Linux sar性能分析

Linux使用sar进行性能分析 sar简介 sar命令常用格式 sar常用性能数据分析 整体CPU使用统计-u 各个CPU使用统计-P 内存使用情况统计-r 整体IO情况-b 各个IO设备情况-d 网络统计-n sar日志保存-...

易野
57分钟前
0
0
用 Python 实现打飞机,让子弹飞吧!

所用技术和软件 python 2.7 pygame 1.9.3 pyCharm 准备工作 安装好 pygame 在第一次使用 pygame 的时候,pyCharm 会自动 install pygame。 下载好使用的素材。 技术实现 初始化 pygame 首先要...

猫咪编程
今天
0
0
MySQL的行锁和表锁

简单总结一下行锁和表锁。 行锁 每次操作锁住一行数据。开销大,加锁慢;会出现死锁;锁定粒度最小,发生锁冲突的概率最低,并发度也最高。 表锁 每次操作锁住整张表。开销小,加锁快;不会出...

to_ln
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部