我可以假设按位与运算是 O(1) 吗？如果是，为什么？

Question

我的处理器只能对 8 位或 16 位无符号整数进行算术运算。

1) 这意味着该处理器的字长是 16 位，对吗？

单词的运算复杂度为 O(1)。

这与处理器工作原理的实际电路级实现有关，对吗？

如果我将两个单词相加，结果是一个超过16位的数字，我可以这样写吗？

1) 处理器可以将数字相加，但只会报告 16 位最低有效数字。

2) 也报告超过 16 位，处理器必须有允许这些大数字（不适合一个字的数字）操作的软件。

最后，

假设我有一个单词 w，它是一个 16 位数字，我想要八个最低有效数字。我可以做 w & 0xFF。这个操作的时间复杂度是多少？这是 O(1) 也是因为处理器的电路级实现吗？

Answer 1

依次为：

没有。如果您的处理器可以执行 8 位或 16 位操作，则它可以是 8 位或 16 位处理器。事实上，它更有可能是 8 位，因为大多数处理器都试图处理双倍大小的操作。
是的，O(1)。但不是因为它在硬件中，而是因为它在硬件中实现了 O(1)。另外，请记住，所有 O(x) 实际上都是 "times a constant." 因此，如果某些东西是 O(16)，那实际上是 O(1) 乘以常数 16.

最后，如果您有一个 16 位字并且想要低位，并且您的处理器确实支持 8 位操作，您可以使用 MOV 指令访问低位。类似于：

mov16 ax, (memory)
mov8  (othermemory), al

如果那不可用，并且您必须执行 AND，那么是的，AND 将是 O(1)，因为它几乎可以肯定在硬件中是这样的。即使不是，最坏的情况下也可能是 O(8)，这实际上是 O(1) 的别名。

Answer 2

首先关于添加。大多数 CPU 在某些处理器状态寄存器中都有所谓的进位标志，可让您检测加法和减法溢出寄存器的位大小。因此，找出特定 CPU 上的寄存器大小以确定数据总线带宽，然后找出如何检查状态寄存器标志。大多数 CPU 将有一个带有和不带进位的 SUB 和 ADD。

接下来，关于时间复杂度：你不能假设为此使用大 O 表示法。您需要找出 CPU 在绝对时间内执行操作所需的周期（频率 * 周期），然后您需要考虑其他因素，例如内存访问与 L1 和 L2 缓存访问，以确定该操作将花费的总时间 CPU。

最后，从汇编代码访问内存（正如您似乎暗示的那样）让您比 Python 这样的高阶语言更有效率。 CPU 将包含可以调整其内存寻址以适应您正在寻找的大小的指令。类 C 语言也将在语言中具有这种能力，但 Python 不会。 JavaScript 甚至没有整数，但我离题了...

如果您的目标是了解低级编程，这对您更好地理解机器总是有好处的，特别是关于指针和调试，我鼓励您拍摄有关 Arduino 的视频 class。您甚至可以享受它并开始新的爱好。

Answer 3

您显然对 O(...) 的含义有些困惑。

大O符号需要一个变量；例如，使用比较和交换 n 元素的数组进行排序已知至少为 O(n*log(n)) 并且您有 n变量：随着 n 的增加，排序时间也会增加得更快。当说 x & 0xFF 是 O(1) 时，你说的变量是什么？
big-O 是关于抽象算法的，其中 n 可以增长到无穷大。如果 n 并且计算机受到上限的限制，那么任何算法都不会终止或受常数限制（讨论某事的限制是没有意义的如果 n 不能超过特定限制，n 会增加到无穷大。

在谈论低级硬件操作时，所有操作都是 O(1)。有些速度更快，只需要一个 "step"（如清除寄存器），有些则需要更多步骤（如整数除法）。然而，即使除法也最多需要 n 步，其中 n 是一个小整数。

具体讨论不同算法的性能时CPU使用大O符号没有意义，你可以做的是计算完成一个算法所需的机器周期数显式公式，可能取决于输入大小 n，但其中 n 不能增长到无穷大。

这就是 Knuth 在 TAOCP

中所做的

PS：不幸的是，今天的 CPU 太复杂了，以至于循环计数在现实世界中不再起作用。例如，它们可以将指令拆分为并行重新调度为运行的微指令，它们支持具有回溯、分支预测和其他难以分析技术的推测执行。最重要的是，缓存问题在当今极为重要，不同但兼容的 模型可以采用截然不同的方法。真正知道使用现代 CPUs 执行一段代码需要多长时间的唯一方法就是运行并在特定 CPU 模型和硬件上对真实数据进行测量。

Answer 4

简答：

是的，单个按位与将被视为 O(1)。

更多细节：

即使您查看每个位的操作数，它仍然是 O(1)。位操作的实际数量可能因变量类型而异，例如8 位、16 位、32 位和 64 位（甚至 128 位或更多）。关键是无论底层机器使用什么，它仍然会执行 constant 次操作来执行它。因此，即使计算机随着时间的推移而发展，按位 AND 仍将是 O(1).

另一个帮助说明的例子

下面的代码块是 O(1):

print('Hello World');
print('Hello World');
print('Hello World');

虽然我们打印了3次hello world，但是每次我们运行它都会花费一定的时间来运行并运行，如果有人喂大块，也不会花费更长的时间数据集到程序中。无论输入如何，它只会打印 3 样东西。

在按位与的情况下，我们执行指定数量的子操作，这些子操作总是相同的数量。例如8、16、32 等用于一次操作，但它始终相同或不变。

在您的示例中，您似乎在尝试表明您有一些不需要所有位也能执行的操作。即使这些较小的操作只考虑了 8 位中的 4 位。您的代码在遇到该代码时总是只会执行固定数量的操作。就像打印 4 个 hello world 语句而不是 8 个 hello world 语句。无论哪种方式，打印 4 或 8 次，它仍然不变。

这就是为什么单个按位与运算是 O(1)。

我可以假设按位与运算是 O(1) 吗？如果是，为什么？

Can I assume that a bitwise AND operation is O(1)? If so why?

algorithm

big-o

time-complexity

bitwise-and