二进制小总结

真值与机器值

  真值很好理解,就是十进制的数字前面再加上正负号,这是人类可以简单识别的数字,比如 0、±16、±1084、±10.34、±100.453 等,而正数前面的+符号可以省略。机器值从字面理解就是机器(计算机)识别的值,实际上也确实是这个意思。

  计算机中通过高低电平表示1或者0,这样就可以表示一个二进制的数值。一个1或者0表示的数值位称为一个bit,而计算机中存储和传输数据的最小单位是一个字节(byte)也就是8个bit,所以说计算机所有计算本质上都是基于二进制。

  在计算机中,我们可以使用1个或者多个字节存储一个数,但无论是多少个字节,其大小肯定是固定的,同时其所能表示的数值的范围也是固定的。比如说对使用1个字节存储的数进行计算或者传输,那么这个数所能表示的最小值为00000000最大值为11111111,转换为十进制为0 ~ 255。那么无论对这个数做了什么计算,无论计算之后的结果为多少都不能超出这个范围,同理使用2个字节存储的数范围为0 ~ 65535。

  由于很多时候一个数据需要使用2个或者2个以上的字节表示,那么这种数据无论是存储还是传输的时候都会有一个顺序的问题,也就是大小端对齐(字节序)问题。在存储时高位字节在前为大端对齐,反之为小端对齐。在数据传输时先传输高位字节为大端字节序,反之为小端字节序。目前绝大多数平台内部都是小端对齐的方式存储数据,而大多数通信协议却都是用大端字节序传输数据,所以这一点值得注意一下。

符号位与数值位

  计算机中使用二进制存储传输和计算数值,但是不能只有数值,计算的时候还得有正负之分。在计算机中使用最高bit位的数值来表示正负号,这个bit位称作符号位。

  计算机中符号位的值为0表示这个数为正数,符号位值为1表示这个树为负数。由于符号位表示符号所以其不表示具体的值,除开符号位剩余的bit位用来表示数值也就是数值位。比如1个字节的整数00000001,其中最高bit(最左边)位的0为符号位,表示这个数为正数,数值位为1,所以其真值为1。同理2个字节的整数00000000_0000001,其真值也是1。

原码、反码和补码

  计算机只识别机器码,其实也就是二进制数,并且使用最高bit位表示符号位。那么两个真值为8和-8的8位整数,它们在计算机内部的机器值是否就分别是00001000和10001000?其实并不是,这只是8和-8的原码,而机器算计中的机器值是使用补码存储和计算的。

  计算机中,正数的原码、反码和补码是一样的,所以上面那个例子中,真值为8的8位整数的机器值确实是00001000,但是-8就不是这么回事了。负数的首先将原码数值位按位取反得到反码,然后再将反码数值位加1之后则得到补码。我们来看一下-8这个例子,其原码为10001000,数值位按位取反之后的反码为11110111,然后数值位加1之后的补码为11111000。所以真值为-8的8位整数在计算机中的机器值为11111000,我们来看下面这张表

原码 反码 补码
int8 00000001 00000001 00000001
int8 10000001 11111110 11111111
int16 00000000_00000001 00000000_00000001 00000000_00000001
int16 10000000_00000001 11111111_11111110 11111111_11111111
... ... ... ...

注:int8为8bit位整数占用1byte,int16为16bit位整数占用2byte。

  刚说的是原码转补码的步骤,其实补码转原码的步骤是一样的。首先正数的原码补码是一样的不需要转换,我们看负数11111000,首先将数值位按位取反得到10000111,然后再将数值位加1得到10001000。我们再来看一个8位的整数10000000,是不是发现这个数原码和补码是一样的,那么这个看起来像是“-0”的数是怎么回事呢?其实可以将这个数看成是一个特殊值,它的真实含义就是最小值。8位的这种“-0”的真值为-128,16位的这种“-0”真值为-32768。所以只需要记住100...000这种补码就是最小值就行,我们看下面的这张表

