Logo

菜单

发布于 2026-01-06 5 阅读
0

使用位运算符：为什么浪费空间使用很多位，而少位就能达到目的？

使用位运算符：为什么浪费空间使用很多位，而少位就能达到目的？

如今，我们生活在未来。内存非常便宜。当我们想要存储一个整数时，大多数情况下，即使数值很小，使用一个完整的多字节值来表示也是合理的。当然，这样做会浪费很多空间。这个数字2用 32 位整数表示如下：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Enter fullscreen mode Exit fullscreen mode

结尾处只有一部分内容被翻转——其余部分都只是填充内容。

我正在开发一个Chip8模拟器。要构建这样的模拟器，你需要创建一个整个计算机的软件表示。它包含程序存储器空间、一些用于短期存储的寄存器、一些计数器、一些布尔标志——执行程序所需的一切。

Chip8 的内存空间比现代计算机要有限得多。它的全部内存空间只有 4096 字节，而且其中一部分还被系统自身占用。在这种限制下，浪费所有空间毫无意义。我们应该尽可能每次只处理一个字节，这样周围的字节就可以有效地用于程序的其他部分。

事实上，正如我们将看到的，我们甚至不需要将自己限制在一个字节内。利用位运算符，我们可以高效地使用字节内的各个位来存储和传递信息，最大限度地减少空间浪费。

机器

我用的是 Rust，但你不需要懂 Rust 也能看懂这篇文章。以下是我的机器结构体：

/// The top-level software representation of the Chip8 machine
pub struct Machine {
    opcode: Opcode,
    /// Available memory space - 4K
    memory: [u8; 4096],
    /// CPU Registers
    registers: [u8; 16],
    /// Index register
    pub idx: u16,
    /// Program counter
    pub pc: u16,
    /// Graphics system - 2048 total pixels, arranged 64x32, each containing 0 or 1
    pub screen: [u8; 64 * 32],
    /// Delay timer - 60Hz, counts down if above 0
    pub delay_timer: u8,
    /// Sound timer - buzzes at 0.  60Hz, counts down if above 0
    pub sound_timer: u8,
    /// Call stack
    pub stack: [usize; 16],
    /// Stack pointer
    pub sp: usize,
    /// Keep track of the keypad - 0x0-0xF
    keys: [bool; 16],
    /// Flag to signal the screen state has changed and must be redrawn
    pub draw_flag: bool,
}
Enter fullscreen mode Exit fullscreen mode

你需要知道的最重要的一点是，`a`u8是一个无符号 8 位值，也就是一个字节，而 `a`u16是一个无符号 16 位值。这些usize类型是与机器相关的指针大小的值，用于索引数组。在我的例子中，它们类似于 `a` u64。

程序会与计算机的每个部件进行交互，而这些部件都有一个对应的软件表示。这样，你就可以通过编程方式随意连接实际的输入和输出，而运行中的程序对此毫不知情。在这个结构体内部，一切都像在物理机上一样正常工作。

十六进制表示

处理单个字节时，十六进制比十进制方便得多。一个十六进制数字正好对应一个 4 位值（或一个半字节），因此可以表示 4 位的所有可能组合：

0x0 -> 0 0 0 0
0x1 -> 0 0 0 1
0x2 -> 0 0 1 0
0x3 -> 0 0 1 1
0x4 -> 0 1 0 0
0x5 -> 0 1 0 1
0x6 -> 0 1 1 0
0x7 -> 0 1 1 1
0x8 -> 1 0 0 0
0x9 -> 1 0 0 1
0xA -> 1 0 1 0
0xB -> 1 0 1 1
0xC -> 1 1 0 0
0xD -> 1 1 0 1
0xE -> 1 1 1 0
0xF -> 1 1 1 1
Enter fullscreen mode Exit fullscreen mode

规律显而易见。这使得十六进制成为描述如此小容量内存的自然方式。一个字节由 8 位组成，也就是两个相邻的半字节。使用两个十六进制数字，我们可以表示从 0（0x00全 8 个零）到0xFF1（全 8 个一）的所有可能字节。

操作码

为了与机器状态交互，程序由一系列操作码组成。每个周期，机器读取当前操作码，然后根据找到的特定指令更新内存和寄存器中的状态。程序加载时，这些操作码会从起始地址开始，按顺序复制到计算机内存中：

/// Locate a program file by filename and load into memory.  Returns total bytes loaded.
pub fn load_game(&mut self, name: &str) -> Result<usize> {
    // Clear the memory to make way
    self.reset();
    let rom = SHELF.rom(name)?; // I have all game data pre-loaded in memory and tagged by name
    // Load in memory starting at location 512 (0x200), which is where the pc pointer starts
    for (idx, &byte) in rom.iter().enumerate() {
        self.memory_set(idx as u16 + self.pc, byte);
    }
    Ok(rom.len())
}
Enter fullscreen mode Exit fullscreen mode

