仓颉中的位运算

  计算机内的数据存储和操作永远是二进制的。称一个占据 8 字节空间的对象为 Int64，仅仅表明我们以 Int64 的形式去理解和操作那 64 个比特位。从电路层面上，储存一个 Int64 的 8 字节空间与存储一个 Float64 的 8 字节空间没有什么不同，都存储着 64 个 0 或者 1。
  当我们操作一个整数对象，比如给它赋值时，是把其 64 个比特当成一个整体操作。有时，特别当我们的程序试图直接跟 CPU 之外的电路打交道时，我们期望能够直接操作一个对象的单个比特位。仓颉提供按位与&、按位或|、按位取反!、按与异或^、左移位<<、右移位>>等操作符，使得我们可以对构成整数对象的各个比特进行操作。

1. 二进制及16进制

  假设一个无符号16位整数由2字节共16比特构成，其每个比特的值如图1所示。

  在图1中，16个二进制位来源于连续的两字节存储空间，从低到高依次标为第0位 ~ 第15位，每一位分别对应位权2⁰ ~ 2¹⁵。

  为了帮助读者理解，作者特意画了十进制的9527₁₀的结构作为参照。十进制数9527₁₀的值 = 9 × 10³ + 5 × 10² + 2 × 10¹ + 7 × 10⁰。即，十进制数的值等于其每位的位值乘以对应的位权，再求和。

  类似地，无符号二进制数的值也等于其每位的位值乘以对应的位权，再求和。本例中，有：

  在编程时，如果直接书写二进制字面量是一件痛苦的工作，程序员要非常小心地反复确认那些0和1的数字有没有错漏。相对于二进制，那些长期与电路打交道的电气工程师更愿意使用十六进制。十六进制的每一位，可以表示0 ~ 15共16种组合，由于2⁴恰好等于16，所以每个十六进制位正好对应4个二进制位，其对应关系如表1所示。

  按照表1，我们很容易把二进制数换算成对应的十六进制。方法就是从低位往高位方向，将二进制位分为4位一组，然后按表1将每一组转成对应的十六进制符号即可。如图2所示，本例中的01001111101100102 = 4FB2₁₆，按字面量表示为0x4FB2。

  反过来，如果要把十六进制转换成二进制，则需要按表1将每个十六进制位转换成4位二进制，然后再串起来即可。

  请注意，本文关于位操作的讨论均基于无符号整数。对于有符号整数，由于补码的存在，问题要稍显复杂。在实践中，对有符号整数进行位操作的情况相对较少。

2. 按位取反

  仓颉支持对整数对象进行按位取反操作。

1
2
3
4
5
6
7
8
9
10

package BitNot
import std.convert

main(): Int64 {
    let c:UInt8 = 0b01011101            //8位无符号整数， 0b开头的字面量为2进制
    let d = !c    //对c按位取非
    println("c  = ${c.format('08b')}")  //08b表示按2进制输出8个符号，不足补0
    print("!c = ${d.format('08b')}")    //08b表示按2进制输出8个符号，不足补0
    return 0
}

上述程序的执行结果为：

1
2

c  = 01011101
!c = 10100010

  如执行结果所见，!c对c进行按位取反，简单地说就是0变1，1变0。

3. 按位与

  a & b中的&操作符将a对象与b对象的对应二进制位逐一进行按位与（and）运算。当且仅当a与b中的对应二进制位均为1时，结果位为1，否则为0。对于单个比特位的&运算，可以总结其规则如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package BitAnd
import std.convert 

main(): Int64 {
    let a:UInt32 = 0x8ffff37a   //0x开头的为16进制字面量
    let b:UInt32 = 0xfc7779f6

    let c:UInt32 = a & b 
    println("a   = ${a.format('032b')}")  //032b表示输出32位二进制，不足前方补0
    println("b   = ${b.format('032b')}")
    println("a&b = ${c.format('032b')}")
    
    let d = a & 0xfffffff7
    println("a              = ${a.format('032b')}")
    println("0xfffffff7     = ${UInt32(0xfffffff7).format('032b')}")
    print("a & 0xfffffff7 = ${d.format('032b')}")
    return 0
}

上述程序的执行结果为：

1
2
3
4
5
6

a   = 10001111111111111111001101111010
b   = 11111100011101110111100111110110
a&b = 10001100011101110111000101110010
a              = 10001111111111111111001101111010
0xfffffff7     = 11111111111111111111111111110111
a & 0xfffffff7 = 10001111111111111111001101110010

  执行结果的第1 ~ 3行反应了无符号整数a与b进行按位与运算的结果，请读者仔细逐一检查结果中每一个比特位的值与a、b对应位之间的关系。

▶第13行：将a与0xfffffff7进行按位与运算。

  请读者注意，0xfffffff7是一个很特别的数，在它的32个比特位中，只有第3位为0，其余位全为1。将UInt32对象a与0xfffffff7进行按位与运算，将导致如下结果：

• 结果的第3位将被置为0，不论其第3位本来是0还是1；

• 其余位不会发生变化（与a相同），因为任何值与1做与运算，值不变。

  请读者观察执行结果的第4 ~ 6行，检验上述分析是否正确。通过按位与运算，可以达到将对象的特定位“置0”同时又保持其它位不变的目的。

4. 按位或

  a | b中的|操作符将a对象与b对象的对应二进制位逐一进行按位或（or）运算。当且仅当a与b中的对应二进制位中至少有一个1时，结果位为1，否则为0。对于单个比特位的|运算，可以总结其规则如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package BitOr
import std.convert 