二进制补码 十进制
int8 10000000 -128
int16 10000000_00000000 -32768
int32 10000000_00000000_00000000_00000000 -2147483648
int64 10000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000 -9223372036854775808

  有两对8bit位的整数4、8和4、-8,我们分别看一下他们在计算机中是怎么做加法计算的。首先看4和8的补码分别为00000100和00001000,只需要将每个bit位相加就行,结果为00001100,其真值为12。我们再来4和-8的计算,它们补码分别为00000100和11111000,然后将它们按位相加(注意符号位也要做加法)得到11111100,其原码为10000100,真值为-4。

  再来看一下减法计算,比如8bit位的整数-8减去4,首先可以将4处理一下可以变为(-8) + (-4),这样是不是就又变为了加法了?-8和-4的补码分别为11111000和11111100,将它们按位相加得到补码11110100(注意这是8位的整数,超出部分发生了溢出),转换成原码为10001100,真值为-12。

  再来看一下乘法,比如8bit位的整数-8乘以13,他们的补码分别为11111000和00001101。其中-8为被乘数,13为乘数,并且乘数有8个bit位,需要将被乘数按位与和位计算8次然后将结果相加,看如下分析:

  • 1、被乘数的第0个bit位值为1,将被乘数乘以1然后左移0位得到:11111000;
  • 2、被乘数的第1个bit位值为0,将被乘数乘以0然后左移1位得到:00000000;
  • 3、被乘数的第2个bit位值为1,将被乘数乘以1然后左移2位得到;11100000;
  • 4、被乘数的第3个bit位值为1,将被乘数乘以1然后左移3位得到;11000000;
  • 5、被乘数的第4个bit位值为0,将被乘数乘以0然后左移4位得到;00000000;
  • 6、被乘数的第5个bit位值为0,将被乘数乘以0然后左移5位得到;00000000;
  • 7、被乘数的第6个bit位值为0,将被乘数乘以0然后左移6位得到;00000000;
  • 8、被乘数的第7个bit位值为0,将被乘数乘以0然后左移7位得到;00000000;

由此可以得计算得到8组补码(注意上面做位移涉及到的整数溢出,只能是8个bit位),然后将它们做加法得到10011000(也存在整数溢出)转换为原码为11101000,真值为-104。

  至于除法则是使用交替加减法的方式,本文只是对计算原理做一下扩展,这里不再继续深入做介绍,如果有想了解的可以自行上网查询。

  通过上面的分析可以知道,使用补码可以将所有计算都转化为加法计算,这样可以让计算机底层对于整数(浮点数再此不做讲解,有时间会再单独写一篇文章作介绍)计算变得简单,反码属于历史遗留,因为其存在±0的问题。

Java中的基本数据类型

  在计算机编程语言中都会有数据类型的概念,数据类型是用来修饰变量的。不同数据类型所修饰的变量,其指代的数据在内存中占用空间的大小(基本类型变量使用的空间、指针或引用变量指向的地址空间等,后面简单称数据类型占用的内存空间)是固定的。即使在一些弱类型语言中,虽然变量可以不用显示地声明数据类型,但当第一次为变量赋值时,还是会隐式地为其附上数据类型属性。

  对于java来说,由于其具有跨平台的特性,所以基本数据类型所占用的内存空间大小(字节数)是固定的。我们来看一下java中的几个基本数据类型:

byte char short int float long double boolean
字节数 8bit / 1byte 16bit / 2byte 16bit / 2byte 32bit / 4byte 32bit / 4byte 64bit / 8byte 64bit / 8byte /
取值范围 -27 ~ 27 - 1 0 ~ 216 - 1 -215 ~ 215 - 1 -231 ~ 231 - 1 - -263 ~ 263 - 1 - false | true
默认值 0 0 0 0 0.0 0 0.0 false
后缀 / / / / f | F l | L d | D /

