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

Question

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

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

对单词的操作是 O(1)。

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

如果我将两个单词相加，结果是一个超过 16 位的数字，我可以说明以下内容吗？

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

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

最后，

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

Answer 1

简短回答：

是的，将考虑单个按位 AND O(1)。

更多细节：

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

另一个有助于澄清的例子

以下代码块的复杂度为 O(1)：

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

虽然我们打印了 3 次 hello world，但每次运行它时，都会花费恒定的时间来运行和操作，并且如果有人将大量数据集输入到程序中，也不会花费更长的时间。无论输入什么，它都会简单地打印 3 件事。

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

在您的示例中，听起来您试图表明您有一些操作不需要所有位也能执行。即使这些较小的操作只考虑 4 位（例如 8 位）。当您的代码命中该代码时，它始终只会执行恒定数量的操作。这就像打印 4 个 hello world 语句而不是 8 个 hello world 语句。无论哪种方式，4 或 8 次打印，它仍然是恒定的。

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