main(): Int64 {
    let a:UInt16 = 0xf37a
    let b:UInt16 = 0x79f6

    let c = a | b    //按位或
    println("a     = ${a.format('016b')}")
    println("b     = ${b.format('016b')}")
    println("a | b = ${c.format('016b')}")

    let d = a | 0x0800 
    println("a          = ${a.format('016b')}")
    println("0x0800     = ${UInt16(0x0800).format('016b')}")
    print("a | 0x0800 = ${d.format('016b')}")
    return 0
}

上述程序的执行结果为：

1
2
3
4
5
6

a     = 1111001101111010
b     = 0111100111110110
a | b = 1111101111111110
a          = 1111001101111010
0x0800     = 0000100000000000
a | 0x0800 = 1111101101111010

  执行结果的第1 ~ 3行反应了无符号短整数a与b进行按位或运算的结果，请读者仔细逐一检查结果中每一个比特位的值与a、b对应位之间的关系。

▶第13行：请读者注意，0x0800是一个很特别的数，在它的16个比特位中，只有第11位为1，其余位全为0。将UInt16对象a与0x0800进行按位或运算，将导致如下结果：

• 结果第11位将被置为1，不论其第11位本来是0还是1；

• 其余位不会发生变化（与a相同），因为任何值与0作或运算，值不变。

  请读者观察执行结果的第4 ~ 6行，检验上述分析是否正确。通过按位或运算，可以达到将对象的特定位“置1”同时又保持其它位不变的目的。

5. 按位异或

  a ^ b中的^操作符将a对象与b对象的对应二进制位逐一进行按位异或（xor）运算。当且仅当a与b中的对应二进制位不同时，结果位为1，否则为0。

6. 左移位

  a << n中的<<称为左移位操作符（left shift operator），它将对象a的二进制位逐次左移n位，超出左端的二进制位丢弃，并用0填充右端空出的位置。下述示例演示了<<操作符的用法。

1
2
3
4
5
6
7
8
9
10

package LeftShift
import std.convert

main(): Int64 {
    var a:UInt16 = 5
    println("a    = ${a.format('016b')},  value = ${a}")
    a = a << 3 
    print("a<<3 = ${a.format('016b')},  value = ${a}")
    return 0
}

上述程序的执行结果为：

1
2

a    = 0000000000000101,  value = 5
a<<3 = 0000000000101000,  value = 40

  第7行代码将a左移3位，执行结果显示，在左移三位后，右方空位全部填充了0。

  对于10进制数523₁₀，如果将其左移一位，右方补0，得5230₁₀，客观上，左移一位相当于把数字乘以10。同理，在不溢出的前提下，二进制数左移一位，右方补0，客观上相当于把该数乘以2。如果左移n位，则相当于把该数乘以2ⁿ。本例中，原值为5的a被左移了3位，相当于乘以2³，变为原始的8倍，结果为40。

7. 右移位

  a >> n中的>>称为右移位操作符（right shift operator），它将对象a的二进制位逐次右移n位，超出右端的二进制位丢弃。如果a是无符号整数，用0填充左端空位。

1
2
3
4
5
6
7
8
9
10

package RightShift
import std.convert 

main(): Int64 {
    var a:UInt16 = 2368
    println("a      = ${a.format('016b')}, value = ${a}")
    a = a >> 5
    print("a >> 5 = ${a.format('016b')}, value = ${a}")
    return 0
}

上述程序的执行结果为：

1
2

a      = 0000100101000000, value = 2368
a >> 5 = 0000000001001010, value = 74

  第7行代码将无符号整数a右移5位，执行结果显示，在右移五位后，左方空出位全部填充了0。

  与左移操作相反，将无符号整数右移1位，相当于将该数除以2，右移n位，相当于将该数除以2ⁿ。本例中，原值为2368的无符号16位整数a右移5位，相当于除以2⁵，即32，结果为74。

8. 置位与复位

  将整数的指定位“置为1”称为置位（set bit）；将整数的指定位“置为0”称为复位（reset bit）。之前的讨论已知：通过按位与运算，可以达到将对象的特定位“置0”同时又保持其它位不变的目的；通过按位或运算，可以达到将对象的特定位“置1”同时又保持其它位不变的目的。

  下述程序中的setBit()及resetBit()函数即是通过按位或及按位与操作实现置位和复位的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package SetResetBit
import std.convert 

func setBit(v:UInt16, bit:Int64): UInt16 {
    let r = v | (0x01 << bit)
    return r
}

func resetBit(v:UInt16, bit:Int64): UInt16 {
    let r = v & (!(0x01<<bit))
    return r
}

main(): Int64 {
    var v:UInt16 = 0xff00 
    println("before v = ${v.format('016b')}")
    v = setBit(v,6)
    v = setBit(v,0)
    v = setBit(v,11)   //置0，6，11位为1
    v = resetBit(v,15)
    v = resetBit(v,10) //置10，15位为0
    print("after  v = ${v.format('016b')}")
    return 0
}

上述程序的执行结果为：

1
2

before v = 1111111100000000
after  v = 0111101101000001

  图3以setBit(v,6)为例，来说明本程序的置位原理。本例中，程序首先使用0x01 << 6来构造一个第6位为1，其它位全为0的UInt16，然后再把这个临时对象与v作按位或运算，将v的第6位置位，其它位则保持不变。

  图4以resetBit(v,10)为例，来说明本程序的复位原理。本例中，程序首先使用0x01 << 10来构造一个第10位为1，其它位全为0的UInt16，然后再按位取反，得到一个第10位为0，其它位全为1的UInt16。然后，再把这个临时对象与v作按位与运算，将v的第10位复位，其它位则保持不变。

  多数CPU都没有提供直接操作单个比特位的机器指令，所以, 仓颉语言仅提供了基于单个字节、两个字节、四个字节及八个字节的整体位操作语法。单个比特位的操纵，只能通过上述运算来间接完成。