位运算

Posted on | In

这又是一篇存货文233..还有好多存货文，慢慢发吧。

简单来学学位运算相关的。补补基础趴。

感谢JOHNSON师傅的文章让我学到了这么有趣的知识。

ps：就一个右移时符号位的问题就巴拉了这么多我也是醉了

引言

总所周知，计算机中进行数据表示的方式是二进制，最小的存储单元就是位(bit)。一个位只有两种状态：0或1。

1个字节(byte)为8个位

下面以Java为例，简单看看“位”在编程中是如何工作的。

1
2
3
4
5
6
7
8
9
public static void main(String[] args) throws Exception{
    byte a = 10;
    byte b = -10;
    File file = new File("D:\\tmp.bin");
    FileOutputStream fileOutputStream = new FileOutputStream(file);
    fileOutputStream.write(a);
    fileOutputStream.write(b);
    fileOutputStream.close();
}

运行后用hexdump查看/tmp.bin。

1
2
PS C:\Users\e> hexdump.exe D:\tmp.bin
000000  0a f6

计算器转成二进制

1
2
00001010  - 0a
11110110  - f6

注意：这里的10不是指int 10（int是4个byte组成的），而是byte的10。

10的二进制是00001010很好理解，那为啥-10的二进制是11110110呢？

这里涉及到原码、反码和补码的概念了

原码、反码和补码

原码，顾名思义，就是字节最原始的二进制表示形式。如十进制10的二进制表示形式就是00001010

反码，顾名思义，就是把原码中的位取反，1变0，0变1。啥意思呢？如十进制10的反码就是

1
2
00001010 - 原码
11110101 - 反码

补码。就是在反码的基础上，再+1。如十进制10的补码就是

1
2
3
00001010 - 原码
11110101 - 反码
11110110 - 补码

关于有符号

那么原码，反码和补码有啥用呢？

查了下资料，发现最重要的是补码，反码只是运算到补码的其中一步。补码最大的作用是减法运算。

总所周知，减去一个数等于加上这个数的相反数。这样减法就变成了加法。

那么要解决减法问题，首先要解决负数的表示问题。

以1 (00000001)为例。思路是，要找到表示1的负数，那么就是找到一个数，让这个数与1相加为0

正常加肯定不可能为0的，大佬们想到了一个思路：让字节溢出。即：正常一个字节8位，如果找到一个数让0000 0001(8位)相加等于1 0000 0000(9位)。我们只保留后8位，这样不就能得到0了嘛。

于是，00000001的负数表示就是 11111111.变换过程就是

1
2
3
00000001 - 原码
11111110 - 反码
11111111 - 补码

正由于最高一位的特殊性(最高一位为1后才能进位到溢出)，且为了平衡一个字节中，负数和正数的数量。于是顺带规定，在有符号字节中，最高一位为0表示正数，最高一位为1表示负数。运算时最高位通常不变。

也正由于补码的特殊性，能够让CPU运算减法。于是计算机存储数据时都是使用的补码形式存储。

于是这样就成了我们耳熟能详的：有符号字节数据位是7位，最高位保留用作表示正负符号。以及：正数的原码等于补码，负数的补码等于反码+1。

还有人说。补码是为了区分+0 (10000000)和-0 (10000001)。我觉得在当时应该没这个必要，这应该只是补码出现的附属产物。

以上是我阅读了补码是谁发明的，它的最初作用是什么的简单理解。可能不大对 :)。就这样把，，

左移，右移

先来看一段代码，应该不陌生了吧：

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) throws Exception{
    byte a = 10;
    byte b = -10;

    File file = new File("D:\\tmp.bin");
    FileOutputStream fileOutputStream = new FileOutputStream(file);
    fileOutputStream.write(a);
    fileOutputStream.write(b);
    fileOutputStream.close();
}

通过hexdump查看

1
2
PS C:\Users\e> hexdump.exe D:\tmp.bin
000000  0a f6

转成二进制

1
2
00001010 - 0a
11110110 - f6

那么左移和右移是什么东西呢？我们用Java来做例子，尝试将a和b左移1位

1
2
3
4
5
public static void main(String[] args) throws Exception{
    byte a = 10 << 1;
    byte b = -10 << 1;
	.....   
}

查看a、b的二进制：

1
2
3
4
5
6
7
#左移前
00001010 - 0a - a
11110110 - f6 - b

#左移后
00010100 - 14 - a
11101100 - ec - b

