1 1
Go的Bit操作

原文地址:https://medium.com/learning-the-go-programming-language/bit-hacking-with-go-e0acee258827

本文是对原文的个人翻译,翻译不是很完善,能理解其中的思想即可。翻译原文的原因是之前参加公司的算法比赛,做题过程中我们在自身的程序做了较多的位运算操作,觉得比较有意思,于是根据原文翻译出下文内容 :)

在计算机正处于发展初期的阶段,内存和处理能力相对有限,于是为了避免这些昂贵的开销,人们一般都首选直接进行位操作的方式获取数据。直至今天,虽然计算机硬件飞速发展,内存和CPU的处理能力已经不是什么问题了,但位操作依然在一些情况(例如:底层系统编程、图像处理、密码加密解密等)中扮演重要的角色。

Go这门编程语言为我们提供了一些位运算符操作,如下:

 &   bitwise AND
 |   bitwise OR
 ^   bitwise XOR (异或)
&^   AND NOT
<<   左移
>>   右移

下文我们会根据上面的位运算符来详细地进行说明与举例说明用法

一、 & 操作符

在Go里面,&操作符用于在两个整数值之间执行AND运算操作。我们先回顾下AND操作的一些属性:

假设给定数值 a,b

只有满足 a = b = 1 的情况下下
AND(a,b) = 1,否则为 0

所以AND的另外一个很好的效果是可以用于把一个整数进行清零。举个例子,我们可以使用 & 操作符把至少具有4个LSB清零:

LSB或lsb可以指: Linux标准规范(Linux Standard Base)。 最低有效位(英语:Least Significant Bit,lsb),一个二进制数字中的第0位(即最低位);若LSB为全大写,则指的是多字节序列中最小权重的字节(Least Significant Byte)

func main() {
    var x uint8 = 0xAC    // x = 10101100
    x = x & 0xF0          // x = 10100000
}

所有的二元操作支持缩写的方式,所以上面的例子,可以用以下简写的方式达到同样效果:

func main() {
    var x uint8 = 0xAC    // x = 10101100
    x &= 0xF0             // x = 10100000
}

这里说下另外一个使用 & 的技巧:我们可以使用他它来检验我们整数的奇偶性。当一个整数的LSB等于1,我们可以认为他是奇数,换句话说,非1的就被认为是偶数:

import (
    “fmt”
    “math/rand”
)
func main() {
    for x := 0; x < 100; x++ {
        num := rand.Int()
        if num&1 == 1 {
            fmt.Printf(“%d is odd\n”, num)
        } else {
            fmt.Printf(“%d is even\n”, num)
        }
    }
}

二、 | 操作符

| 操作符对整数部分执行OR操作。回顾一下OR操作符的属性:

给定数值 a, b 

当 a = 1 或者 b = 1
OR(a,b) = 1
否则为 0

我们可以对一个给定的整数选择性地使用OR操作符设置各个位的值。例如,在下面的例子中,我们使用OR运算符(从最低位到最高位(MSB))将第3位,第7位和第8位设置为1。

func main() {
    var a uint8 = 0
    a |= 196
    fmt.Printf(“%b”, a)
}
// prints 11000100

当我们使用位掩码的手段为给定的整数值设置任意位时,使用OR是非常有用的,例如:

func main() {
    var a uint8 = 0
    a |= 196
    a |= 3
    fmt.Printf(“%b”, a)
}
// prints 11000111

前面的程序中,不仅具有十进制196的位,还具有十进制值3的最后两个最低有效位。我们可以继续用同样的方式进行OR操作更多的位字段进行掩码设置。

使用位进行配置

现在,我们通过 AND(a, 1) = a if and only if a = 1。我们可以使用这个定理去对一系列的位值进行查询。举个例子,上面的例子中,a & 196 会返回 196 因为a本身已经包含196。所以我们可以结合使用AND、OR 操作符来实现具体的配置操作,下来通过代码来举例:

const (
    UPPER  = 1 // upper case
    LOWER  = 2 // lower case
    CAP    = 4 // capitalizes
    REV    = 8 // reverses
)
func main() {
    fmt.Println(procstr(“HELLO PEOPLE!”, LOWER|REV|CAP))
}
func procstr(str string, conf byte) string {
    // reverse string
    rev := func(s string) string {
        runes := []rune(s)
        n := len(runes)
        for i := 0; i < n/2; i++ {
            runes[i], runes[n-1-i] = runes[n-1-i], runes[i]
        }
        return string(runes)
    }
 
    // query config bits
    if (conf & UPPER) != 0 {
        str = strings.ToUpper(str)
    }
    if (conf & LOWER) != 0 {
        str = strings.ToLower(str)
    }
    if (conf & CAP) != 0 {
        str = strings.Title(str)
    }
    if (conf & REV) != 0 {
        str = rev(str)
    }
    return str
}