所有数据都是逐字节复制的，self.pc指针用于跟踪机器当前正在查找的位置。然而，每条指令实际上都不止一个字节长。维基百科上有完整的列表，总共有 35 条指令。以下是一些示例：

1NNN -> Jump to address NNN
8XY4 -> Add the value in register Y to the value in register X
3XNN -> Skip the next instruction if the value in register X equals 0xNN
Enter fullscreen mode Exit fullscreen mode

这些数字都是十六进制的，因此每个操作码长度为 2 字节，即 16 位。在 Rust 中，我使用 ` u16datatype` 来处理这些数字。此外，每个操作码携带的信息量也不同。操作码的前缀和/或后缀是硬编码的，用于确定具体的指令，然后在指令内部使用不同的半字节（nibble）来表示不同的内容。请比较以下代码之间的差异：

0x1234 -> Jump to address 0x234
     1       2         3        4
0 0 0 1 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0 

Extract value 0x234 - pad to 0x0234
0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0
___

0x8234 -> Add the value in register 3 to the current value in Register 2
    8       2         3        4
1 0 0 0 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0 

Extract values 0x2 and 0x3
0 0 1 0
0 0 1 1

___

0x3234 -> Skip the next instruction if the value in register 2 equals 0x34
    3       2         3        4
0 0 1 1 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0

Extract values 0x2 and 0x34
0 0 1 0
0 0 1 1 0 1 0 0
Enter fullscreen mode Exit fullscreen mode

0x1234 和 0x8234 在位级表示上的唯一区别在于第一个半字节中翻转的位不同。然而，它们存储的信息使用方式却截然不同。要成功寻址所有 4096 个内存位置，单个字节是不够的，但 12 位就足够了，因此我们提取最后三个半字节，并将它们视为一个单独的数字。不过，要指定寄存器，只有 16 个寄存器——我们不需要那么多额外的空间。一个半字节就足以唯一地寻址任何一个寄存器。因此，第二个和第三个半字节用于指定目标寄存器，而最后一个半字节则用作另一个硬编码的操作码指示符。代码3XNN使用了第三种模式，提取两个值，其中一个是半字节，另一个是完整的字节。当寄存器 X 的值等于 NN 中的值时，它会跳过一条指令。

关键在于，虽然特定的比特模式可能相同或相似，但它们在程序中的理解方式却可能不同。根据每个信息单元可能出现的组合数量，有很多不同的方法可以有效地利用16位模式。这意味着你不能把操作码看作一个单独的数字，甚至不能看作两个独立的字节。它实际上是四个半字节，而你如何处理它们取决于具体的操作码。最合理的做法是将它们视为单个比特的模式。

位操作

位运算符会逐位检查每个操作数的各个位来得出结果，而不是像“数字”那样处理更高层次的抽象概念。我们将介绍&、|、<<和>>，并简要提及^。

提取特定小食

第一个例子是1NNN。机器执行此操作码所需的相关信息由操作码的最后三个半字节组成。确定这0x1234是一个此类操作码后，我们只需获取该0x234值即可。为此，您可以使用按位运算&，即 AND 运算：

AND
A  B  Result

0  0  0
1  0  0
0  1  0
1  1  1
Enter fullscreen mode Exit fullscreen mode

该AND操作检查两个值是否都设置为11、2 或true3。如果都设置为 1 A & B = 1，则结果为 1。如果两个值都未设置为 3，则结果为00、1 或false2。我们可以利用此方法查找 16 位值中部分被设置的位。例如0x1234 & 0x0FFF，如果我们取 1，则结果将包含最后三个半字节中被设置的位，并完全忽略第一个半字节：

0x1234 -> 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0
0x0FFF -> 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
&        ________________________________
0x0234 -> 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0
Enter fullscreen mode Exit fullscreen mode

通过对每一对比特依次应用 AND 运算规则，最终结果中第一个半字节（与数据无关）全部为零，并成功保留了第一个字节其余部分的信息。现在，我们得到了一个能够完美契合u16提取信息的比特模式。

我们可以使用相同的逻辑来获取例如最后一个字节，就像我们从0x34以下位置提取数据一样0x3234：

0x3234 -> 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0
0x00FF -> 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
&        ________________________________
0x0034 -> 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0
Enter fullscreen mode Exit fullscreen mode

在 Rust 中：

pub fn last_three_digits(&self) -> u16 {
    self.0 & 0x0FFF
}
Enter fullscreen mode Exit fullscreen mode

需要再次强调的是，这种将位值映射到半字节的巧妙方法只适用于十六0x34进制——16进制对应的是5210进制！很容易混淆。

提取任何小零食