注:jvm规范并没有指明boolean类型占用几个字节的空间,所以根据jvm产品的不同,实现的方式也可能不同。最广泛的说法是,jvm内部使用int代替boolean类型,也就是占用4个字节。另外这里没有列出浮点数的大小范围,由于本文只介绍整数,后面如果有时间则会单独出一篇介绍浮点数的博文。

  我们来看下面几个例子

// 案例1,下面的10进制真值的写法,但是当编译器编译完成之后,在内存中还是会以补码的形式存在
int value1 = 10;
int value2 = -10;
System.out.printf("value1=%d, value2=%d\n", value1, value2); // 结果为: value1=10, value2=-10

// 案例2,下面是2进制补码的写法,在数字前面加上'0b'或者'0B','_'只是一个分隔符
int value3 = 0b00000000_00000000_00000000_00001010; // 2进制int类型10的补码
int value4 = 0B11111111_11111111_11111111_11110110; // 2进制int类型-10的补码
System.out.printf("value3=%d, value4=%d\n", value3, value4); // 结果为: value3=10, value4=-10

// 案例3,下面是16进制补码的写法,在数字前面加上'0x'或者'0X',大于9的数值使用a~f或A-F表示
int value5 = 0x0000000a; // 16进制int类型10的补码
int value6 = 0Xfffffff6; // 16进制int类型-10的补码
System.out.printf("value5=%d, value6=%d\n", value5, value6); // 结果为: value5=10, value6=-10

// 案例4,下面是8进制补码的写法,在数字前面加上'0'
int value7 = 012; // 8进制int类型10的补码
int value8 = 037777777766; // 8进制int类型-10的补码
System.out.printf("value7=%d, value8=%d\n", value7, value8); // 结果为: value7=10, value8=-10

/*
 * 注: 这里不论是10进制还是16进制等方式写的整数,在计算机内部都是以二进制补码的形式体现,
 *     也就是上面案例2的中2进制的形式体现。
 */

  额外说明一下,这些基本数据类型只会出现在线程栈中,或者再详细一点,只会出现在线程栈的运行时栈帧(方法的工作空间)的局部变量表和操作数栈中。也就是说,只有在局部方法中才可以声明基本数据类型的局部变量。对象的成员变量或者类的静态变量即使是基本数据类型,最终也会被自动装箱为包装类型,然后在堆中开辟空间。 但也有例外,在现在的高性能jvm中一般都会有jit(即时编译)系统,在逃逸分析时如果对象被判断为未逃逸(对象不是入参、不是返回值并且也没有被方法外部变量引用),则会做标量替换(拆分对象为基本数据类型)然后在线程栈或者CPU寄存器中分配空间,方法执行完成之后随着运行时栈帧出栈而被回收,可减少GC的工作负载。

Java中的整数类型转换

  整数的基本类型之间可以互相转换,甚至char类型都可以转换为byte、short、int、long等类型,反之亦然。但是不同的数据类型,其所占用的内存空间大小是不一样的,那么这里就涉及到补全和溢出的问题了。

  整数类型按所占内存空间从小到大排序分别为byte、short、int、long,由占用空间小的转型为占用空间大的为向上转型,反之为向下转型。java中类型转换运算符为括号,括号中为转换的目标类型,例如long value = (long) Integer.MAX_VALUE;。向上类型转换可以隐式地完成,也就是说不需要显示地编写出类型转换运算符例如long value = Integer.MAX_VALUE;。但是向下类型转换时,可能会发生整数溢出(舍弃高字节位),所以必须显式的写出类型转换运算符,例如short value = (short) Integer.MAX_VALUE;

  如果是向上转型时,使用符号位的值填充高字节位。向下转型时,直接舍掉高字节位。我们看下面两张表,从上往下看为向下转型,从下往上看则为向上转型:

