移位运算

2022-10-15

位运算是直接操作内存中的二进制数据。因此运算效率比常规的四则运算高出不少。

1.左移运算 #

左移运算用<<表示，按照高位舍弃，低位补0的方式将所有数据位向左移动。

直观来讲，向左移1位等同于将数值乘以2。大多数情形下也确实如此。如：

1val a = 3
2println("a << 1 = ${a shl 1}") // 6
3val b = -1
4println("b << 1 = ${b shl 1}") // -2
5val c = -0xff
6println("c << 1 = ${c shl 1}") // -510
7val d = 0xff
8println("d << 1 = ${d shl 1}") // 510

Kotlin 中使用特定的移位操作符。

但是，这是数据没有溢出的情形。如果一个数足够大，移位时可能会发生数据溢出：

1val a = 0x5FFFFFFF // 1610612736 
2println("a << 1 = ${a shl 1}") // -1073741826
3val b = -0x60000000 // -1610612736 
4println("b << 1 = ${b shl 1}") // 1073741824

上面的2种情形则有不同，当它们向左移位时，按照之前的逻辑，各自的值会翻倍。得到的结果超出了32位整数（int）的取值范围（-2³² ~2³²-1），超出的数位被舍弃。以0x5FFFFFFF为例，其2进制表示为：

        0101 1111 1111 1111 1111 1111 1111 1111
    << 1
    ---------------------------------------------
      0 1011 1111 1111 1111 1111 1111 1111 1110

最高位的0被舍弃，得到的结果高位为1，结果为负数。

左移运算为什么不需要区分逻辑左移和算术左移呢？
左移位数与符号位后位数对应的数只要是1，左移就会溢出，符号发生改变；反之，如果是0，则符号不会发生改变。

因为左移运算存在溢出。以上述-0x60000000为例，其原码的最高位为1（符号位后一位），由此可知，其左移1位，就会溢出，下图展示了其运算过程：

    原码：0110 0000 0000 0000 0000 0000 0000 0000
    反码：1001 1111 1111 1111 1111 1111 1111 1111
    补码：1010 0000 0000 0000 0000 0000 0000 0000
   << 1:   
    ---------------------------------------------------
       1 0100 0000 0000 0000 0000 0000 0000 0000

2. 右移运算 #

和左移运算一样，右移运算将所有的数据位向右移动，低位舍弃，高位补0/1。需要注意的是，对于有符号数，由于计算机用最高位表示符号位，因此根据符号位是否移动，可以将右移运算分为逻辑右移和算术右移。

对于正数来讲，逻辑右移和算术右移是相等的，正数的最高位为0，向右移动时，高位补充的也是0，对结果没有影响。

2.1 逻辑右移 #

逻辑右移又叫“无符号右移”，使用>>>表示，“逻辑”的意思是，不考虑符号位，所有数位全部右移。在这种情况下，负数右移就会发生符号变化。就像下面这样：

1val a = -0xf
2println("$a >>> 1 = ${a ushr 1}")  // -15 >>> 1 = 2147483640
3
4val b = 0xf
5println("$b >>> 1 = ${b ushr 1}") // 15 >>> 1 = 7
6
7val c = -0x80000000
8println("$c >>> 1 = ${c ushr 1}") // -2147483648 >>> 1 = 1073741824

可见，逻辑右移运算在操作负数的情况下，直接移动了符号位，最高位补0，负数也变成了正数。

下图简单地以-0xf为例，解释运算过程：

正数原码：0000 0000 0000 0000 0000 0000 0000 1111
    反码：1111 1111 1111 1111 1111 1111 1111 0000
    补码：1111 1111 1111 1111 1111 1111 1111 0001
----------------------------------------------------
>>> 1   : 0111 1111 1111 1111 1111 1111 1111 1000 1

2.2 算术右移 #

算术右移使用>>表示，相较于逻辑右移，算术右移考虑符号位：

若移动的是正数，符号位是0，移动时，符号位保持0不变，移动多少位，就在符号位后补多少0。从这个描述来看，正数的算术右移和逻辑右移结果是相等的；
若移动的是负数，符号位是1，，移动时，符号位保持1不变，移动多少位，就在符号位后补多少1。

简而言之，算术右移正数补0，负数补1。算术右移的结果就是，值变为原来的1/2。

1val a = -0xf
2println("$a >> 1 = ${a shr 1}") // -15 >> 1 = -8
3
4val b = 0xf
5println("$b >> 1 = ${b shr 1}") // 15 >> 1 = 7
6
7val c = -0x80000000
8println("$c >> 1 = ${c shr 1}") // -2147483648 >> 1 = -1073741824

右移运算不会出现溢出。

xf&pl

移位运算

1.左移运算 #

2. 右移运算 #

2.1 逻辑右移 #

2.2 算术右移 #