按位运算 - 位掩码操作是如何实现的？

Question

背景

我使用了很多位运算，但我甚至不知道它们在最低级别是如何实现的。

我想看一下英特尔/AMD开发人员如何实现这些操作。 不是为了在我的代码中替换它们，那样会很愚蠢... 而是为了更广泛地了解正在发生的事情。

我试图找到一些信息，但大多数时候，人们询问其用途或用其他位运算替换它，但这里并非如此。

问题

它是否在汇编（SSE）中对32位进行基本迭代和比较？

有没有一些技巧可以加快速度？

谢谢

- Larry

---

按位操作是原始操作，有汇编指令执行。因此它们是在 CPU 上的逻辑门中实现，而不是通过代码实现。 - Colonel Thirty Two

像 a = b & c; 这样的一行代码可能会有一个直接的机器指令或两个指令来执行它，而不太可能有任何技巧使其更快。 - chux - Reinstate Monica

Answer 1

绝大部分都是作为基本的本地指令直接在CPU上实现，而不是SSE的一部分。这些是CPU寄存器上最古老、最基本的操作。

至于如何实现and、or、xor等操作，如果你真的有兴趣，可以查阅数字逻辑设计或离散数学。查找Flip-flops、AND门或NAND/NOR/XOR门。

https://en.wikipedia.org/wiki/NAND_logic

还可以查阅K-map（卡诺图），这是你可以手动实现逻辑电路的方法。

https://en.wikipedia.org/wiki/Karnaugh_map

如果你真的喜欢阅读，可以在有工程或计算机科学大学资源的前提下报名数字逻辑设计课程。你将能够在面包板上使用大型集成电路构建逻辑电路，但现在大多数CPU都像软件一样通过代码编写并打印在硅晶圆上。

特别值得关注的是NAND和NOR，因为它们具有功能完备性（可以使用NAND或NOR构造任何真值表）。

NAND（逻辑符号看起来像=Do-）

A
  =Do- Q    is Q = NOT(A AND B)
B

Truth table
A    B     Q
0    0     1
0    1     1
1    0     1
1    1     0

使用NAND门可以重写任何逻辑。

正如您所看到的，它非常高效，使用二进制无法获得更低级别的单个门电路（虽然存在三进制/三态逻辑），因此它只需要一个时钟状态变化。 因此，对于一个64位CPU寄存器，您将需要在寄存器旁边放置64个这些"宝贝"，每个核心...每个指令。 而这仅仅是“逻辑”寄存器。因为先进的处理器（如Intel Core）进行寄存器重命名，所以在硅上存在比名称逻辑上可用的寄存器更多的物理寄存器。

- codenheim

---

"NOR" 也是功能完备的，就像 "NAND" 一样。 - nrz

+1 表示添加数字逻辑和 Karnaugh 地图的参考资料。 - Don Shankin

谢谢大家，我进行了修订并添加了NOR，并加入了一些ASCII艺术！如果您对更好的NAND或NOR的ASCII表示有建议，请告诉我。 - codenheim

如果处理器的物理寄存器比逻辑寄存器多得多，为什么它们不会暴露所有的物理寄存器呢？我的意思是，如果我们有16个逻辑寄存器和100个物理寄存器，为什么我们不能直接访问（而不是间接访问）这100个物理寄存器呢？ - Z boson

@Zboson - 我没有说“更多”的物理寄存器，是你说的。这只是“超标量”的一个方面。它可能意味着处理器有一些额外的（保留）或每个寄存器都有两个。它用于无序执行、推测和代码并行化，而不需要您（或编译器）显式编写操作来实现它。它们没有被公开的原因是：（1）寄存器现在真正是逻辑/虚拟概念，（2）如果它们被公开，人们会使用它们并破坏或干扰自动超标量功能。 - codenheim

其次，它们不必暴露。您可以使用它们所有，只是不明确地使用。处理器将通过并行发出指令为您的代码分配更多的实际寄存器。如果您有一个单独的代码块使用了比可用寄存器更多的寄存器，需要将它们溢出到堆栈中，那么您才会受到真正的限制。 - codenheim

Answer 2