类型 二进制正数补码 十进制正数
long 00000000_00000000_00000000_00000000_00000000_00000000_00000000_01111111 127
int 00000000_00000000_00000000_01111111 127
short 00000000_01111111 127
byte 01111111 127

  

类型 二进制负数补码 十进制负数
long 11111111_11111111_11111111_11111111_11111111_11111111_11111111_10000000 -128
int 11111111_11111111_11111111_10000000 -128
short 11111111_10000000 -128
byte 10000000 -128

  可以看到,不论转换成什么类型,最终的值还是不变的。我们看下面的案例:

// 案例1
byte value = (byte) Short.MAX_VALUE; // Short.MAX_VALUE为short类型的最大值: 32767
// 案例2
short value = Byte.MIN_VALUE; // Byte.MIN_VALUE为byte类型的最小值: -128

  案例1为一个向下类型转换,由于32767这个值超过了byte能表示的最大值,所以其必然会发生整数溢出。short类型的32767的二进制补码为01111111_11111111,向下转型为byte舍掉高位字节的二进制补码为11111111,其值变为了-1。

  案例2为一个向上类型转换,byte类型的-128的二进制补码为10000000,将其转换为short类型之后的二进制补码为11111111_10000000。我们知道虽然其表示的值没有变还是-128,但是如果我们在向上类型转换之后,还想让原来的符号位表示数值,也就是得到byte类型-128这个值的无符号数,则可以做按位与计算int value = Byte.MIN_VALUE & 0xff;

Java中的字面量

  Java中可以可以定义两种类型的整数字面量,分别为int和long。例如int value = 10;或者long value = 10L;,可以看到其中long类型的字面量需要加上'L'类型的后缀,当然也可以是'l'。

  Java中无法直接定义byte和short类型的字面量,但是如果这么写byte value = 127;编译也没错,那么这里的127是不是就是byte类型的字面量呢?其实不是,这个127还是int类型的,只不过做了向下类型转换而已。但是前面说向下类型转换必须显式的写出类型转换运算符,这里没有那么是不是前面说错了呢?其实也不是,int类型127的二进制补码为00000000_00000000_00000000_01111111,向下转型为byte类型之后的二进制补码为01111111,那些被舍弃的0可以看做是填充位所以并没有发生整数溢出。由于字面量是静态不可变的值,编译器在编译的时候就知道其并不会发生整数溢出,所以就直接做了隐式类型转换。但是我们来看字面量为128的int类型整数,其二进制补码为00000000_00000000_00000000_10000000,转换为byte类型之后的补码为10000000,原本属于数值位的1变为了符号位,这里发生了整数溢出,所以需要显式的加上类型转换运算符byte value = (byte) 128;

  我们来看下面这些关于字面量的隐式类型转换的案例

// 案例1
byte value1 = 127;

// 案例2,-128在byte能够表示的数值范围内,编译器直接做了隐式类型转换。
byte value2 = -128; // 赋值给value1的二进制补码为: 10000000

// 案例3,Short.MAX_VALUE是一个常量,编译器编译的时候可以明确的知道其值为32767,所以编译器会先计算出32767 - 32640的值然后赋值给value3变量
byte value3 = Short.MAX_VALUE - 32640; // 赋值给value3的二进制补码为: 01111111

// 案例4,下面由于变量value4被final修饰,其值在编译期间是不可变的,编译器也能明确知道其值不会发生整数溢出
final byte int value4 = 127;
byte value5 = value4;

// 案例5
static final int value6 = 32767;
void func() {
	short value7 = value6;
}

  我们看这一行代码long value = 2147483647,这是一个向上转型的例子,将int类型的字面量2147483647转换为long类型。但是如果字面量为2147483648就必须这么写long value = 2147483648L;,因为2147483648这个值已经超过了int类型的最大值,必须使用long类型的字面量表示。