上面函数调用 procstr(“HELLO PEOPLE!”, LOWER|REV|CAP) 会对字符串先进行小写处理,然后进程反转处理,最后再进行首字母大写处理。

三、 ^ 操作符

^ 操作符主要用于XOR 异或运算,它具有以下的属性:

假设给定 a, b 
当且只有 a!=b 时
XOR(a,b) = 1
否则等于 0

根据XOR的定义,它的实现主要用于把一个值切换到另外一个值。例如,给定一个16位的值,我们可以对它的高八位进行值切换:

func main() {
    var a uint16 = 0xCEFF
    a ^= 0xFF00 // same a = a ^ 0xFF00
}
// a = 0xCEFF   (11001110 11111111)
// a ^=0xFF00   (00110001 11111111)

上面的代码中,每一位根据与1进行XOR的位被翻转(从0到1或从1到0),从而比较符号的大小。当(a ^ b)≥0(或(a ^ b)<0为相反符号)时,两个整数a,b具有相同的符号

func main() {
    a, b := -12, 25
    fmt.Println(“a and b have same sign?“, (a ^ b) >= 0)
}

^补充:

与其他语言(c / c ++,Java,Python,Javascript等)不同,Go没有专门的一元位运算符。相反,异或运算符^也可以用作一元运算符来对数值进行补码。

如,给定 x,在Go中: ^ x = 1 ^ x中反转位。

我们可以在下面的代码片段中看到这一点,它使用^ a来取代变量a的补码。

func main() {
    var a byte = 0x0F
    fmt.Printf(“%08b\n”, a)
    fmt.Printf(“%08b\n”, ^a)
}

// prints
00001111     // var a
11110000     // ^a

四、 &^ 操作符

&^ 可以读作 AND NOT,它具有以下的属性:

假设给定 a, b 
AND_NOT(a,b) = AND(a,NOT(b))

有意思的是,我们可以根据第二个参数出现的1对第一个参数的对应位进行清零操作

AND_NOT(a, 1) = 0; clears a
AND_NOT(a, 0) = a; 

下面我们通过 AND NOT 来对变量a清理其最后4个LSB(从1010 1011 变为 1010 0000)

func main() {
    var a byte = 0xAB
     fmt.Printf("%08b\n", a)
     a &^= 0x0F
     fmt.Printf("%08b\n", a)
}
// prints:
10101011
10100000

五、 >> 和 << 操作符

跟大部分基于C语言一样,Go使用 >> 和 << 来分别表示左移和右移运算符,如下所示:

给定 a 和 n,
a << n; 对a的所有位向左移n次
a >> n; 对a的所有位向右移n次

例如,下面的代码:

func main() {
    var a int8 = 3
    fmt.Printf(“%08b\n”, a)
    fmt.Printf(“%08b\n”, a<<1)
    fmt.Printf(“%08b\n”, a<<2)
    fmt.Printf(“%08b\n”, a<<3)
}
// prints:
00000011
00000110
00001100
00011000

请注意,每次移位时,右侧的LSB都是零填充的。反之,使用右移位运算符,每个位的值可以向右移位,MSB在左侧填零,如以下示例所示:

func main() {
 var a uint8 = 120
 fmt.Printf(“%08b\n”, a)
 fmt.Printf(“%08b\n”, a>>1)
 fmt.Printf(“%08b\n”, a>>2)
}
// prints:
01111000
00111100
00011110

左移或右移位算子可以完成的一些最简单的技巧是乘法和除法,其中每个移位位置代表2的幂。例如,以下将200(以a存储)除以2。

func main() {
    a := 200
    fmt.Printf(“%d\n”, a>>1)
}
// prints:
100

或者通过移位实现乘以4的效果:

func main() {
    a := 12
    fmt.Printf(“%d\n”, a<<2)
}
// prints:
48

移位运算符提供了一些有趣的方法来处理二进制值中指定位置的位。例如,在以下代码片段中,| 和 << 组合使用可以对变量a的第三位bit进行设置

func main() {
    var a int8 = 8
    fmt.Printf(“%08b\n”, a)
    a = a | (1<<2)
    fmt.Printf(“%08b\n”, a)
}
// prints:
00001000
00001100

或者,你可以结合shift和&运算符来测试是否将第n位设置为一个值,如以下代码片段所示:

func main() {
    var a int8 = 12
    if a&(1<<2) != 0 {
        fmt.Println(“take action”)
    }
}
// prints:
take action

通过使用 &^ 和 移位操作,我们可以取消设置值的第n位:

func main() {
    var a int8 = 13 
    fmt.Printf(“%04b\n”, a)
    a = a &^ (1 << 2)
    fmt.Printf(“%04b\n”, a)
}
// prints:
1101
1001

总结

与其他现代语言一样,Go支持所有按位运算符。这篇文章只提供了一些可以用这些操作符完成的各种各样的技巧性操作。