从这个Demo中可以看出，左移就是把位整体往左移动，低位补0。高位溢出的丢弃。

右移1位

1
2
3
4
5
public static void main(String[] args) throws Exception{
    byte a = 11 >> 1;
    byte b = -11 >> 1;
	.....   
}

查看a、b的二进制

1
2
3
4
5
6
7
#右移前
00001011 - 0b - a
11110101 - f5 - b

#右移后
00000101 - 05 - a
11111010 - fa - b

借用菜鸟教程的说明

无符号数，整体往右移动，高位补0，低位溢出的丢弃

有符号数，各个编译器实现方法不一样。有的是高位补符号位（算数右移），有的是高位补0（逻辑右移）

上面这个Demo可以看出，在Java中，有符号位的右移方式是高位补符号位。

无符号右移

运算符是>>>，高位统统补0。

细节

注意到一个小细节，左移1位时，若被左移的字节小于-64和大于63时，将会报错

这是为什么呢？将64和-65转成二进制看看：

1
2
01000000 - 64 - 原码
10111111 - -65 - 补码

可以发现，在正符号字节64中，高位第2位为1，此时若左移1位，将会把高位第1位覆盖为1。这种做法在有符号字节中，会破坏原本字节的含义。负符号字节-65中也同理。

那怎么办呢？IDEA提供了一个解决方法：将变量类型从byte提升为int (8位->32位)。这种类型转换的工作原理是在byte高位补**符号位**。即：

1
2
3
4
5
6
7
01000000 - 64
00000000 00000000 00000000 01000000 - 扩充成int
00000000 00000000 00000000 10000000 - 左移一位。此时最高位依然是0
    
10111111 - -65
11111111 11111111 11111111 10111111 - 扩充成int
11111111 11111111 11111111 01111110 - 左移一位。此时最高位依然是1

&0xff

关于&0xff的操作，网上都是都说的是为了补码对齐。那么啥是补码对齐？

NoNo，其实，他是有实际需求的。左移和右移操作都存在需求。

右移

右移的应用场景是什么呢？我们来看个Demo

假设场景：一个32位的数据，存在以下数据

  • Version

    • 8bit

  • User Id

    • 8bit

  • Company id

    • 8bit

  • H-u

    • 4bit

  • H-c

    • 4bit

数据结构图示如下：

我们要用最方便的方式读取这个数据，该怎么做呢？

很显然，涉及到位的操作，还是用位运算来的方便。我们可以通过将数据右移24位取低8位得到Version；右移16位取低8位得到User id；右移8位取低8位得到Company id；直接取低8位：右移4位得到H-u，&上0x0f得到H-c。

按照这个想法，很容易的写出实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) throws Exception{
    //原始数据
    //00101010 01001110 10110010 11100110
    int a = 0x2a4eb2e6;
    byte version = (byte)(a>>24); //00101010
    byte userId  = (byte)(a>>16); //01001110
    byte companyId = (byte)(a>>8); //10110010

    byte H = (byte)(a); //11100110
    byte H_u = (byte)(H>>>4); //11111110  //[!]
    byte H_c = (byte)(H&0x0f); //00000110
}

不知大家有无注意到，在(byte)(H>>>4)的操作中出现了问题。预期应该是得到**00001110，可实际却拿到的是11111110**。

这是为什么呢？明明我们都用了无符号的右移了啊？

我们把显示转换(byte)去掉，会很清楚的看到一个编译时异常:

是不是Java在进行右移操作时，会自动将运算的数据类型自动提升为32bit呢？莫急，我们来用C写右移，看看是一个什么样的光景，然后再类比看回Java

在汇编视角下的右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int main() {
	char a;
	char b;

	printf("%p\n", &a);
	printf("%p\n", &b);

	a = 0xb1; // 10110001
	b = a >> 4;
    //需求: 取a的高4位
    //预期: b为 00001011
    //实际: b为 11111011
	return 0;
}

通过VIsual Studio的调试可以发现，为a赋值0xb1时，内存中确确实实是写进了1个字节b1

要进行右移时，会先把a的值写入寄存器EAX。由于EAX是32位的，且读取的变量有符号。程序就会以EAX的高位作符号位，且由于读取的是byte只有8位。而EAX有32位，就会以符号位来进行填充。于是EAX的值就变成了FFFFFFB1

最终真正执行右移操作时，是以EAX为准进行右移的。这样就会导致右移时，往低8位中移动的是1而不是0。