作为前文概念的延伸，许多此类操作码只需要提取第二个和/或第三个半字节，而它们在内存中实际上是以连续字节的形式存储的。要获取第二个半字节，可以使用 `nb` 操作码，要获取第三个半字节0x0F00，可以使用 `nb`操作码。0x00F0

你可以为每个位置编写一个单独的函数，但使用位移操作来使其通用化并不难：

pub fn nibble_from_left(&self, from_most: u8) -> u8 {
    // Make sure the parameter is legal
    if from_most > 3 {
        panic!(
            "cannot get the {}th nibble from 2-byte number {:#0x}",
            from_most, self.0
        );
    };
    let bits = 4 * (3 - from_most);
    ((self.0 >> bits) & 0xF) as u8
}
Enter fullscreen mode Exit fullscreen mode

0x2让我们使用这个函数从中获取0x8234。该函数需要从最高有效位（或左侧）开始的索引，从 0 开始，因此要获取第二个半字节，作为参数传递的索引将是1。

首先，我们可以观察到，任何小于该半字节（或位于其右侧）的部分都完全无关紧要，可以完全忽略。我们只对单个半字节感兴趣，这意味着&只需对该半字节运行按位运算符，0xF即可提取所需内容并丢弃其前面的所有部分。通过使用>>右移运算符，我们可以将目标半字节移动到数字的末尾：

0x8234 -> 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0
>> 8
0x0082 -> 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
Enter fullscreen mode Exit fullscreen mode

向右移动一位，丢弃最右边的位，在左边填充一个新的 0 位，然后将所有内容向右移动。如果我们这样做八次，我们就丢弃了最后两个半字节，并将我们感兴趣的那个半字节移动到了末尾。现在我们可以运行&：

0x0082 -> 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0xF    -> 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
&      ___________________________________
0x0002    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Enter fullscreen mode Exit fullscreen mode

太棒了！利用 ` \begin{push >>}` 和 ` &\end{push}`，我们能够生成一个与所需数字完全对应的位模式。缺失的部分在于如何右移位——4 * (3 - from_most);这意味着我们将始终以 4 的倍数移动位，以便一次处理一个半字节。我们只需要知道要右移多少个半字节。要获取倒数第三位，就像本例一样，我们取 `\end{push}` 4 * (3 - 1) = 4 * 2 = 8。这样，我们就可以复用相同的逻辑来提取四个半字节中的任意一个。唯一改变的是我们丢弃的最后数据量——如果我们最终还是想要最后一个半字节，那么就是 `\end{push}` 4 * (3 - 3) = 0，而>> 0对一个数字应用 `\end{push}` 将保持原样。

这通常用于解析 Chip8 机器中使用的操作码。许多操作码的中间两个半字节都包含特定信息，所以我编写了一个辅助函数来提取这些信息：

pub fn middle_nibbles(&self) -> (u8, u8) {
    (self.nibble_from_left(1), self.nibble_from_left(2))
}
Enter fullscreen mode Exit fullscreen mode

(0x2, 0x3)调用时，它将非常整齐地返回结果0x8234。

合并字节

当我们把程序（或一系列操作码）加载到内存中时，我们一次复制一个字节。这意味着每个操作码占用两个相邻的内存位置。我们需要将它们组合起来，并将这 16 个连续的比特序列理解为一个单一的数字。换句话说，我们需要找到u16将两个u8值并排放置后得到的值。如果你有字节 a0xAB和0xCDb，如何生成 16 位的值 n 0xABCD？

从图纸上看，我们可以直观地看到解决方案：

0xAB   -> 1 0 1 0 1 0 1 1
0xCD   ->                 1 1 0 0 1 1 0 1
0xABCD -> 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
Enter fullscreen mode Exit fullscreen mode

你只需要占用足够大的空间，然后将高位字节放在低位字节的左侧即可。当然，由于软件中没有纸笔，我们只能使用位运算符来实现这一点。

为了从较长的位序列中分离出一个半字节，我们使用了上面的右移操作>>将所需的半字节移到末尾。反向的左移操作<<也存在，它会丢弃左侧的较高有效位，并在右侧填充零。如果我们左移 8 位，实际上就是插入一个空字节：

0xAB   -> 1 0 1 0 1 0 1 1
<< 8
0xAB00 -> 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0
Enter fullscreen mode Exit fullscreen mode

太好了！要插入我们实际想要的第二个字节，我们可以使用按位运算符 `__`OR或 ` |__`。它的功能与 `__` 类似，AND但真值表如下：

OR
A  B  Result

0  0  0
1  0  1
0  1  1
1  1  1
Enter fullscreen mode Exit fullscreen mode

区别在于，如果操作数中任一位为假，则此运算符返回true/ 。只有当两个位都为假时，它才返回假。我们可以利用这一点将新展开的第一个字节与预期的第二个字节合并：11

