我在一次面试中被问到上述问题，面试官非常肯定答案。但我不确定。有人能帮我一下吗？
问问题
139 次
3 回答
2
当然。显而易见的蛮力方法只是一个大查找表，其中输入数字的每个可能值都有一个条目。如果数字很大，这不是很实用，但仍然足以证明它是可能的。
编辑：有人提出这完全是胡说八道，基本上任何算法都可以这样说。
在有限的程度上，这是一个公平的说法——但限制是如此严重，以至于对于大多数算法来说它仍然完全没有意义。
我最初的观点（至少在我记得的情况下）是人口计数大约相当于许多其他操作，例如我们通常假设为 O(1) 的加法和减法。
在硬件层面，单周期POPCNT指令的电路可能比单周期指令更容易ADD。仅举一个例子，对于任何实际大小的数据字，我们可以在 4 位块上并行使用表查找，然后将这些块的结果相加。即使使用不太可能的最坏情况假设（例如，为每个表单独存储），这仍然很容易在现代 CPU 中实现——事实上，它可能至少比提到的单周期加法或减法更简单一些以上1。
这与许多其他算法形成鲜明对比。举一个明显的例子，让我们考虑排序。即使是大多数人能想象到的最琐碎的排序——2 个项目，每个 8 位，我们已经在一个 64 KB 的查找表中获得恒定的复杂性。早在我们可以做一个相当简单的排序（例如，100 个项目）之前，我们需要一个查找表，其中包含的数据项比宇宙中的原子多得多。
从相反的方向来看，在某些时候，基本上没有O(1) 是肯定的。让我们考虑最简单的操作。对于 N 位 CPU，按位OR通常实现为一组OR并行的 N 个门。与加法不同，一位与另一位之间没有交互，因此对于任何实际大小的 CPU，这很容易在一条指令中执行。
尽管如此，如果我按位指定OR每个操作数为 100 petabit，那么甚至没有任何方法可以接近实际的方法来完成具有恒定复杂性的工作。使用通常的并行OR门方法，我们最终得到（除其他外）300 petabit 的输入和输出线——这个数字甚至完全使最大 CPU 上的引脚数量相形见绌。
在合理的硬件上，OR对 100 petabit 操作数进行按位运算需要一段时间（更不用说相当多的硬盘空间了）。如果我们将其增加到 200 petabit 操作数，时间可能会（大约）翻倍——所以从这个角度来看，这是一个 O(N) 操作。显然，对于其他“微不足道”的操作（如加法、减法、按位、按AND位等XOR）也是如此。
尽管如此，除非您有非常具体的指示说您将要处理非常庞大的操作数，否则您通常会将其中的每一个都视为恒定复杂性操作。从这些方面来看，就在固定时间执行的难度而言，POPCNT 指令一方面介于按位AND/ OR/XOR和另一方面的加法/减法之间。
1. 你可能想知道它怎么可能比在执行一些其他操作之后add实际包含 an 时更简单。add如果是这样，赞一个——这是一个很好的问题。
答案是因为它只需要一个小得多的加法器。例如，一个 64 位 CPU 需要一个半加器和 63 个全加器。在简单的实现中，您执行按位加法——即，将一个操作数的位 0 添加到另一个操作数的位 0。这会生成一个输出位和一个进位位。该进位位成为下一对位的加法输入。有一些技巧可以在某种程度上将其并行化，但是野兽的本质（可以这么说）是位串行的。
使用 POPCNT 指令，我们在进行单独的表查找后有一个加法，但我们的结果仅限于输入字的大小。给定相同大小的输入（64 位），我们的最终结果不能大于 64。这意味着我们只需要一个 6 位加法器而不是 64 位加法器。
由于如上所述，加法基本上是位串行的，这意味着POPCNT指令末尾的加法基本上比普通加法快得多。具体来说，它在操作数大小上是对数的，而简单的加法在操作数大小上大致是线性的。
于 2012-04-27T02:32:40.327 回答
1
一些处理器可以在一条指令中完成，显然对于有限大小的整数。查找 POPCNT 助记符以获取更多详细信息。
对于无限大小的整数，显然您需要读取整个输入，因此下限为 O(n)。
面试官可能是指位计数技巧（第一个谷歌结果如下）：http ://www.gamedev.net/topic/547102-bit-counting-trick---new-to-me/
于 2012-04-27T11:24:20.637 回答
1
如果位大小是固定的（例如 32 位或 64 位机器的自然字长），您可以迭代这些位并在 O(1) 时间内直接计算它们（尽管肯定有更快的方法来做到这一点） . 对于任意精度数（BigInt 等），答案必须是否定的。
于 2012-04-27T02:51:10.580 回答