AND、OR、XOR 和 NOT 操作在硅上实现相当高效，在大多数处理器上通常都是单周期本地指令。也就是说，对于一个 16 位处理器，整个 16 位寄存器会一次性进行 AND 运算；对于 32 位处理器，32 位一次性进行 AND 运算等等。你需要知道的唯一性能问题是对齐：例如，在 ARM 处理器上，如果一个 32 位值从一个内存地址开始，该地址是 4 的倍数，则可以在两到三个周期内执行读-修改-写操作。如果它在奇数地址上，则必须在相邻的对齐地址上执行两次读取和两次写入，因此速度较慢。

在某些旧处理器中，位移可能涉及循环移位。也就是说，“1 << 5” 所需的时间比 “1 << 2” 更长。但是，大多数现代处理器都具有所谓的“barrel shifter”，可使所有移位均衡到寄存器大小，因此在 Pentium 上，“1 << 31” 与 “1 << 2” 用时相同。

加法和减法也是快速的基元。乘法和除法则比较棘手：这些主要是作为微码循环来实现的。通过将循环展开成高端处理器中的大块硅片，可以加快乘法，但是除法无法这样做，因此一般情况下，除法是微处理器中最慢的基本操作。

- Lee Daniel Crocker

---

对于移位寄存器和对齐方式，加1。这就是为什么我们必须关注代码中的对齐方式。 - codenheim

Answer 3

按位操作是处理器的组成部分，因此自然要用指令来公开这些操作。像AND、OR、XOR、NOR、NAND和NOT这样的操作可以通过每位ALU只有几个逻辑门来执行。重要的是，结果的每个比特只依赖于输入的两个比特（不像乘法或加法），因此整个操作可以并行进行，没有任何复杂性。

- hcs

Answer 4

正如您所知，计算机中的数据以二进制格式表示。

例如，如果您有整数13，则表示为1101b（其中b表示二进制）。这相当于(1) * 8 + (1) * 4 + (0) * 2 + (1) * 1 = 13，就像(1) * 10 + (3) * 1 = 13一样--不同的进制。

然而，对于基本操作，计算机需要知道您正在处理多少数据。典型的整数大小为32位。因此，它不仅是1101b，而且是00000000000000000000000000001101b--32位，其中大部分未使用。

按位运算就是这样--它们仅在位级别上进行操作。加法、乘法和其他操作考虑多个位来执行其功能，但按位运算符不会。例如：

12按位与7是多少？（在C语言中，12 & 7）

1010b 12 &
0111b  7
-----  =
0010n  2

为什么？垂直思考！看左边的数字集合——1和0是0。然后，0和1是0。接着，1和1是1。最后，0和1是0。

这基于“与”真值表规则——只有真（即1）和真（即1）才会得到假（即0）。所有其他结果都是假（即0）。

同样地，“或”真值表规则指出，除了假（即0）和假（即0）得到假（即0）外，所有结果都是真（即1）。

让我们做同样的例子，但这次让我们计算12按位或7。（在C语言中，12 | 7）

1010b 12 |
0111b  7
-----  =
1111n 15

最后，让我们考虑另一个主要的位运算符：not。这是一个一元运算符，您只需翻转每个位。让我们计算按位非7（或在C术语中，~7）

0111b ~7
-----  =
1000b  8

等等..那些前导零呢？嗯，是的，在此之前我省略了它们，因为它们并不重要，但现在它们肯定很重要：

00000000000000000000000000000111b ~7
---------------------------------  =
11111111111111111111111111111000b  ... big number?

如果您指示计算机将结果视为无符号整数（32位），那么这是一个非常大的数字（略小于40亿）。如果您指示计算机将结果视为带符号整数（32位），那么结果为-8。

正如您可能已经猜到的那样，由于所有这些操作的逻辑非常简单，因此您不能做太多事情来使它们单独更快。但是，按位操作遵循布尔逻辑相同的逻辑，因此您可以使用布尔逻辑缩减技术来减少可能需要的按位操作数量。

例如：(A & B) | (A & C) 的结果与 A & (B | C) 相同。

然而，这是一个更大的话题。卡诺图是一种技术，但boolean algebra通常是我在编程时使用的技术。

- Kaganar

---

回顾起来，我可能误读了这个问题，但我会把它留在这里，以防对某人有用。 - Kaganar