0xAB00 -> 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0
0xCD   -> 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1
|       _________________________________
0xABCD -> 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
Enter fullscreen mode Exit fullscreen mode

此操作会从两个字节中提取相关信息，从而有效地将它们组合起来。因此，首先，将高位字节移位，然后将其与低位字节进行按位或运算，以提取所需的单个 16 位值：

pub fn combine_bytes(byte_one: u8, byte_two: u8) -> u16 {
    (byte_one as u16) << 8 | byte_two as u16
}
Enter fullscreen mode Exit fullscreen mode

当模拟器模拟一个周期时，它会从当前程序计数器开始读取两个字节，并使用以下方法将它们组合起来，以了解当前的操作码：

fn fetch_opcode(&self) -> Result<Opcode> {
    let first_byte = self.current_byte();
    let second_byte = self.memory_get(self.pc + 1);
    Ok(Opcode::new(first_byte, second_byte)?)
}
Enter fullscreen mode Exit fullscreen mode

在我的实现中，Opcode::new()逻辑部分包含了对这个内部方法的调用combine_bytes。

杂项

这些是我在处理 Chip8 操作码时使用的位运算，但理解这些运算符可以帮助我们非常高效地实现一些其他常用的操作。

偶数或奇数

一个非常实用的技巧是判断一个数是奇数还是偶数。我们很多人都会用到取模运算符：byte % 2 == 0如果除以 2 的余数为 0，那么这个数就是偶数。

实际上，据我所知，有两种方法可以做到这一点。我们在本文中已经讲解过按位与运算，所以我将介绍它——它类似于我们之前用来提取半字节的技巧。在数字的二进制表示中，我们只需要最后一位就能判断一个数字是偶数还是偶数。如果是偶数，则最后一位为 0；如果是奇数，则最后一位为 1。如果这个观察不够直观，可以返回前面查看十六进制数字到半字节的映射，看看你是否能理解其中的原因。

这意味着只需将你的值与另一个值进行“与”运算即可1。如果待检查的值以 1 结尾，则结果为 1；如果以 0 结尾，则结果为 0。

5 -> 0 1 0 1
1 -> 0 0 0 1
&  _________
1 -> 0 0 0 1

___

6 -> 0 1 1 0
1 -> 0 0 0 1
&  _________
0 -> 0 0 0 0
Enter fullscreen mode Exit fullscreen mode

然后，检查一下结果。如果该位被置位，则结果为奇数；否则，结果为偶数。在 Rust 中：

fn is_even(val: u32) -> bool {
    val & 1 == 0
}
Enter fullscreen mode Exit fullscreen mode

这适用于任何大小的值，因为它只会查看最低有效位。

虽然在大多数应用中性能提升可能微乎其微，但这种解决方案比使用其他方法更高效%。在某些情况下，选择这种方案就足够了。

我把我知道的另一种解法留给大家作为练习——你能用按位异或（XOR）实现吗？这个运算符^在很多编程语言中都有实现方式。以下是真值表：

XOR
A  B  Result

0  0  0
1  0  1
0  1  1
1  1  0
Enter fullscreen mode Exit fullscreen mode

^/操作与/XOR类似，但只有当其中一个位被设置时才返回 true，而不是两个位都被设置。请在评论区告诉我你的结果！|OR

双数/半数

我们上面用到的左移和右移操作非常方便。当你把二进制数中的位向左移动时，最终值会翻倍：

6  -> 0 1 1 0
<< 1
12 -> 1 1 0 0
Enter fullscreen mode Exit fullscreen mode

从上面的例子中可以看出，反过来也一样。向右移动会抵消上述操作，有效地将值减半。你可以将此方法推广到任何 2 的幂次方：

6  -> 0 0 1 1 0

<< 2
24 -> 1 1 0 0 0

<< 3
48 -> 1 1 0 0 0 0
Enter fullscreen mode Exit fullscreen mode

向右平移 n 位相当于乘以 2^n。妙啊！就像奇偶数技巧一样，这种方法可能比直接乘法更高效——不过，可读性会降低一些。任何优化都取决于具体情况。

像这样的位运算“技巧”还有很多。在下方分享一些你最喜欢的技巧吧！

致谢

如果你打算自己编写 Chip8 模拟器，虽然维基百科页面包含了大部分所需信息，但我还是推荐Laurence Muller的《如何编写模拟器》。到目前为止，这篇博文和维基百科是我唯一需要的参考资料。

封面图片： Federica Galli拍摄，来自Unsplash

文章来源：https://dev.to/decidously/using-bitwise-operators-why-waste-space-use-many-bits-when-few-bits-do-trick-2ap6
Docker Swarm vs K...
💡 17 个你可以独立开发的微型...