内存对齐和有效位移

  不管是四则运算还是位运算,参与计算的整数有可能是不同的数据类型,也就意味着它们在内存中的占用的字节数不同,所以在计算的时候需要将转换为相同的类型,也就是内存对齐。

  如果是byte、short、int等类型的数据做计算,默认会将byte和short了类型的数据先转换为int类型的数据然后在做计算。如果参与计算的数据中有long类型的数据,则会将非long类型的数据先转换为long类型,然后在做计算。

  位移计算的时候数据类型要么是int类型要么是long类型,也就是说计算的说要么有32的bit位要么有64个bit为,那么我们做位移的时候是不是可以位移无限的bit位呢?当然不是,有效位移的位数为0到bit为数量(字宽)减去1,也就是说int的有效位移大小为0 ~ 31,long的有效位移数量为0 ~ 63。如果超出这个范围的话则会与31或者63做按位与计算,比如int数据位移36位则实际位移为36 & 31 = 4

Varints 128位可变长整型

  通过前面的说明,大家应该对计算机中的整数有了清晰的理解。比如有一个int类型的整数,我们需要在网络传输传输它,那么发送方只需要传输4个字节的数据就行,接收方也只需要接收4个字节。比如我们传输一个值为10的int类型数据,大家可以知道其实只需要传输一个字节就行,但是谁也不能保证下一个传输的数据使用一个字节会不会溢出,所以这时候我们就需要设计一个可以变换字节数量的编解码方式,并且数据接收方也能够知道自己需要接受几个字节,Varints就是为了解决这个问题的。

  Varints是按小端字节序排列,也就是低位字节在前高位字节在后。每个字节的第7个bit位不表示数值,只是用来标识是否为最后一个字节,如果第7个bit位值为1则代表不是最后一个字节,如果值为0则代表为最后一个字节,如下表:

真值 补码 varints
100 01100100 [01100100]
1000 00000011_11101000 [11101000, 00000111]
100000 00000000_00000001_10000110_10100000 [10100000, 10001101, 00000010]
... ... ...

  我们看上表中,红色部分为标识是否最后一个字节的bit位,那么这样是不是就可以表示一个无穷大的整数了,不过一般也没必要太大,就拿java来说,最大也就long类型的8个字节64个bit位大小。其实正真生产过程中应用所处理处理数据时,遇到小数值的概率要比遇到大数值的概率要大得多,所以varints可以在做网络传输或者数据存储时可以省不少流量和空间,而且可以便于扩展。不说别的,直接上代码了:

public final class ByteUtil {

    private ByteUtil() {}
    
    public static byte[] enVarInt(int value) {
        int size = 0;
        byte[] temps = new byte[5];
        for (; (value & 0xffffff80) != 0; value >>>= 7, ++size) {
            temps[size] = (byte) (value & 0x7f | 0x80);
        }
        temps[size] = (byte) value;
        byte[] result = new byte[size + 1];
        System.arraycopy(temps, 0, result, 0, result.length);
        return result;
    }
    
    public static byte[] enVarInt(long value) {
        int size = 0;
        byte[] temps = new byte[10];
        for (; (value & 0xffffffffffffff80L) != 0; value >>>= 7, ++size) {
            temps[size] = (byte) (value & 0x7fL | 0x80L);
        }
        temps[size] = (byte) value;
        byte[] result = new byte[size + 1];
        System.arraycopy(temps, 0, result, 0, result.length);
        return result;
    }
    
    public static IntPair deVarInt(int offset, byte... buffer) {
        isLegalArg(offset >= 0 && offset < buffer.length, String.format("offset=%d, bufferLen=%d, Must meet: offset >= 0 && offset < %d", offset, buffer.length, buffer.length));
        int bitSize = 0, result = 0, length = 0;
        for (; offset < buffer.length && bitSize < Integer.SIZE; ++offset) {
            int value = buffer[offset] & 0xff;
            result |= (value & 0x7f) << bitSize;
            bitSize += 7;
            ++length;
            if (0 == (value & 0x80)) {
                break;
            }
        }
        return IntPair.of(length, result);
    }
    