解决方式:

  1. 将char改成unsigned char。无符号在寄存器中高位填充的永远是0

    1
    2
    3
    unsigned char a;
    unsigned char b;
    ......

  2. 在运算时进行&0xff。这样会在寄存器运算时，将EAX的高24位置0。这样右移时往低8位移动的就都是0了

    1
    2
    3
    a = 0xb1;
    b = (a&0xff) >> 4;
    ....

回到Java

以下纯属yy，肯定不严谨，当看个乐呵就好：

看回Java的那个编译异常。联想到EAX寄存器32位的值，是不是大概明白了点？在有符号的运算中，就算运算的数据类型是8位，EAX也会整上32位的长度，实际上是32位在运算。所以Java为了在位运算时保持类型长度和寄存器统一，便要求位运算返回值是int

看回byte H_u = (byte)(H>>>4);的非预期结果。再结合汇编视角写的右移。可以猜测这样的一个运算逻辑:

  • 将H装入EAX。由于它是有符号的且符号位为1（Java没有提供unsigned）。此时EAX的值为1......11100110
  • 对EAX进行无符号右移4位，是整体32位右移，此时EAX的值为00001.......11111110
  • 此时再转换为byte类型，截取低8位赋值给H_U。
  • H_u的值为11111110。不符合我们预期的00001110

明白了原因之后，解决也就变的简单了。就按照前文C的解决方式即可。但是注意Java没有无符号类型，所以我们只能选择用&0xff来清理EAX中高24位的污染。

1
2
3
4
5
.....
byte H = (byte)(a);
byte H_u = (byte)((H&0xff)>>4); //00001110
byte H_c = (byte)(H&0x0f);
.....

左移

右移的应用场景是解析数据，左移的场景更多的偏向数据组装。整合和右移相对应。

数据我们还是用右移的那个数据，只是场景变了，右移的时候我们是解析数据，在左移这一节，我们来组装这个数据。

基本的Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) throws Exception{
        byte version = (byte)0x05; //00000101
        byte userId  = (byte)0xa7; //10100111
        byte companyId = (byte)0xe1; //11100001
        byte H_u = (byte)0x05; //0101
        byte H_c = (byte)0x07; //0111

        int data1;
        int data2;
        data1 = version<<24; //00000101 0.....
        data2 = userId<<16;  //预期: 00000000 10100111 0.....
    					     //实际: 11111111 10100111 0.... [!]
}

可以发现，在赋值给data2时，userId左移16位时，高位是1。不符合预期。

结合前文”汇编视角下的右移”不难猜出，这里依然是EAX的锅。原理如下:

  1. 将userId的值存入EAX，由于EAX是32位的，会按照符号位对高位进行填充。此时EAX的值是1...... 10100111
  2. 对EAX整体左移16位，低位补零。此时EAX的值是11111111 10100111 0.....
  3. 把EAX的值赋给data2。造成了非预期结果

解决方式也很简单，只要我们在EAX执行左移前，使用&0xff把高24位置0即可。

1
2
....
data2 = (userId&0xff)<<16; //00000000 10100111 0.....

解决了左移时的小问题后，我们就可以通过使用左移，把各个byte放到int的对应偏移中，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) throws Exception{
        byte version = (byte)0x05;    //00000101
        byte userId  = (byte)0xa7;    //10100111
        byte companyId = (byte)0xe1;  //11100001
        byte H_u = (byte)0x05; 		  //0101
        byte H_c = (byte)0x07; 		  //0111

        int data1, data2, data3, data4, data5;
        data1 = version<<24;      	  //00000101 0...
        data2 = (userId&0xff)<<16;	  //0...     10100111 0...
        data3 = (userId&0xff)<<8;	  //0... 	          11100001 0...
        data4 = (userId&0xff)<<4;	  //0...                       01010000
        data5 = (userId&0xff);		  //0...                           0111
}

偏移位置正确后，我们可以通过”或”运算符把数据拼在一个int中

1
2
......
int dataRes = data1 | data2 | data3 | data4 | data5; //00000101 10100111 11100001 01010111

再简化点，不弄5个int变量，直接把byte塞进dataRes

1
2
3
......
int dataRes = version<<24 | (userId&0xff)<<16 | (companyId&0xff)<<8 | (H_u&0xff)<<4 | (H_c&0xff);
//00000101 10100111 11100001 01010111

Reference

JOHNSON~ JOHNSON！HTTP 2 协议学习与实战

补码是谁发明的，它的最初作用是什么