从根本上讲，程序员需要操作位。现代处理器通过加载“寄存器”而不是单个位来操作数据。因此，程序员必须知道如何操作寄存器中的位。通常，我们可以在使用 8 位、16 位、32 位和 64 位整数进行编程时这样做。例如，假设我想将单个位设置为值 1。让我们在 64 位字中选择索引为 12 的位。仅在索引 12 设置位的单词是1<<12 ：数字 1 向左移动 12 次，或 4096。在 Go 中，我们使用fmt.Printf函数格式化数字：我们使用一个字符串，后面跟着格式化指令通过我们要打印的值。我们以具有特殊含义的字母%开始格式化序列（如果要打印% ，大多数人使用字符串%% ）。它后面可以跟字母b （代表二进制）、字母d （代表十进制）或x （代表十六进制）。有时我们想指定输出的最小长度（以字符为单位），我们通过一个前导数字来实现：例如， fmt.Printf("%100d", 4096)打印一个 100 个字符的字符串，以 4096 结尾并开始带空格。我们可以将零指定为填充字符而不是空格，方法是将其添加为前缀（例如， "%0100d" ）。在 Go 中，我们可以打印一个单词中的各个位，如下例所示：
package main import "fmt" func main() { var x uint64 = 1 << 12 fmt.Printf("%064b", x) }
运行这个程序，我们得到一个表示1<<12的二进制字符串：
0000000000000000000000000000000000000000000000000001000000000000
打印数字时的一般约定是首先打印最高有效数字，然后是最低有效数字：例如，当我们表示1000 + 200 + 30 + 4时，我们写 1234 。类似地，Go 首先打印最高有效位，因此数字1<<12有64-12=52前导零，后跟一个带有 11 个尾随零的1 。
我们可能会发现重新审视 Go 是如何表示负整数很有趣。让我们采用 64 位整数-2 。使用二进制补码表示法，该数字应表示为无符号数(1<<64)-2 ，除倒数第二位外，该数字应完全为 1。我们可以利用 Go 中的强制转换操作（例如uint64(x) ）保留二进制表示的事实：
package main import "fmt" func main() { var x int64 = -2 fmt.Printf("%064b", uint64(x)) }
该程序将按预期打印1111111111111111111111111111111111111111111111111111111111111110 。
Go 有一些相关的二元运算符，我们经常使用它们来操作位：
& bitwise AND | bitwise OR ^ bitwise XOR &^ bitwise AND NOT
此外，当用作一元运算时，符号^还用于翻转字的所有位： a ^ b计算a和b的按位异或，而^a翻转a的所有位。我们可以验证我们有a|b == (a^b) | (a&b) == (a^b) + (a&b) 。
我们还有其他有用的身份。例如，给定两个整数a和b ，我们有a+b = (a^b) + 2*(a&b) 。在恒等式中， 2*(a&b)表示进位，而a^b表示没有进位的加法。考虑例如0b1001 + 0b01001 。我们有0b1 + 0b1 == 0b10 ，这是2*(a&b)组件，而0b1000 + 0b01000 == 0b11000由a^b捕获。我们有2*(a|b) = 2*(a&b) + 2*(a^b) ，因此a+b = (a^b) + 2*(a&b)变成a+b = 2*(a|b) - (a^b) 。无论我们考虑无符号整数还是有符号整数，这些关系都是有效的，因为运算（按位逻辑、加法和减法）在位级别是相同的。
设置、清除和翻转位
我们知道如何创建一个只有一位设置为 1 的 64 位字（例如， 1<<12 ）。相反，我们也可以通过翻转所有位来创建一个由 1 组成的单词，但位索引 12 处的 0 除外： ^uint64(1<<12) 。在翻转表达式的所有位之前，指定其类型（采用uint64或uint32 ）有时很有用，以便结果明确。
然后我们可以使用这些词来影响现有词：
- 如果我们想将
w的第 12 位设置为 1：w |= 1<<12。 - 如果我们想清除（设置为零）单词
w的第 12 位：w &^= 1<<12（相当于w = w & ^uint64(1<<12)）。 - 如果我们只想翻转（将 0 发送到 1，将 1 发送到 0）第 12 位：
w ^= 1<<12。
我们也可能会影响一系列位。例如，我们知道单词(1<<12)-1除了 11 个最低有效位之外的所有位都设置为 0，并且 11 个最低有效位设置为 1。
- 如果我们想将单词
w的 11 个最低有效位设置为一个：w |= (1<<12)-1。 - 如果我们想清除（设置为零）单词
w的 11 个最低有效位：w &^= (1<<12)-1。 - 如果我们想翻转 11 个最低有效位：
w ^= (1<<12)-1。
表达式(1<<12)-1是通用的，如果我们想选择 60 个最低有效位，我们可以做(1<<60)-1。它甚至适用于 64 位：(1<<64)-1将所有位设置为 1。
我们还可以生成一个具有任意范围位集的单词：单词((1<<13)-1) ^ ((1<<2)-1)具有从索引 2 到索引 12（含）的位设置为 1，其他位设置为 0。通过这样的结构，我们可以有效地设置、清除或翻转一个字内的任意范围的位。
我们可以在一个字中设置任何我们喜欢的位。但是查询位集呢？我们可以通过检查w & (1<<12)是否非零来检查字u中的第 12 位是否已设置。实际上，如果第 12 位在w中设置，则表达式w & (1<<12)的值为1<<12 ，否则，它的值为零。我们可以扩展这样的检查：我们可以通过计算w & ((1<<13)-1) ^ ((1<<2)-1)来验证从索引 2 到索引 12（含）的任何位是否设置为 1 w & ((1<<13)-1) ^ ((1<<2)-1) 。当且仅当指定范围内的任何位都没有设置为 1 时，结果才为零。
高效安全的整数运算
通过根据位表示来考虑值，我们可以编写更高效的代码，或者等效地，更好地理解优化后的二进制代码可能是什么样子。考虑检查两个数字是否具有相同符号的问题：我们想知道它们是都小于零，还是都大于或等于零。一个天真的实现可能如下所示：
func SlowSameSign(x, y int64) bool { return ((x < 0) && (y < 0)) || ((x >= 0) && (y >= 0)) }
但是，让我们考虑一下负整数与其他整数的区别：它们的最后一位已设置。也就是说，作为无符号值，它们的最高有效位是 1。如果我们对两个整数进行异或 (xor)，那么如果它们的符号相同，则结果的最后一位将设置为零。也就是说，当且仅当符号一致时，结果为正（或零）。因此，我们可能更喜欢以下函数来确定两个整数是否具有相同的符号：
func SameSign(x, y int64) bool { return (x ^ y) >= 0 }
假设我们要检查x和y是否最多相差 1。也许x小于y ，但也可能更大。
让我们考虑计算两个整数的平均值的问题。我们有以下正确的功能：
func Average(x, y uint16) uint16 { if y > x { return (yx)/2 + x } else { return (xy)/2 + y } }
通过更好地了解整数表示，我们可以做得更好。
我们有另一个相关身份x == 2*(x>>1) + (x&1) 。这意味着x/2在[(x>>1), (x>>1)+1)之内。也就是说， x>>1是不大于x/2的最大整数。相反，我们有(x+(x&1))>>1是不小于x/2的最小整数。
我们有x+y = (x^y) + 2*(x&y) 。因此我们有(x+y)>>1 == ((x^y)>>1) + (x&y) （忽略x+y中的溢出）。因此， ((x^y)>>1) + (x&y)是不大于(x+y)/2的最大整数。我们还有x+y = 2*(x|y) - (x^y)或x+y + (x^y)&1= 2*(x|y) - (x^y) + (x^y)&1等等(x+y+(x^y)&1)>>1 == (x|y) - ((x^y)>>1) （忽略x+y+(x^y)&1中的溢出).因此(x|y) - ((x^y)>>1)是不小于(x+y)/2的最小整数。 (x|y) - ((x^y)>>1)和((x^y)>>1) + (x&y)之间的区别是(x^y)&1 。因此，我们有以下两个快速函数：
func FastAverage1(x, y uint16) uint16 { return (x|y) - ((x^y)>>1) }
func FastAverage2(x, y uint16) uint16 { return ((x^y)>>1) + (x&y) }
尽管我们使用类型uint16 ，但它的工作原理与整数大小无关（ uint8 、 uint16 、 uint32 、 uint64 ）并且它也适用于有符号整数（ int8 、 int16 、 int32 、 int64 ）。
高效的 Unicode 处理
在 UTF-16 中，我们可能有代理对：对中的第一个单词在0xd800到0xdbff范围内，而第二个单词在0xdc00到0xdfff范围内。我们如何检测效率代理对？如果值是使用uint16类型存储的，那么我们似乎可以通过两个比较检测代理对的值部分： (x>=0xd800) && (x<=0xdfff) 。但是，使用减法自然环绕这一事实可能会更有效： 0-0xd800==0x2800 。因此，只要我们有一个值是代理对的一部分， x-0xd800范围将介于 0 和0xdfff-0xd800之间（含）。但是，任何其他值都将大于0xdfff-0xd800=0x7fff 。因此，需要进行一次比较： (x-0xd800)<=0x7ff 。
一旦我们确定我们有一个可能对应于代理对的值，我们可以检查第一个值x1是否有效（在0xd800到0xdbff的范围内），条件为(x-0xd800)<=0x3ff ，类似地第二个值x2 ： (x-0xdc00)<=0x3ff 。然后我们可以将代码点重构为((x-0xd800)<<10) + x-0xdc00 。实际上，您可能不需要关心这样的优化，因为您的编译器可能会为您完成。然而，重要的是要记住，看似多重比较实际上可以作为单一比较来实施。
基本SWAR
现代处理器具有专门的指令，能够使用一条指令对多个数据单元进行操作（称为 SIMD，表示单指令多数据）。我们可以使用称为 SWAR（寄存器中的 SIMD ）的技术使用一条（或几条）指令执行多项操作。通常，我们会得到一个 64 位字w ( uint64 )，我们希望将其视为一个包含八个 8 位字 ( uint8 ) 的向量。
给定一个字节值 ( uint8 )，我可以通过一次乘法将它复制到一个字的所有字节上： x * uint64(0x0101010101010101) 。例如，我们有0x12 * uint64(0x0101010101010101) == 0x1212121212121212 。这种方法可以以各种方式推广。例如，我们有0x7 * uint64(0x1101011101110101) == 0x7707077707770707 。
为了方便起见，让我们将b80定义为等于0x8080808080808080的uint64 ，将b01定义为等于0x0101010101010101 uint64我们可以检查是否所有字节都小于 128。我们首先复制字节值，除了最高有效位之外的所有位都设置为零（ 0x80 * b01 ）或b80 ）然后我们用我们的 64 位字计算按位与并检查结果是否为零： (w & b80)) == 0 。它可能会在处理器上编译成两条或三条指令。
我们可以检查任何字节是否为零，假设我们已经检查过它们小于 128，使用诸如((w - b01) & b80) == 0的表达式。如果我们不确定它们是否小于零，我们可以简单地添加一个操作： (((w - b01)|w) & b80) == 0 。检查一个字节是否为零允许我们检查两个单词w1和w2是否具有匹配的字节值，因为发生这种情况时， w1^w2具有零字节值。
如果我们假设所有字节值不大于 128，我们还可以设计更复杂的操作。例如，我们可以通过以下例程检查所有字节值不大于 7 位值 ( t )： ((w + (0x80 - t) * b01) & b80) == 0 。如果值t是一个常量，那么乘法将在编译时进行评估，它应该比检查所有字节是否都小于 128 稍微贵一点。在 Go 中，我们检查没有字节值大于 77，假设通过验证b80 & (w+(128-77) * b01)是否为零，所有字节值都小于 128。类似地，我们可以检查所有字节值是否至少与 7 位t一样大，假设它们也都小于 128： ((b80 - w) + t * b01) & b80) == 0 。我们可以进一步概括。假设我们要检查所有字节是否至少与 7 位值a一样大并且不大于 7 位值b 。检查((w + b80 - a * b01) ^ (w + b80 - b * b01)) & b80 == 0就足够了。
旋转和反转钻头
给定一个词，我们说如果我们向左或向右移动位，我们会旋转这些位，同时在开始时将剩余的位移回。为了说明这个概念，假设给定了 8 位整数0b1111000 ，我们想将它向左循环 3 位。 Go 语言为此提供了一个函数（来自math/bits包的bits.RotateLeft8 ）：我们得到0b10000111 。在 Go 中，没有旋转右操作。但是，在处理 8 位整数时，向左旋转 3 位与向右旋转 5 位是一样的。 Go 为 8 位、16 位、32 位和 64 位整数提供旋转函数。
假设您想知道两个 64 位字（ w1和w2 ）是否具有匹配的字节值，而不考虑顺序。我们知道如何有效地检查它们是否具有匹配的有序字节值（例如， (((w1^w2 - b01)|(w1^w2)) & b80) == 0 。要将所有字节与所有其他字节进行比较，我们可以重复相同操作的次数与字中的字节数相同（64 位整数为八次）：每次，我们将其中一个字旋转 8 位：
(((w1^w2 - b01)|(w1^w2)) & b80) == 0 w1 = bits.RotateLeft64(w1,8) (((w1^w2 - b01)|(w1^w2)) & b80) == 0 w1 = bits.RotateLeft64(w1,8) ...
我们记得单词可以被解释为小端还是大端，这取决于第一个字节是最不重要还是最重要。 Go 允许您使用math/bits包中的函数bits.ReverseBytes64 64 位字中字节的顺序。 16 位和 32 位字有类似的功能。我们有bits.ReverseBytes16(0xcc00) == 0x00cc 。反转 16 位字中的字节和旋转 8 位是等效的操作。
我们也可以反转位。我们有bits.Reverse16(0b1111001101010101) == 0b1010101011001111 。 Go 具有反转 8 位、16 位、32 位和 64 位字的位的函数。许多处理器都有快速指令来反转位顺序，并且它可以是快速操作。
快速位计数
计算一个字中设置为 1 的位数可能很有用。 Go 在math/bits包中针对具有 8 位、16 位、32 位和 64 位的单词具有用于此目的的快速函数。因此我们有bits.OnesCount16(0b1111001101010101) == 10 。
同样，我们有时想要计算尾随零或前导零的数量。尾随零的数量是出现在最低有效位置的连续零位的数量。例如，字0b1没有尾随零，而字0b100有两个尾随零。当输入是 2 的幂时，尾随零的数量是以 2 为底的对数。我们可以使用 Go 函数bits.TrailingZeros8 , bits.TrailingZeros16
依此类推计算尾随零的数量。前导零的数量相似，但我们从最重要的位置开始。因此 8 位整数0b10000000有零个前导零，
而整数0b00100000有两个前导零。我们可以使用函数bits.LeadingZeros8 , bits.LeadingZeros16
等等。
虽然尾随零的数量直接给出了 2 的幂的对数，但我们可以使用前导零的数量来计算任何整数的对数，四舍五入到最接近的整数。对于 32 位整数，以下函数提供了正确的结果：
func Log2Up(x uint32) int { return 31 - bits.LeadingZeros32(x|1) }
我们还可以计算其他对数。直觉上，这应该是可能的，因为如果log_b是以b为底的对数，则log_b (x) = \log_2(x)/\log_2(b) 。换句话说，所有对数都在常数因子内（例如1/log_2(b) ）。
例如，我们可能对表示整数所需的小数位数感兴趣（例如，整数100需要三位数）。一般公式为ceil(log(x+1)) ，其中对数应以 10 为底。我们可以证明以下函数（由工程师 Kendall Willets 设计）计算 32 位整数所需的位数:
func DigitCount(x uint32) uint32 { var table = []uint64{ 4294967296, 8589934582, 8589934582, 8589934582, 12884901788, 12884901788, 12884901788, 17179868184, 17179868184, 17179868184, 21474826480, 21474826480, 21474826480, 21474826480, 25769703776, 25769703776, 25769703776, 30063771072, 30063771072, 30063771072, 34349738368, 34349738368, 34349738368, 34349738368, 38554705664, 38554705664, 38554705664, 41949672960, 41949672960, 41949672960, 42949672960, 42949672960} return uint32((uint64(x) + table[Log2Up(x)]) >> 32) }
虽然这个函数有点神秘，但它的计算主要涉及计算尾随零的数量，并使用结果在表中查找值。它只翻译少量 CPU 指令并且效率很高。
分度位
给定一个词，有时计算设置位（设置为 1 的位）的位置很有用。例如，给定单词0b11000111 ，我们希望索引 0、1、2、6、7 对应于值为 1 的 5 位。由于bits.OnesCount ，我们可以有效地确定我们需要生成多少索引功能。 bits.TrailingZeros函数可用于识别位的位置。我们还可以使用x & (x-1)将x的最低有效 1 位设置为零这一事实。以下 Go 函数生成一个索引数组：
func Indexes(x uint64) []int { var ind = make([]int, bits.OnesCount64(x)) pos := 0 for x != 0 { ind[pos] = bits.TrailingZeros64(x) x &= x - 1 pos += 1 } return ind }
给定0b11000111 ，它生成数组0, 1, 2, 6, 7 ：
var x = uint64(0b11000111) for _, v := range Indexes(x) { fmt.Println(v) }
如果我们想以相反的顺序计算位 ( 7, 6, 2, 1, 0 )，我们可以使用位反转函数来实现，如下所示：
for _, v := range Indexes(bits.Reverse64(x)) { fmt.Println(63 - v) }
结论
作为程序员，您可以高效地访问、设置、复制或移动单个位值。小心一些，您可以避免算术溢出而不会造成太大的性能损失。使用 SWAR，您可以像使用多个子词一样使用单个词。尽管这些操作中的大多数很少需要，但知道它们可用很重要。
原文： https://lemire.me/blog/2023/02/07/bit-hacking-with-go-code/