    public static IntLPair deVarLong(int offset, byte... buffer) {
        isLegalArg(offset >= 0 && offset < buffer.length, String.format("offset=%d, bufferLen=%d, Must meet: offset >= 0 && offset < %d", offset, buffer.length, buffer.length));
        int bitSize = 0, length = 0;
        long result = 0;
        for (; offset < buffer.length && bitSize < Long.SIZE; ++offset) {
            int value = buffer[offset] & 0xff;
            result |= (value & 0x7fL) << bitSize;
            bitSize += 7;
            ++length;
            if (0 == (value & 0x80)) {
                break;
            }
        }
        return IntLPair.of(length, result);
    }

    private static void isLegalArg(boolean isLegalArg, String message) {
        if (!isLegalArg) {
            throw new IllegalArgumentException(message);
        }
    }

}

ZigZag

  前面我们讲解了varints可以省流量和空间,因为一般遇到小数值的概率要比遇到大数值的概率要大得多,同时我们也说了计算机内部是只是别补码的,如果处理一个数值很小但是却是负数的时候,单凭varints可就不能达到省流量和省空间的效果了。前面我们也讲到符号位为整数的最高bit位,那么即使一个负数的数值再小,整个整数看起来也不小,所以这时候就需要使用到ZigZag来吧符号位处理一下。

  ZigZag编码时,正数不做任何处理。对于负数则将整体数值位按位取反再左移一位,然后将符号位放到第0个bit位上,这样处理之后就会得到一个与原来不一样的整数,然后再按varints进行编码。直接上ZigZag的代码了:

public final class ByteUtil {

    private ByteUtil() {}

    public static int enZigZag(int value) {
        return (value << 1) ^ (value >> 31);
    }
    
    public static long enZigZag(long value) {
        return (value << 1) ^ (value >> 63);
    }
    
    public static int deZigZag(int value) {
        return (value >>> 1) ^ -(value & 1);
    }
    
    public static long deZigZag(long value) {
        return (value >>> 1) ^ -(value & 1);
    }

}

附加代码

import java.util.Objects;

public class IntLPair {
    
    private int left;
    
    private long right;
    
    public IntLPair() {
    }
    
    private IntLPair(int left, long right) {
        this.left = left;
        this.right = right;
    }
    
    public static IntLPair of(int left, long right) {
        return new IntLPair(left, right);
    }
    
    public int getInt() {
        return left;
    }
    
    public void setInt(int left) {
        this.left = left;
    }
    
    public long getLong() {
        return right;
    }
    
    public void setLong(long right) {
        this.right = right;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        IntLPair intLPair = (IntLPair) o;
        return left == intLPair.left &&
                right == intLPair.right;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(left, right);
    }
    
    @Override
    public String toString() {
        return "IntLPair{" +
                "left=" + left +
                ", right=" + right +
                '}';
    }
    
}
import java.util.Objects;

public class IntLPair {
    
    private int left;
    
    private long right;
    
    public IntLPair() {
    }
    
    private IntLPair(int left, long right) {
        this.left = left;
        this.right = right;
    }
    
    public static IntLPair of(int left, long right) {
        return new IntLPair(left, right);
    }
    
    public int getInt() {
        return left;
    }
    
    public void setInt(int left) {
        this.left = left;
    }
    
    public long getLong() {
        return right;
    }
    
    public void setLong(long right) {
        this.right = right;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        IntLPair intLPair = (IntLPair) o;
        return left == intLPair.left &&
                right == intLPair.right;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(left, right);
    }
    
    @Override
    public String toString() {
        return "IntLPair{" +
                "left=" + left +
                ", right=" + right +
                '}';
    }
    
}
发表评论

评论已关闭。

相关文章